Tag Archives: recursion

Producing permutations, part four

Posted on by
8

Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.

Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to n!-1. What I’d like is an algorithm which given size, the number of items in the permutation, and index, an integer between zero and size!-1, gives back the indexth permutation of length size, without having to calculate all of them.

Continue reading →

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 →