Permutation Generation

If you do any kind of simulation, you're basing your work on probability theory and probably permutations


July 31, 2007
URL:http://www.drdobbs.com/architecture-and-design/permutation-generation/201200326

Before we dive into the programming issues, a bit of mathematical background is in order. You're probably familiar with the factorial function (n!), which is defined as the product of all numbers between 1 and n, with the special case that 0! = 1. It should be familiar since it is often the first example of a recursive function used in programming textbooks. It is generally presented like this: 

FUNCTION  factorial<n INTEGER> :
     INTEGER;
BEGIN
IF <n=0>
THEN factorial :=1
ELSE factorial :=n * factorial
     < <n - 1> >
END;

This is a terrible waste of computer resources. But because it is one of the shortest examples that does anything even remotely useful, it appears frequently.

A simple FOR loop uses less time and memory: 

FUNCTION factorial< n INTEGER>  :
     INTEGER;
VAR i, fact : INTEGER
BEGIN
fact :=1;
FOR i :=1 TO n
DO fact = fact * n;
factorial := fact
END;

Even this version encounters problems. The factorial function grows quickly, screaming toward the brick wall that confines integers in a computer.

As an alternative, Sterling's formula yields a good estimate of the value of (n!) and can be helpful for larger values of (n). The formula is: 

FUNCTION Sterling< n INTEGER> :
     INTEGER;
     CONST pi = 3.141592653;
     CONST e = 2.718281828;
   BEGIN { Sqrt<> is square root}
               {Power<> is exponent}
     Sterling :=Sqrt(2 * pi * n>  *
                  Power < < n/e>, n>;
END;

Arranging Things

Now we can look at one of the most useful things a factorial can do: calculate permutations and combinations. Imagine that you have a collection of (n) comic books and you want to select a subset of (k) comic books to trade with friends. How many different subsets of size (k) exist? This number is referred to as the combination of (n) objects taken (k) at a time.

Once we have our subsets, how many different ways can we arrange each of them? This number of different arrangements is called the permutation of (n) objects taken (k) at a time.

These two terms are easy to confuse. The combination on your gym locker has an ordering, but the mathematical term combination does not. Maybe someday you will be asked for your gym locker permutation of 36 numbers taken three at a time, but don't hold your breath.

If you think about it for a minute, given (n) marks (letters, numbers, whatever), you have (n!) ways to arrange them. The first position has (n) possible candidates. When we pick one, we are left with (n--1) possible candidates for the second position, and so forth.

How can a programmer put permutation algorithms to practical use? In building brute-force solutions, of course! A computer science professor actually said this in print! When you cannot see an elegant algorithm, beat the problem to death with a big stick. Computer time is cheap.

One of the examples I use in software design courses is a puzzle that involves arranging the digits zero to nine in a grid to find the pattern that gives the best row and column totals according to a set of rules and conditions. Instead of pondering an elegant and sophisticated algorithm, I could simply generate 10! (= 3,628,800) grids and test them overnight.

The order in which permutations are generated can be important. If you want to use them in a particular order but your algorithm does not produce them in that order, you have to write the results to a file and sort it. Since the number of permutations can be quite large, you had better have a big disk and lots of time.

The most commonly used generation order is lexicographic order, which in rough terms means the order in which you would find anagrams in a dictionary (assuming your marks are letters). Lexicographic order has the advantage of working with the results of sorts, binary searches, and other algorithms. Other generation sequences take their names from the algorithms that generate them. At the other extreme is random order.

Two fundamental generating schemes exist. The first generates the permutation of (n) things from the permutation of (n--1) things. This is done by moving the nth mark through all positions in each of the (n--1) permutations. The way it is moved through the positions differs depending on the algorithm used. The second scheme assumes we have a procedure that can generate (k--1)! permutations, where (k*4!n). The (k!) permutations of (k) marks can be found by taking all subsets of (k--1) of the (k) marks, then permuting each of them and placing the leftover mark in the kth position. Start with (k=1) and increase it until (k=n).

The (k!) permutations of (k) marks can be found by taking all subsets of (k--1) of the (k) marks, then permuting each of them and placing the leftover mark in the kth position. Start with (k=1) and increase it until (k=n).

All of the programs given here are recursive because both fundamental generating schemes invite recursive solutions. Much of the early work in programming was spent converting algorithms to nonrecursive form; the early hardware simply did not cope well with recursion. On the current generation of hardware, this is no longer a problem. In fact, recursive algorithms can be the fastest option. Listing One, FikePerm, uses Fike's algorithm because it is one of the fastest known. It demonstrates the first of the two fundamental generating schemes. Note that it begins with a parameter of two and builds up permutations. 

PROGRAM TestFikePerm;
CONST marksize = 5;
VAR
	marks : ARRAY [1..marksize] OF INTEGER;
	ii : INTEGER;
	permcount : INTEGER;
PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write <marks[i],         >;
WriteLn;
permcount := permcount + 1;
End;
PROCEDURE FikePerm <k : INTEGER>;
{Outputs permutations in nonlexicographic order.  This is Fike's algorithm	}
{ with tuning by J.S. Rohl.  The array marks[1..marksizn] is global.  The	}
{ procedure WriteArray is global and displays the results.  This must be               }
{ evoked with FikePerm(2) in the calling procedure.				}
VAR
	dn, dk, temp : INTEGER;
BEGIN
IF <k = marksize>
THEN BEGIN { swap the pair }
	WriteArray;
	temp :=marks[marksize];
	FOR dn := <marksize - 1> DOWNTO 1
	DO BEGIN
		marks[marksize] := marks[dn];
		marks [dn] := temp;
		WriteArray;
		marks[dn] := marks[marksize]
		END;
	marks[marksize] := temp;
	END {of bottom level sequence }
ELSE BEGIN
	FikePerm<k + 1>;
	temp := marks[k];
	FOR dk := <k - 1> DOWNTO 1
	DO BEGIN
		marks[k] := marks[dk];
		marks[dk][ := temp;
		FikePerm<k + 1>;
		marks[dk] := marks[k];
		END; { of loop on dk }
	marks[k] := temp;l
	END { of sequence for other levels }
END; { of FikePerm procedure }
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 0;
WriteLn <  Starting position: >;
WrieLn;
FikePerm <2>; { It always starts with 2 }
WriteLn <  Permcount is   . permcount>;
ReadLn;
END.
Listing One

Listings Two and Three are lexicographic (LexPerm) and nonlexicographic (AllPerm), respectively. The lexicographic program is given because the order it generates can be handy. 

PROGRAM TestLexPerms;
CONST marksize = 5;
VAR
	marks : ARRAY [1..marksize] OF INTEGER;
	ii : INTEGER;
	permcount : INTEGER;
PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write <marks[i],       >;
permcount := permcount + 1;
WriteLn;
END;
PROCEDURE LexPerm <n : INTEGER>;
{ Outputs permutations in lexicographic order.  The array marks is global	}
{ and has n or fewer marks.  The procedure WriteArray () is global and	}
{ displays the results.								}
VAR 
	work : INTEGER:
	mp, hlen, i : INTEGER;
BEGIN
IF <n = 2>
THEN BEGIN { Swap the pair }
	work := marks[1];
	marks[1] := marks[2];
	marks[2] := work;
	WriteArray ;
	END
ELSE BEGIN
	FOR mp := <n - 1> DOWNTO 1
	DO BEGIN
		LexPerm<<n - 1>>;
		hlen := <n - 1> DIV 2;
		FOR i := 1 TO hlen
		DO BEGIN { Another swap }
			work := marks[i];
			marks[i] := marks[n - i];
			marks[n - i] := work
			END;
		work := marks[n]; { More swapping }
		marks[n] := marks[mp];
		marks[mp] := work;
		WriteArray;
		END;
	LexPerm<<n - 1>>
	END;
END
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 1; { The starting position is permutation }
WriteLn <   Starting position:  >;
WriteLn
LexPerm <marksize>;
WriteLn <   PermCount is   , permcount>;
ReadLn;
END.
Listing Two

The nonlexicographic algorithm runs faster and demonstrates the second fundamental generating scheme. It starts with a parameter of the size of the array of marks two, and then recurses down to create permutations. 

PROGRAM TestAllPerms;
CONST marksize = 5;
VAR
	marks : ARRAY [1..marksize] of INTEGER;
	ii : INTEGER;
	permcount : INTEGER;
PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write <marks[i],     >;
WriteLn;
permcount := permcount + 1;
END;
PROCEDURE AllPerm (n : INTEGER);
{ Outputs permutations in nonlexicographic order. The array marks is	}
{ global and has n or few marks.  The procedure WriteArray is global and	}
{ displays the results.								}
VAR
	work : INTEGER;
	mp, swaptemp : INTEGER;
BEGIN
IF <n = 2>
THEN BEGIN { Swap the pair }
	work := marks[1];
	marks[1] := marks[2];
	marks[2] := work;
	WriteArray;
	END
ELSE BEGIN
	FOR mp := <n - 1> DOWNTO 1
	DO BEGIN
		ALLPerm<< n - 1>>;
		IF <odd<n>> 
		THEN swaptemp := 1
		ELSE swaptemp := mp;
		work := marks[n];
		marks[n] := marks[swaptemp};
		marks[swaptemp} := work;
		WriteArray;
	AllPerm< n-1 >;
	END;
END;
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii
permcount :=1;
WriteLn < Starting position;   >;
WriteLn;
Allperm < marksize>;
WriteLn < Perm count is  , permcount>;
ReadLn;
END.

VAR
	marks : ARRAY [1..marksize] of INTEGER;
	ii : INTEGER;
	permcount : INTEGER;
PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write < marks[i], >;
WriteLn;
permcount := permcount + 1;
END;
PROCEDURE AllPerm < n : INTEGER>;
{ Outputs permutations in nonlexicographic order. The array marks is	}
{ global and has n or few marks.  The procedure WriteArray is global and	}
{ displays the results.								}
VAR
	work : INTEGER;
	mp, swaptemp : INTEGER;
BEGIN
IF (n = 2)
THEN BEGIN { Swap the pair }
	work := marks[1];
	marks[1] := marks[2];
	marks[2] := work;
	WriteArray;
	END
ELSE BEGIN
	FOR mp := <n - 1>  DOWNTO 1
	DO BEGIN
		ALLPerm<n - 1>;
		IF <odd<n> > 
		THEN swaptemp := 1
		ELSE swaptemp := mp;
		work := marks[n];
		marks[n] := marks[swaptemp};
		marks[swaptemp} := work;
		WriteArray;
	AllPerm<n-1>;
	END;
END;
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii
permcount :=1;
WriteLn <   Starting position; >;
WriteLn;
Allperm <marksize);
WriteLn <  Perm count is , permcount>;
ReadLn;
END.
Listing Three

The references given here are not intended to be comprehensive, but they are a good place to start. Many of the algorithms were originally written in ALGOL, FORTRAN 66, or PL/I. I have translated them into Pascal for readability. You should have no trouble moving them to any other block-structured language such as C, Ada, or Modula-2.

References

Fike, C.T. Generating of Permutations by Transposition, The Computer Journal 18: 21-22, 1975.

Iyer, Mani G. Permutation Generation Using Matrices, Dr. Dobb's Journal.

Ord-Smith, R.J. Generating of Permutation Sequences: Part 1, The Computer Journal 13: 152-155, 1970.

Ord-Smith, R.J. Generating of Permutation Sequences: Part 2, The Computer Journal 14: 136-139, 1971.

Ord-Smith, R.J. Generations of Permutations in Lexicographic Order, Communications of the ACM 11: 117, 1968.

Rohl, J.S. Generating Permutations by Choosing, The Computer Journal 21: 302-305, 1978.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.