A 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 nth element. How many posibilities does this give us? So, n ways to choose the 1st 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) &amp;&amp; (v[i] > n)) {
        v[i] = 1;
        i--;
        if(i >= 0)
            v[i]++;
    }

    if (i &lt; 0)
        return 0;
    return 1;
}

void printv(int v[], int n) {
    int i;

    for (i = 0; i &lt; 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 &lt; n; i++)
        for (j = i + 1; j &lt; 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 &lt;= 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.

Advertisements