懒惰地生成排列

Question

我正在寻找一种算法来生成集合的排列，以便可以在Clojure中列出它们的惰性列表。即，我想遍历一系列排列，在我请求之前不会计算每个排列，并且不必将所有排列立即存储在内存中。或者，我正在寻找一种算法，给定特定集合，该算法将返回该集合的“下一个”排列，以这种方式，在其自己的输出上重复调用该函数将循环遍历原始集合的所有排列，一些订单（顺序无关紧要）。有这样的算法吗？我见过的大多数排列生成算法都倾向于一次全部生成它们（通常是递归生成），而这些算法并不能扩展到非常大的集合。用Clojure（或另一种功能语言）实现将很有帮助，但我可以从伪代码中弄清楚。

Answer 1

假设我们在讨论排列值的字典顺序，则可以使用两种通用方法：

将元素的一个排列转换为下一个排列（如ShreevatsaR发布），或者

从0向上n计数n，直接计算th排列。

对于那些不像本地人那样讲c ++的人（如我；-），可以从下面的伪代码实现方法1，假设索引的零从零开始在索引的左侧为数组（用其他结构代替） ，例如列表，是“作为练习留下的；”-）：

1. scan the array from right-to-left (indices descending from N-1 to 0)

1.1. if the current element is less than its right-hand neighbor,

     call the current element the pivot,

     and stop scanning

1.2. if the left end is reached without finding a pivot,

     reverse the array and return

     (the permutation was the lexicographically last, so its time to start over)

2. scan the array from right-to-left again,

   to find the rightmost element larger than the pivot

   (call that one the successor)

3. swap the pivot and the successor

4. reverse the portion of the array to the right of where the pivot was found

5. return

这是一个从CADB当前排列开始的示例：

1. scanning from the right finds A as the pivot in position 1

2. scanning again finds B as the successor in position 3

3. swapping pivot and successor gives CBDA

4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD

5. CBAD is the next permutation after CADB

对于第二种方法（直接计算nth排列），请记住存在元素的N!排列N。因此，如果要排列N元素，则第一个(N-1)!排列必须以最小的元素开始，接下来的(N-1)!排列必须以第二个最小的元素开始，依此类推。这导致以下递归方法（再次使用伪代码，从0开始对排列和位置进行编号）：

To find permutation x of array A, where A has N elements:

0. if A has one element, return it

1. set p to ( x / (N-1)! ) mod N

2. the desired permutation will be A[p] followed by

   permutation ( x mod (N-1)! )

   of the elements remaining in A after position p is removed

因此，例如，发现ABCD的第13个置换如下：

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}

C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}

  perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}

  A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}

    perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}

    D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}

      B (because there's only one element)

    DB

  ADB

CADB

顺便说一下，元素的“删除”可以由布尔值的并行数组表示，该数组指示哪些元素仍然可用，因此不必在每个递归调用上创建新的数组。

因此，要遍历ABCD的排列，只需从0到23（4！-1）计数并直接计算对应的排列即可。