Tag Archives: permutations

Producing permutations, part two

Posted on by
10

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 →

Producing permutations, part one

Posted on by
20

One of my more popular articles from 2010 was my post on how to produce the Cartesian product of arbitrarily many sequences of the same type. That is, we have some sequences, say {10, 20, 30} and {200, 300, 400}, and we wish to produce the sequence of all possible combinations:

{ 
  {10, 200}, {10, 300}, {10, 400}, 
  {20, 200}, {20, 300}, {20, 400},
  {30, 200}, {30, 300}, {30, 400} 
}

A related question that I did not answer was “how do you produce all possible permutations of a sequence?” That’s the question we’re going to explore for the next few episodes.

Continue reading →