# Algorithm for generating permutations for the rubik cube

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

### Steinhaus Johnson Trotter

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 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/

## It is relatively straightforw

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/