6.6 Generating Permutations and Combinations

Question 1

Generating the Next Permutation in Lexicographic Order.

Theory only: not generation process in English, like pre requisites.

Answer 1

Any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3, … , n}.We can list the permutations of any set of n elements by generating the permutations of the n
smallest positive integers and then replacing these integers with the corresponding elements.
Many different algorithms have been developed to generate the n! permutations of this set.

This is based on lexicographic ordering of the
set of permutations of {1, 2, 3, … , n}.
In this ordering, the permutation a1a2 ⋯ an precedes the
permutation of b1b2 ⋯ bn, if for some k, with 1 ≤ k ≤ n, a1 = b1, a2 = b2, … , ak−1 = bk−1, and
ak < bk.

Question 2

Generating the Next Permutation in Lexicographic Order.

Generation process theory not genralised, but process details and jist.

Answer 2

An algorithm for generating the permutations of {1, 2, … , n} can be based on a procedure that constructs the next permutation in lexicographic order following a given permutation
a1a2 ⋯ an.

First, suppose that an−1 < an. Interchange an−1
and an to obtain a larger permutation. No other permutation is both larger than the original permutation and smaller than the permutation obtained by interchanging an−1 and an.
if an−1 > an then larger permutatn can’t be obtained by interchanging them.

If an−2 < an−1, then the last three integers in the
permutation can be rearranged to obtain the next largest permutation. Put the smaller of the two
integers an−1 and an that is greater than an−2 in position n − 2. Then, place the remaining integer
and an−2 into the last two positions in increasing order.

if an−2 > an−1 (and an−1 > an) then again permuting last 3 ints won’t give a larger permutatn.

Question 3

Generating the Next Permutation in Lexicographic Order.

Generalized :

Answer 3

A general method can be described for producing the next larger permutation in increasing order
following a given permutation a1a2 ⋯ an. First, find the integers aj and aj+1 with aj < aj+1 and
aj+1 > aj+2 > ⋯ > an,
that is, the last pair of adjacent integers in the permutation where the first integer in the pair
is smaller than the second.

Then, the next larger permutation in lexicographic order is obtained by putting in the jth position the least integer among aj+1, aj+2, … , and an that is greater
than aj and listing in increasing order the rest of the integers aj
, aj+1, … , an in positions j + 1 to
n.

It is easy to see that there is no other permutation larger than the permutation a1a2 ⋯ an but
smaller than the new permutation produced. (The verification of this fact is left as an exercise
for the reader.)

To produce the n! permutations of the integers 1, 2, 3, … , n, begin with the smallest permutation in lexicographic order, namely, 123 ⋯ n, and successively apply the procedure described
for producing the next larger permutation of n! − 1 times. This yields all the permutations of
the n smallest integers in lexicographic order.

Question 4

ALGORITHM 1 Generating the Next Permutation in Lexicographic Order

Algorithm 1 displays the procedure for finding the next permutation in lexicographic order
after a permutation that is not n n − 1 n − 2 … 2 1, which is the largest permutation.

Answer 4

procedure next permutation(a1a2 … an: permutation of
{1, 2, … , n} not equal to n n − 1 … 2 1)
j := n − 1
while aj > aj+1
    j := j − 1
{j is the largest subscript with aj < aj+1}
k := n
while aj > ak
   k := k − 1
{ak is the smallest integer greater than aj to the right of aj
}
interchange aj and ak
r := n
s := j + 1
while r > s
    interchange ar and as
    r := r − 1
    s := s + 1
{this puts the tail end of the permutation after the jth position in increasing order}
{a1a2 … an is now the next permutation}

Question 5

Generating Combinations

Pre req for generating combination, what is step before that :

Answer 5

How can we generate all the combinations of the elements of a finite set? Because a combination is just a subset, we can use the correspondence between subsets of {a1, a2,… , an} and bit strings
of length n.
Recall that the bit string corresponding to a subset has a 1 in position k if ak is in the subset,
or 0 if ak absent. If all the bit strings of length n can be listed,
then by the correspondence between subsets and bit strings, a list of all the subsets is obtained.
Recall that a bit string of length n is also the binary expansion of an integer between 0 and
(2^n) − 1. The 2^n bit strings can be listed in order of their increasing size as integers in their binary
expansions. To produce all binary expansions of length n, start with the bit string with
n zeros. Then, successively find the next expansion until the bit string 111 … 11 is obtained.
At each stage the next binary expansion is found by locating the first position from the right that is
not a 1, then changing all the 1s to the right of this position to 0s and making this first 0 (from
the right) a 1.

Question 6

ALGORITHM 2 Generating the Next Larger Bit String.

Answer 6

procedure next bit string(bn−1 bn−2…b1b0: bit string not equal to 11…11)
i := 0
while bi = 1
bi := 0
i := i + 1
bi := 1
{bn−1 bn−2…b1b0 is now the next bit string}

Question 7

Next, an algorithm for generating the r-combinations of the set {1, 2, 3, … , n} , logic for it:

Answer 7

An r-combination can be represented by a sequence containing the elements in the
subset in increasing order. The r-combinations can be listed using lexicographic order on
these sequences.

In this lexicographic ordering, the first r-combination is {1, 2, … , r − 1, r}
and the last r-combination is {n − r + 1, n − r + 2, … , n − 1, n}.

The next r-combination
after a1a2 ⋯ ar can be obtained in the following way: First, locate the last element ai in
the sequence such that ai ≠ n − r + i. Then, replace ai with ai + 1 and aj with ai + j − i + 1,
for j = i + 1, i + 2, … , r. It is left for the reader to show that this produces the next larger
r-combination in lexicographic order

Question 8

ALGORITHM 3 Generating the Next r-Combination in Lexicographic Order.

Answer 8

procedure next r-combination({a1, a2,… , ar}: proper subset of
{1, 2, … , n} not equal to {n − r + 1, … , n} with
a1 < a2 < ⋯ < ar)
i := r
while ai = n − r + i
i := i − 1
ai := ai + 1
for j := i + 1 to r
aj := ai + j − i
{{a1, a2,… , ar} is now the next combination}