Paradigms for constructing permutations explained

Question

According to the Algorithm Design Manual Sec 14.4, there are two paradigms to constructing permutations:

1. Ranking/Unranking
2. Incremental Change

I'm not grasping the section and I would appreciate an alternative explanation. Can you elaborate on the two with examples?

Answer 1

Ranking/Unranking

A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items. For our purposes the ranking will assign integers 0..(n!-1) to an ordering of all the permutations of the integers 0..(n-1).

Rank({2, 1, 0, 3}) = 17

Unranking is the inverse process: given a rank r obtain the permutation.

Unrank(17) = {2, 1, 0, 3}

Therefore, rank and unrank functions must be inverses of each other, that is, there exists a bijection.

permutation p = Unrank(Rank(p), n)

For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:

PERMUTATION      RANK
  (0, 1, 2, 3) ->  0
  (0, 1, 3, 2) ->  1
  (0, 2, 1, 3) ->  2
  (0, 2, 3, 1) ->  3
  (0, 3, 1, 2) ->  4
  (0, 3, 2, 1) ->  5
  (1, 0, 2, 3) ->  6
  (1, 0, 3, 2) ->  7
  (1, 2, 0, 3) ->  8
  (1, 2, 3, 0) ->  9
  (1, 3, 0, 2) -> 10
  (1, 3, 2, 0) -> 11
  (2, 0, 1, 3) -> 12
  (2, 0, 3, 1) -> 13
  (2, 1, 0, 3) -> 14
  (2, 1, 3, 0) -> 15
  (2, 3, 0, 1) -> 16
  (2, 3, 1, 0) -> 17
  (3, 0, 1, 2) -> 18
  (3, 0, 2, 1) -> 19
  (3, 1, 0, 2) -> 20
  (3, 1, 2, 0) -> 21
  (3, 2, 0, 1) -> 22
  (3, 2, 1, 0) -> 23

Incremental Change

Incremental change methods work by defining the next and previous operations to transform one permutation into another, typically by swapping two elements. The tricky part is to schedule the swaps so that permutations do not repeat until all of them have been generated. The output picture below gives an ordering of the six permutations of {1,2,3} using a single swap between successive permutations.

References

https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation https://en.wikipedia.org/wiki/Factorial_number_system#Permutations https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/