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.
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.
Fabulous adventures in coding 