懒洋洋地产生排列

我正在寻找一种算法来生成集合的排列,这样我就可以在Clojure中创建它们的惰性列表.即我想迭代一个排列列表,其中每个排列都不计算,直到我请求它,并且所有排列不必一次存储在内存中.

或者我正在寻找一种给定某个集合的算法,它将返回该集合的"下一个"排列,以这种方式在自己的输出上重复调用该函数将循环遍历原始集合的所有排列,一些订单(订单无关紧要).

有这样的算法吗？我见过的大多数排列生成算法都倾向于一次性生成它们(通常是递归的),这些算法不能扩展到非常大的集合.Clojure(或其他函数式语言)中的实现会有所帮助,但我可以从伪代码中找出它.

1> ShreevatsaR..：

---

是的,是 "下一个置换"的算法,这是相当简单了.C++标准模板库(STL)甚至还有一个名为的函数next_permutation.

该算法实际上找到下一个排列 - 按字典顺序排列下一个排列.这个想法是这样的:假设给你一个序列,比如"32541".下一个排列是什么？

如果你考虑一下,你会发现它是"34125".你的想法可能是这样的:在"32541"中,

没有办法保持"32"固定并在"541"部分中找到后来的排列,因为该排列已经是5,4和1的最后一个排列 - 它按降序排序.

所以你必须将"2"改为更大的东西 - 实际上,要比"541"部分中的最小数字更大,即4.

现在,一旦您确定排列将以"34"开始,其余数字应按递增顺序排列,因此答案为"34125".

算法是精确地实现这一推理:

找到按降序排序的最长"尾部".("541"部分.)

将尾部("2")之前的数字更改为比尾部(4)更大的数字.

按递增顺序排序尾部.

只要前一个元素不小于当前元素,您就可以通过从末尾开始并向后返回来有效地执行(1.).您可以通过将"4"与"2"交换来做(2.),因此您将拥有"34521".一旦执行此操作,您可以避免使用(3.)的排序算法,因为尾部是,并且仍然(想想这个),按降序排序,所以它只需要颠倒.

C++代码正是这样做的(查看系统中的源代码/usr/include/c++/4.0.0/bits/stl_algo.h,或者查看本文); 将它翻译成您的语言应该很简单:[如果您不熟悉C++迭代器,请将"BidirectionalIterator"读作"指针".false如果没有下一个排列,则代码返回,即我们已经按降序排列.]

template 
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

看起来每个排列可能花费O(n)时间,但如果你仔细考虑它,你可以证明所有排列总共需要O(n!)时间,所以只有O(1) - 恒定时间 - 每个排列.

好的是,即使你有一个带有重复元素的序列,该算法也可以工作:例如,"232254421",它会发现尾部为"54421",交换"2"和"4"(所以"232454221" ),反转其余部分,给出"232412245",这是下一个排列.

---

如果从一组开始,您可以任意定义元素的总顺序; 将元素映射到不同的数字.:-)

---

假设您对元素有总订单,这将有效.

---

这个答案只是没有得到足够的支持,但我只能投票一次...... :-)

2> joel.neely..：

---

假设我们正在讨论关于被置换的值的词典顺序,您可以使用两种通用方法:

将元素的一个排列转换为下一个排列(如ShreevatsaR发布的),或

直接计算nth置换,同时n从0向上计数.

对于那些不喜欢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

对于第二种方法(直接计算n排列),请记住存在元素的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)计数并直接计算相应的排列.