Last time, we defined what permutation is and gave a few basic properties.

In a few minutes we’ll see another algorithm for generating them, but first a little theory.

Lexicographical order is defined by Wikipedia as:

In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets.

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as
(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

The result is a partial order. If A and B are totally ordered, then the result is a total order also.

More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

Mathworld adds the following regarding permutations and sets:

When applied to permutations, lexicographic order is increasing numerical order (or equivalently, alphabetic order for lists of symbols; Skiena 1990, p. 4). For example, the permutations of {1,2,3} in lexicographic order are 123, 132, 213, 231, 312, and 321.

When applied to subsets, two subsets are ordered by their smallest elements (Skiena 1990, p. 44). For example, the subsets of {1,2,3} in lexicographic order are {}, {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}.

An easy way to determine if a set is lexicographically after another is to interpret them as numbers in base n, where n is the largest element the set contains. So, (2, 1, 3) is after (1, 2, 3) because 213 < 123. Note: You may also choose n as any number greater than the largest element of the set. This is particularly convenient as most would rather use numbers in base 10 and not base 3.

Ok, but what does this have to do with permutations? Well, generating permutations in any order isn’t enough; you must generate them in lexicographic order.

Now, if you run last times’ algorithm, you find that, for n = 3, it prints:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Now, 123 < 132 < 213 < 231 < 312 < 321. So, the permutations are in lexicographic order!

The worst algorithm for any problem is usually called naive, but a more adequate adjective for the last algorithm would be retarded. It’s the slowest one I can think of, but it’s extraordinarily easy to explain.

This algorithm is slightly faster (about twice as fast) than the last one. It’s quite complex and harder to understand. It does the same thing as the last one, but where the naive algorithm just generated all possible sets, this one generates only valid permutations.

Here it is:

P1. Given n, we start with the first imaginable permutation p = (1, 2, ..., n) from the lexicographic point of view.

P2. Print the the permutation p or use it for something else.

P3. Let's say we have already build the permutation p = (p1, p2, ..., pn). In order to obtain the next permutation, we must first find the largest index i so that Pi<Pi + 1. Then, the element, Pi will be swapped with the smallest of the elements after Pi, but not larger than Pi. Finally, the last n - i elements will be reversed so that they appear in ascending order. Then, jump to P2.

That’s it for the algorithm, here’s the code in C (lexicoPerm.c):

#include <stdio.h>

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

	for (i = 0; i < n; i++)
		printf("%d ", v[i]);
	printf("\\n");
}

/*!
	This just swaps the values of a and b

	i.e if a = 1 and b = 2, after

		SWAP(a, b);

	a = 2 and b = 1
*/
#define SWAP(a, b) a = a + b - (b = a)

/*!
	Generates the next permutation of the vector v of length n.

	@return 1, if there are no more permutations to be generated

	@return 0, otherwise
*/
int next(int v[], int n) {
	/* P2 */
	/* Find the largest i */
	int i = n - 2;
	while ((i >= 0) &amp;&amp; (v[i] > v[i + 1]))
		--i;

	/* If i is smaller than 0, then there are no more permutations. */
	if (i < 0)
		return 1;

	/* Find the largest element after vi but not larger than vi */
	int k = n - 1;
	while (v[i] > v[k])
		--k;
	SWAP(v[i], v[k]);

	/* Swap the last n - i elements. */
	int j;
	k = 0;
	for (j = i + 1; j &lt; (n + i) / 2 + 1; ++j, ++k)
		SWAP(v[j], v[n - k - 1]);

	return 0;
}

int main(int argc, char *argv[]) {
	int v[128];
	int n = 3;

	/* The initial permutation is 1 2 3 ...*/
	/* P1 */
	int i;
	for (i = 0; i &lt; n; ++i)
		v[i] = i + 1;
	printv(v, n);

	int done = 1;
	do {
		if (!(done = next(v, n)))
			printv(v, n); /* P3 */
	} while (!done);

	return 0;
}



The code is commented and it does nothing but implement the algorithm. Have fun!

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.

Follow

Get every new post delivered to your Inbox.

Join 122 other followers