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 = (p _{1}, p_{2}, ..., p_{n})*. In order to obtain the next permutation, we must first find the largest index

*i*so that

*P*. Then, the element,

_{i}<P_{i + 1}*P*will be swapped with the smallest of the elements after

_{i}*P*, but not larger than

_{i}*P*. Finally, the last

_{i}*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) && (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 < (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 < 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!

2007-10-15 at 4:04

thanks!!

2007-10-16 at 12:07

Your code doesn’t work. As is, it prints “1 2 2” over and over again. You might want to download it and give it a look. What does that “swap” typedef do? It looks like it just adds b to a and then subtracts 1…

2007-10-16 at 18:13

Checked code. Works for me:

$ gcc lp.c -o lp

$ ./lp

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

SWAP swaps the values of a and b. It relies on the way C interprets variables. Step by step:

1. b takes the value of a

2. a + b – (b = a) is now equivalent to a + b – a which is b

3. it attributes the value of the expression (now b) to a

It’s a nasty trick, slower then the normal method, but it’s faster to write.

2007-10-28 at 4:41

[…] here This entry was posted on Monday, October 8th, 2007 at 9:19 am and is filed under computer […]

2008-03-31 at 3:18

Thank you for the algorithm. I appreciate it.

2008-05-18 at 3:47

Well, I had to translate this to ActionScript, but it was exactly what I was looking for. Been working on this for 2-3 days. your solution is a cool little routine with tons of potential applications. I am using it for a crossword puzzle creator. You type in (n) words and the routine will solve every possible combination of words that can be placed on the grid. I am using a simple recursive maze solving routine to check each character in the picked word against the words on the grid — I just realized that I need to multiply the factorial by two since the words can either go down or across. Anyway, it’s working pretty good so far and this is the last big piece of the problem, so thanks again.

2009-08-12 at 22:00

is there any chance i can get the ActionScript a code ? Thanks

2008-10-31 at 21:01

The SWAP() macro defined here might not work on all compilers, especially if the compiler decides it wants to evalute (b = a) first (and there’s nothing that stops it from doing so; it’s valid C).

a = a+b – (b=a)

which becomes

a = a+a – (a)

which is just a. So you end up with a=a,b=a instead of a=b,b=a!

2009-02-17 at 22:23

Поставьте Akismet

2009-03-10 at 3:18

I’m challenging all of you with the reversed problem: Please give a simple algorithm / formula to compute the lexicographic number lex(p) of a given permutation p. (An obvious but long and memory-consuming way to compute lex(p) would be first to build the huge list of all n! permutations for a given n, and then to search for the given permutation in the list.)

Examples of lex(p):

lex(1234) = 1

lex(1243) = 2

lex(1324) = 3

lex(1342) = 4

…

lex(4321) = 24

2009-10-05 at 4:42

Convert the permutation into its Factoradic then it’s trivial to get its lexicographic index.

2009-06-05 at 14:09

10q most! btw, is there any chance i can get a code generating lexicographically ordered codewords constant weight code of length n and weight w?

2010-05-29 at 3:51

How do you go 2 3 1 to 3 1 2? According to your algorithm, Pi is 2 at index 0, it will be swapped with 1 at index 2 this results in 1 3 2. And after reversing everything after index 0, you end up with 1 2 3, back to the beginning.

In fact, if you say, “smallest of the elements after Pi, but not larger than Pi” how do you even go from 1 3 2 to 2 1 3, because again Pi is 1 at index 0, but it can’t be swapped with anything else because are all larger than 1

2010-05-29 at 4:38

Actually I realised, it should say “smallest of the elements after Pi, at the highest index, that IS larger than Pi”

In this case you start with 2 3 1, Pi is 2 at index 0, but you don’t replace it with 1 because it is smaller than 2. You replace it instead with 3. This gives you 3 2 1. Now you reverse everything after index 0 to give you 3 1 2.

Reference : Donald Knuth’s Algorithm L

2010-06-19 at 0:31

what if i wish to get the i-th lexicographic permutation, without going through all of the permutations till we get to it? is it possible to do so in an efficient way?

2011-03-13 at 17:13

[…] Problem Statement : Given a string of characters generate all permutations of string in lexicographic order. Solution: This algorithm has been taken from https://compprog.wordpress.com/2007/10/08/generating-permutations-2/ […]

2011-10-23 at 4:00

I do not have the C++ in my computer now. So, please help with a problem. Given A = (7 3 1 6 9 5 2 4 8) B = (7 3 1 4 5 8 6 2 9)

(a) which permutation immediatly follows A in the lexicographic order. which precedes B?

(b) How many permutations lie between A and B in the lexicographic order?

2011-11-05 at 17:07

promotional gifts…[…]Generating Permutations: 2 « Computer programming[…]…

2012-02-20 at 12:56

do

{

if (k < n – 1)

{

j = k + 1;

arraytoReturn[c] = concatArray(val);

temp = val[k];

val[k] = val[j];

val[j] = temp;

k++;

c++;

}

else

{

k = 0;

}

} while (c < length);

/*I am trying this code but it works for 123 but not working for 1234 or more. what should i do*/

2012-02-20 at 12:59

length is the factorial of array length and c, k and j are initialized by 0. val is the array for which permutations are to be found.

2012-05-02 at 3:43

Very helpful! Could you please post more algorithms for generating permutations?

2012-08-22 at 12:38

A safer swap would be

SWAP(a,b) ( a ^= b, b ^= a, a ^= b )