Using LexOrder a Find the next twelve 7permutations on 1 9

Using Lex-Order, (a) Find the next twelve 7-permutations on { 1 ..9 } after (8, 1, 3, 9, 7, 6, 4). (b) Find the next 7 full permutations on { 1.12) after (8, 11, 10, 1,12,5,3,9, 7,6,4,2).

Solution

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

(a)

(8,1,3,9,7,6,4)

let index k=2 because 3 is place at k+1 which satisfies condition of being the largest index that is still less than a[k + 1] which is 9

now 9,7,6,4 are all greater that 3 so we could get the next sequense as follows

th next twelve permutations are:

1. (8,1,4,9,7,6,3)    

2. (8,1,6,9,7,3,4)

3. (8,1,6,9,7,4,3)

4. (8,1,7,9,3,6,4)

5. (8,1,7,9,6,4,3)

6. (8,1,7,9,4,6,3)

7. (8,1,7,9,6,3,4)

8. (8,1,9,3,7,6,4)

9. (8,1,9,4,7,6,3)

10. (8,1,9,6,7,3,4)

11. (8,1,9,6,7,4,3)

12. (8,1,9,7,4,6,3)

(b)

(8,11,10,1,12,5,3,9,7,6,4,2)

lets take index k=4

now a[k]<a[k+1]

hence the next 7 full permutations are:

1.   (8,11,10,12,1,5,3,9,7,6,4,2)

2. (8,11,10,12,1,6,3,9,7,5,4,2)

3. (8,11,10,12,1,7,3,9,5,6,4,2)    

4. (8,11,10,12,1,7,3,9,6,5,4,2)

5. (8,11,10,12,1,9,3,5,7,6,4,2)

6. (8,11,10,12,1,9,3,7,6,5,4,2)

    take index j=1

    a[j]<a[j+1]

hence the seventh permutation is

7.   (8,12,10,11,1,5,3,9,7,6,4,2)