用于解释排列的范例

Question

根据Algorithm Design Manual Sec 14.4，构造排列有两种范例：

1. 排名/排名
2. 增量变化

我没有掌握本节内容，不胜感激。您可以通过示例详细说明两者吗？

Answer 1

排名/排名

置换的

特定的排名将整数与一组不同项的所有置换的特定顺序相关联。为了我们的目的，排名将整数0 ..（n！-1）分配给整数0 ..（n-1）的所有排列的顺序。

Unranking是相反的过程：给定等级r获得排列。

因此，rank和unrank函数必须彼此相反，即存在bijection。

例如，按字典顺序排列的数字0到3的排列具有以下等级：

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

增量更改

增量更改方法的工作原理是定义下一个和上一个操作，通常通过交换两个元素将一个排列转换为另一个排列。棘手的部分是安排交换，以便在所有替换生成之前不会重复排列。下面的输出图片使用连续排列之间的单个交换给出{1,2,3}的六个排列的顺序。

参考

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