Generating Permutations

Applications of Arrays

Permutations

• a permutation of n is a one-to-one and onto function from {1,2,…,n} to itself

• permutation p is represented by writing values of p(1) p(2) …… p(n) in sequence

• 3 1 6 5 4 2 is a permutation of 6

• represented naturally using an array

• arise in many contexts

• how many different permutations of n?

Traveling Salesman Problem

• input is a set of n cities and distance between every pair of cities

• output is a tour of the cities visiting each city exactly once

• many tours are possible – how many?

• find one for which total distance traveled is minimized

• no efficient method known for this!

Generating Permutations

• every possible tour represented by a permutation of the cities

• cities listed in the order they are visited

• suggests a simple algorithm

– list all permutations

– find distance traveled for each

– take the minimum of these

• very time consuming algorithm

Lexicographic Order

• any listing of permutations defines an ordering of the permutations

• list using some natural order

• lexicographic order

• permutation p is listed before q iff there is an i such that

– p(j) = q(j) for 1 <= j < i, and

– p(i) < q(i)

• similar to ordering for character strings

• 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1

• first permutation is the identity 1 2 ….. n

• given a permutation how to generate next?

• intuitive idea

– keep initial part the same as far as possible

– increase the next number by minimum possible

– remaining numbers in increasing order

Example

• 6 3 5 1 9 2 8 7 4 is a permutation of 9

• what is the next in lexicographic order?

• if 6 3 5 1 9 2 is fixed next number cannot be increased

• a number can be increased only if it has a larger number to its right

• 6 3 5 1 9 is fixed

• increase 2 to 4

• arrange remaining numbers as 2 7 8

Program

a(1:n) = (/(i,i=1,n)/)

do

print *, a(1:n)

do j = n-1, 1, -1

if (a(j) < a(j+1)) exit

end do

if ( j == 0) exit ! loop variable used outside

do k = n, j+1, -1

if (a(k) > a(j)) exit

end do

! a(j) is the rightmost number having a number greater

! than itself to its right

! a(k) is the smallest number > a(j) to its right

! exchange a(k) and a(j) and reverse a(j+1:n)

temp = a(k)

a(k) = a(j)

a(j) = temp

a(j+1:n) = a(n:j+1:-1) ! section in reverse order

end do

Loop Invariant

• at beginning of i^th iteration, a(1:n) contains i^th permutation in lexicographic order

• p be permutation at start of i^th iteration

• q be permutation at start of (i+1)^th iteration

• show that there is no r such that p < r < q in lexicographic order

• suppose there is an r, p <= r <= q

• p(i) = q(i), implies p(i) = r(i) for 1 <= i < j

• if p(j) < r(j) then r(j) = q(j), since q(j) is the smallest number > p(j) to its right

• thus, either r(j) = p(j) or r(j) = q(j)

• p(j+1:n) is a decreasing sequence

• q(j+1:n) is an increasing sequence

• p(j) = r(j) and p <= r implies p = r

• r(j) = q(j) and r <= q implies r = q

• thus either p = r or r = q

Rank and Unrank Functions

• rank of a permutation is the number of permutations < than it in lexicographic order

• consider a permutation p(1) p(2)……p(n)

• if q(1) < p(1), q < p

• there are (p(1)-1)(n-1)! such permutations

• if q(1) = p(1) and q(2) < p(2), q < p

• there are either (p(2)-1)(n-2)! or

(p(2)-2))(n-2)! permutations of this type

Rank Function

• in general, for permutation p(1) ……. p(n)

• rank = d(1)(n-1)! + d(2)(n-2)! + ……

– d(i) is the number of p(j), j > i, p(j) < p(i)

• consider the permutation n n-1 n-2 …… 1

• rank = n!-1

• d(i) = i-1

• n!-1 = (n-1)(n-1)!+(n-2)(n-2)!+…….1(1!)

• ranking functions used to prove identities

Computing the Rank

rank = 0

fact = 1

do i = n-1, 1, -1

fact = fact*(n-i)

d = count(a(i+1:n) < a(i))

rank = rank + fact*d

end do

! count is an intrinsic function which counts number of

! true values in a logical array

Unrank Function

• given a number r, find the permutation of n whose rank is r

• 0 <= r <= n!-1

• any such r can be written uniquely as

• r = d(1)(n-1)! + d(2)(n-2)!+ ……+d(n).0! such that 0 <= d(i) <= n-i

• d(1) = r/(n-1)!

• remaining terms have sum at most (n-1)!-1

Computing Unrank Function

fact = 1

do i = 2, n-1

fact = fact*i

end do

do i = 1, n-1 ! compute d values first

d(i) = r/fact ! integer division

r = r – fact*d(i)

fact = fact/(n-i)

end do

d(n) = 0

do i = n, 1, -1

a(i) = d(i) + 1

where(a(i+1:n) >= a(i)) a(i+1:n) = a(i+1:n)+1

end do

! computes the permutation iteratively

! a(i:n) is a permutation p’ of n-i+1 such that a(j) has

! exactly d(j) numbers < than it to its right, i<=j<=n

! a(1:n) is the required permutation

! separate d array is not required, use a itself

Other Listings

• other orders of listing may be more useful

• listing by minimal change

– next permutation obtained by swapping two consecutive numbers

– useful for computing distances in TSP

• more efficient rank and unrank functions

– useful for generating random permutations

• similar listings possible for other objects

Summary

• permutations are basic combinatorial objects

• listing of all permutations is useful

• listing in lexicographic order

• rank and unrank functions

• useful for generating random permutations

• other orders for listing possible

• other combinatorial objects may be similarly listed