Computer Science 101

with:  Erik Oosterwal

Search for specific programs or algorithms:
Custom Search




All Permutations Routine


The following describes a method for rotating cells in a one dimensional array so that all possible permutations are visited one time with no repeats.

For small arrays (2-4 cells) it's a rather trivial process, but as the number of cells goes up linearly, the number of possible permutations goes up factorially.

1! (1 factorial) = 1
2! = 2
3! = 6
4! = 24
5! = 120
10! = 3,628,800
100! = 9.33262 e157
200! = 7.88658 e374

This routine is useful for computing permutations using a "brute force" method. Programs such as password crackers use a similar brute force method, but instead of using a given number of elements to rearrange, each character of a password can be 1 of alphanumeric characters and sometimes special characters. Each position can have any character so repeated characters within a password string are quite common. The all permutations routine works for combinations where repeats are not allowed. The algorithm is given later, here is what's going on in the routine:

For an array of 4 elements (1, 2, 3, 4) there are 24 possible permutations:
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
2, 1, 3, 4
2, 1, 4, 3
2, 3, 1, 4
2, 3, 4, 1
2, 4, 1, 3
2, 4, 3, 1
3, 1, 2, 4
3, 1, 4, 2
3, 2, 1, 4
3, 2, 4, 1
3, 4, 1, 2
3, 4, 2, 1
4, 1, 2, 3
4, 1, 3, 2
4, 2, 1, 3
4, 2, 3, 1
4, 3, 1, 2
4, 3, 2, 1



If the above list of permutations is sorted correctly, a pattern can be seen. In the routine a separate array is used to keep track of the repeating pattern. In the following list of the same permutations the pattern array is shown next to the pattern. The minimum size of the tracking array is 1 less than the dimension of the array being manipulated. For our list, we use a tracking array of 3 elements.

             0, 0, 0 
1, 2, 3, 4 
^--^         1, 0, 0 
2, 1, 3, 4 
^-----^      0, 1, 0 
3, 1, 2, 4 
^--^         1, 1, 0 
1, 3, 2, 4 
^-----^      0, 2, 0 
2, 3, 1, 4 
^--^         1, 2, 0 
3, 2, 1, 4 
^--------^   0, 0, 1 
4, 1, 2, 3 
^--^         1, 0, 1 
1, 4, 2, 3 
^-----^      0, 1, 1 
2, 4, 1, 3 
^--^         1, 1, 1 
4, 2, 1, 3 
^-----^      0, 2, 1 
1, 2, 4, 3 
^--^         1, 2, 1 
2, 1, 4, 3 
^--------^   0, 0, 2 
3, 4, 1, 2
.
.
.


It's important to note that during the "swapping" steps that the elements of the array are not simply being swapped, but the entire subarray is being mirrored. This can be seen when the third column of the tracking array changes.



/* Written By Erik Oosterwal */

Dim DataArray(N) 
Dim TrackingArray(N-1) 

Set DataArray=[1, 2, 3, 4, 5,... N] 
Set TrackingArray=[0, 0, 0, ... N-1] 

Repeat(
	If TrackingArray(1) < 1 Then( 
		Mirror DataArray(1 - 2) 
		Increment TrackingArray(1) 
		) 
	Else If TrackingArray(2) < 2 Then( 
		Mirror DataArray(1 - 3) 
		Increment TrackingArray(2)
		Reset TrackingArray(1) 
		) 
	Else If TrackingArray(3) < 3 Then( 
		Mirror DataArray(1 - 4) 
		Increment TrackingArray(3) 
		Reset TrackingArray(1, 2) 
		) 
	Else If TrackingArray(4) < 4 Then( 
		Mirror DataArray(1 - 5) 
		Increment TrackingArray(4)
		Reset TrackingArray(1, 2, 3) 
		) 
	Else... 
		.
		.
		. 

	Else Stop 
	)



There is a serious drawback to the routine given above in that it requires a separate "Else If" clause for each element in TrackingArray. It's not bad for a small array like our example, but for an array of 100 elements it becomes quite involved. The following routine is a translation of the same algorithm as I encoded it in "G", a proprietary programming language sometimes called LabVIEW:



AllPermutations(DataArray(), TrackingArray())( 

	/* Written by Erik Oosterwal */

	i=0 

	While(TrackingArray(i)== i+1)( 
		i++ 
		) 

	Mirror(DataArray(0), i+2) 

	for(j=0, j<i+1, j++)(
		TrackingArray(j-1)=0 
		) 

	TrackingArray(i)++ 
	return(DataArray(), TrackingArray())
	)


Some things to note about this implementation:

1. DataArray and TrackingArray are initialized in the calling routine.
2. The second parameter in the "Mirror" statement is the number elements to be mirrored.
3. Because of the way the "G" program handles For-Next loops, it required the indexing of TrackingArray to start at -1. For your implementation of the routine adjust the indexing to suit your needs.

allcombinations.vi





Discuss computer algorithms and other computer science topics at the Computer Algorithms blog page.

All code and original algorithms are © Erik Oosterwal - 1987-2008
Computer Science 101

Dressing for Success

1