Permutations: Applications

c go java js lua py vbs rkt scm pro

This page contains some applications and examples of permutation processing.

The process of enumeration is sometimes called "brute force".

The process of listing every possible alternative, object, thing, etc., is called enumeration.

Brute force enumeration requires looking at all possibilities.

In the case of a combination lock, this is all the possible combinations (permutations).

How many combinations are there on a typical combination lock?

The numbers on the lock range from 0 to 39, or 40 values.
There are 3 turns to be made to open the lock.
Thus, there are 40 choices for the first turn, 40 choices for the second turn, and 40 choices for the third turn.

Thus, the number of combinations for a typical combination lock is 40*40*40 = 64,000.

How long would a brute force attack take? What happens if the last number is known? Note: Order matters, so a combination lock is really a permutation lock. But the generation of the "combinations" does not follow exactly the permutation algorithm (since there is replacement).

This page looks at a simple combination lock and brute-force processing.

To keep it simple, each setting has 3 choices instead of 40 choices.

That yields 27 possibilities instead of 64,000 but the concepts remain the same.

The goal of the program is to output all possible combinations (actually permutations).

An iterative program uses nested loops.

Here is the C code.

#include <stdio.h>

int main() {
	printf("Settings:\n");
	printf("\n");
	int count1 = 0;
	for (int s1=1; s1 <= 3; s1++) {
		for (int s2=1; s2 <= 3; s2++) {
			for (int s3=1; s3 <= 3; s3++) {
				count1++;
				printf("\t%d. %d-%d-%d\n",count1,s1,s2,s3);
				}
			}
		}
	return 0;
	}

Here is the output of the C code.

Settings:

	1. 1-1-1
	2. 1-1-2
	3. 1-1-3
	4. 1-2-1
	5. 1-2-2
	6. 1-2-3
	7. 1-3-1
	8. 1-3-2
	9. 1-3-3
	10. 2-1-1
	11. 2-1-2
	12. 2-1-3
	13. 2-2-1
	14. 2-2-2
	15. 2-2-3
	16. 2-3-1
	17. 2-3-2
	18. 2-3-3
	19. 3-1-1
	20. 3-1-2
	21. 3-1-3
	22. 3-2-1
	23. 3-2-2
	24. 3-2-3
	25. 3-3-1
	26. 3-3-2
	27. 3-3-3

Note that this way of handling a "permutation" is not quite what the rsPermute module handles. This is common in computer science. Algorithms have many variations on a theme. Here is the C code.

#include <stdio.h>

#define SETTINGMAX 4

// global variables
int settingList1[SETTINGMAX+1];
int settingCount1;

void lockDo1(int start1, int stop1) {
	if (start1 > stop1) {
		settingCount1++;
		printf("\t%d. ",settingCount1);
		for (int pos1=1; pos1 <= stop1; pos1++) {
			if (pos1 != 1) {
				printf("-");
				}
			printf("%d",settingList1[pos1]);
			}
		printf("\n");
		}
	else {
		for (int pos1=1; pos1 <= stop1; pos1++) {
			settingList1[start1] = pos1;
			lockDo1(start1+1,stop1);
			}
		}
	}

int main() {
	printf("Settings:\n");
	printf("\n");
	lockDo1(1,3);
	return 0;
	}

Here is the output of the C code.

Settings:

	1. 1-1-1
	2. 1-1-2
	3. 1-1-3
	4. 1-2-1
	5. 1-2-2
	6. 1-2-3
	7. 1-3-1
	8. 1-3-2
	9. 1-3-3
	10. 2-1-1
	11. 2-1-2
	12. 2-1-3
	13. 2-2-1
	14. 2-2-2
	15. 2-2-3
	16. 2-3-1
	17. 2-3-2
	18. 2-3-3
	19. 3-1-1
	20. 3-1-2
	21. 3-1-3
	22. 3-2-1
	23. 3-2-2
	24. 3-2-3
	25. 3-3-1
	26. 3-3-2
	27. 3-3-3

Compare the iterative and the recursive code.

The iterative code appears shorter, but if another setting is added, another loop needs to be added.

In the recursive code, the literal 3 needs to be changed to 4 to add another setting.

Note that the code is very similar to the permute code, but just a little different.

If this functionality were useful in many places, it could be abstracted to a module.

To sort something is to arrange that something into order.

To sort a list is to arrange that list so it is in order.

Slowsort is a simple but slow exchange sorting algorithm based on the definition of sorting. That is, take all permutations of the items in the set or multiset to be sorted. At least one such permutation will be in sorted order. Pick one of those permutations to complete the sort.

Obviously, slowsort is not a very machine efficient sorting algorithm.

5