# Algorithm for generating permutations for the rubik cube

hi,

let's say I want to distribute permutation checking over say 10 computers.
so if there are a total of n permutations the first machine will check n/10.
the second will check from n/10 to 2n/10
third will check from 2n/10 to 3n/10.
and so forth.
the algorithm that generates permtuations needs to generate the ith permutation in O(1)
so that I can efficiently start each machine's work.
what algos for generating permtuations do you know that can do this ?

thanks

## Comment viewing options

### It is relatively straightforw

It is relatively straightforward to map any permutation of m items uniquely to a number in the range [0, m!-1]. This is essentially done via the Factorial Number System (Wikipedia). Similarly, you can map piece orientations to a range of integers. By combining these, you can map each puzzle position to a unique number on the range [0, N-1] where N is the total number of reachable positions. This map is invertible, so you can also reproduce a puzzle position from any of these numbers (in polynomial time w.r.t. the number of pieces).

Take a look at my Computer Puzzling page, and in particular to my page about Indexing.

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

### Steinhaus Johnson Trotter

that's interesting, I've just read the page you gave me.
I have one more question, is there any indexing for permutations generated by Steinhaus-Johnson-Trotter algorithm ? in the order that said algorithm computes them of course ?

### Plain Changes

I never heard that name for that algorithm before. It has been known and used since the 17th century by bell-ringers to generate all sequences of any number of bells, and is usually called Plain Changes.

Sure there is a way to convert any permutation on a list in that order to its index number on the list and back again. I don't really see any reason why you would particularly need that order though, as normally any order will do (but you often do want the identity permutation to have index zero).

Here is some Java code I just put together to show this conversion. I found it easiest to use recursion.

```public class Test{
public static void main(String[] args){
int[] perm = new int[4];
for( int idx = 0; idx<24; idx++ ){
// test idx2perm
idx2perm(idx, perm, 4);
// display perm
for( int j=0; j<4; j++) System.out.print(perm[j]);
// test perm2idx
int idx2 = perm2idx( perm, 4 );
System.out.println( " "+idx2);
}
}

private static void idx2perm( int idx, int[] output, int length ){
// base case
if( length == 0 ) return;
// extract info for largest item of permutation
int idxOfLargest = idx % length;
int idxOfSubPerm = (idx - idxOfLargest ) / length;
// build up sub-permutation, excludes largest item.
idx2perm( idxOfSubPerm, output, length-1);
// get position at which to insert largest item
int posOfLargest = idxOfLargest;
if( idxOfSubPerm%2 == 0 ) posOfLargest = length -1 - idxOfLargest;
// insert largest item at correct position
for( int i=length-1; i>posOfLargest; i--){
output[i] = output[i-1];
}
output[posOfLargest] = length;
}

private static int perm2idx( int[] perm, int largest ){
// base case
if( largest == 0 ) return 0;
// extract info for largest item of permutation. Ignore all larger items
int posOfLargest = 0;
for( int i=0; i<perm.length; i++ ){
if( perm[i]<largest ) ++posOfLargest;
else if( perm[i]==largest ) break;
}
// get index of sub-permutation, excluding largest items.
int idxOfSubPerm = perm2idx(perm, largest-1);
// Get index of permutation
int idx = idxOfSubPerm * largest;
if( idxOfSubPerm%2==0 ) idx += largest -1 - posOfLargest;
else idx += posOfLargest;
return idx;
}
}
```

Here's the output:

```1234 0
1243 1
1423 2
4123 3
4132 4
1432 5
1342 6
1324 7
3124 8
3142 9
3412 10
4312 11
4321 12
3421 13
3241 14
3214 15
2314 16
2341 17
2431 18
4231 19
4213 20
2413 21
2143 22
2134 23```

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

### I have one more question, if

I have one more question, if you know of some formal development of the factorial base and a proof of the algorithm you gave above please ?
I know they are true, they're pretty intuitive but still I would like to read a proof if possible

thank you

### TAOCP

I don't have a proof of the correctness of the code I gave, but as you say it is pretty intuitive. Especially if you think of the Plain Changes permutation generation slightly differently from the links you gave. Instead of each item in the permutation having a direction, and generating the permutations one by one, imagine you already have a list of all permutations of n-1 items, and want to use that to generate a list of all permutations of n items. I explain it a little on my Hamilton Paths page, under the section "Bell-ringing".
http://www.jaapsch.net/puzzles/hamilton.htm
With that image in mind, the recursive definition of how to calculate the index number from the permutation (and vice versa) is straightforward.

The only book(s) I know that contain this material is Donald E Knuth's The Art of Computer Programming, which every mathematician programmer ought to have.

In TAOCP Volume 2 (Seminumerical Algorithms, section 3.3.2, Random numbers test F) Knuth gives a very simple algorithm for converting a permutation into an index number, but using a different ordering. I should actually start using that version myself when the particular order of the permutations does not matter.

In TAOCP Volume 3 (Sorting and Searching, section 5.1.1, Inversions), he shows how you can convert a permutation into an inversion table, and vice versa. An inversion table is just the list of digits of the factorial number representation of an index number. The ordering of the permutations used here is lexical order.

In TAOCP Volume 4, Fascicle 2 (Generating All Tuples and Permutations, section 7.2.1.2, Adjacent interchanges), he notes that incrementing/decrementing one number in the inversion table of a permutation is the same as a transposition, and therefore that by applying a Gray code algorithm to run through all inversion tables you generate all permutations using only single transpositions each time. This results in the Plain Changes algorithm.

He does not give the algorithms I coded up above, though earlier on in that book (section 7.2.1.1, Nonbinary Gray Codes) he shows how to recursively convert Gary codes to index numbers, and vice versa. That is about a fixed base number system instead of the factorial number system, but the same method applies.

So it is all there, but rather scattered. This is because generally the order of permutations doesn't matter, and when it does then you are usually generating them all anyway and don't need translate an index number to a permutation.

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

### thank you Jaap, this is exact

thank you Jaap, this is exactly what I needed, I will mention you when I release this code