Producing permutations, part three

Last time on FAIC I described an algorithm for producing every permutation of size n such that any two successive permutations differ only by swapping two adjacent items. Today let’s actually write some code to implement this algorithm.

Continue reading

Producing permutations, part two

Last time on FAIC I described a simple recursive algorithm for generating all permutations of the first n whole numbers: if you have all the permutations of the first n-1 whole numbers, you just insert the nth whole number at each of n positions in each permutation. So if we had all the permutations of {0, 1, 2} and we wanted all the permutations of {0, 1, 2, 3}, we just start listing permutations of {0, 1, 2} with the 3 stuck in each of 4 places:

  {3, 0, 1, 2},  
  {0, 3, 1, 2},
  {0, 1, 3, 2},
  {0, 1, 2, 3}, That does it for {0, 1, 2}...
  {3, 0, 2, 1}, 
  {0, 3, 2, 1},
  {0, 2, 3, 1}, 
  {0, 2, 1, 3}, That does it for {0, 2, 1}...

and continue to get the 24 permutations.

Continue reading