2007-10-05

## Generating Permutations: 1

Posted by scvalexA *permutation of n objects* is an arrangement of n distinct objects.

Wikipedia gives a slightly more detailed definition:

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. (For cases wherein the ordering of elements is irrelevant, compare combination and set.) For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: “4, 5, 6, 1, 2, 3″.

And Mathworld gives the standard mathematical definition:

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.

Permutations are crucial to studying the behaviour of many algorithms and we’ll find a lot of intresting things about them.

For starters, what are the permutations of {1, 2, 3}? The definition says a permutation is a rearrangement of the list’s elements. So, the permutations (plural) are *all the possible rearrangements of the list’s elements*. This gives us six permutations:

123, 132, 213, 231, 312, 321

For convenience, we’ll only work with sets like {1, 2, 3, …, n}. In computer science, the permutations of this set is called *the permutations of n*. In mathematics *the permutations of n* means the **number** of permutations of the given set.

How many permutations of n are there? This is easily solved, to create a permutation one element at a time: there are *n* ways in which to choose the first element; then, there are *n - 1* ways in which to choose the second element, so that no element repeats itself; then, there are *n - 2* ways to choose the third element; …; finally, there is **only one way** to choose the n^{th} element. How many posibilities does this give us? So, *n* ways to choose the 1^{st} element, *n(n - 1)* ways for the first 2 elements, *n(n - 1)(n - 2)* for the first 3 elements, …, *n(n - 1)(n - 2)…(n - k + 1)* for the first k elements, …, *n(n - 1)(n - 2)…(1)* ways for all the n elements.

Now we can calculate that there are *1 * 2 * 3 = 6* permutations of 3. And … that’s right! By the way, the value *1 * 2 * 3 * … * n* is usually written as *n!* and is called **n factorial**.

Great. We know what a permutation is. We know how many there are for a given set. But how do we generate them?

There are quite a few (more like dozens) methods, and I’ll describe a few here. The simplest one I can think of is this:

Let’s say you want to generate **all** the permutations of 3. So, you want to generate the permutations of the set {1, 2, 3}. We’ll generate the list:

123, 131, 132, 133,

211, 212, 213, 221, 222, 223, 231, 232, 233

311, 312, 313, 321, 322, 323, 331, 332, 333

That’s all the numbers you can make of length 3 using only the digits 1, 2 and 3. I start from *123* and not from *111* because there’s no permutation between *111* and *123*.

Then we’ll filter the results using the rule: “A valid permutation **cannot** contain the **same** digit **twice**“.

Then we’ll print out what’s left.

Here’s the code in C (naiveperm.c):

#include <stdio.h> /*! Generates the next try. If v is 1 2 1 2, after calls to next(v, 4); v will be 1 2 1 3 1 2 1 4 1 2 2 1 1 2 2 2 @return 0, if there are no more valid tries @return 1, otherwise */ int next(int v[], int n) { int i = n - 1; v[i] = v[i] + 1; while ((i >= 0) && (v[i] > n)) { v[i] = 1; i--; if(i >= 0) v[i]++; } if (i < 0) return 0; return 1; } void printv(int v[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", v[i]); printf("\\n"); } /*! @return 1, if v is a valid permutation (no digits repeat) @return 0, otherwise */ int is_perm(int v[], int n) { int i, j; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (v[i] == v[j]) return 0; return 1; } int main(int argc, char *argv[]) { int v[128]; int n = 8; /* The initial permutation is 1 2 3 ...*/ int i; for(i = 0; i <= n; i++) v[i] = i + 1; while (next(v,n)) if (is_perm(v,n)) printv(v,n); return 0; }

The code’s commented and it’s fairly simple, so there shouldn’t be any problems understanding it. Of course, I’m open to suggestions.

The next article in this series is Generating permutations: 2.