Algorithm for generating permutations for the rubik cube

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