Last time on FAIC I showed how you could produce the `m`

th permutation of `n`

elements, where `m`

is a number between zero and `n!-1`

that chooses from the `n!`

possible permutations. There’s a very interesting way to represent numbers that are always less than `n!`

for a given `n`

that I thought I might talk about today.

# Tag Archives: permutations

# Producing permutations, part four

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 `index`

th permutation of length `size`

, *without *having to calculate all of them.

# 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.

# 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.

# Producing permutations, part one

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.