生成排列懒洋洋地 [英] Generating permutations lazily

问题描述

我在寻找一种算法来生成一组排列在这样一种方式，我可以让他们在Clojure的懒列表。即我想遍历每个置换不计算，直到我要求它排列的列表，并且所有的排列没有被存储在内存中一次。

I'm looking for an algorithm to generate permutations of a set in such a way that I could make a lazy list of them in Clojure. i.e. I'd like to iterate over a list of permutations where each permutation is not calculated until I request it, and all of the permutations don't have to be stored in memory at once.

另外我要找的地方给予一定的设置，它会返回一个集的下一个置换，以这样的方式，通过原始的所有排列多次呼吁自己的输出将循环函数的算法设置，以某种顺序（顺序是什么并不重要）。

Alternatively I'm looking for an algorithm where given a certain set, it will return the "next" permutation of that set, in such a way that repeatedly calling the function on its own output will cycle through all permutations of the original set, in some order (what the order is doesn't matter).

有没有这样的算法？大多数我见过的排列生成算法往往生成它们一次全部（通常递归），它没有规模非常大集。 Clojure中的实现（或其他功能性的语言）将是有益的，但​​我可以计算出来的伪code。

Is there such an algorithm? Most of the permutation-generating algorithms I've seen tend to generate them all at once (usually recursively), which doesn't scale to very large sets. An implementation in Clojure (or another functional language) would be helpful but I can figure it out from pseudocode.

推荐答案

对了，还有的是的下一个置换的算法，这是相当简单了。 C ++标准模板库（STL），甚至有一个调用的函数 next_permutation 。

Yes, there is a "next permutation" algorithm, and it's quite simple too. The C++ standard template library (STL) even has a function called next_permutation.

该算法实际上找到的下一步的置换 - 字典序下一个。我们的想法是这样的：假设你将得到一个序列，说：32541。什么是下一个排列？

The algorithm actually finds the next permutation -- the lexicographically next one. The idea is this: suppose you are given a sequence, say "32541". What is the next permutation?

如果你仔细想想，你会发现它是34125。而你的想法很可能是一些这样的：32541，

If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",

• 也没有办法来保持32的固定，并找到在541的部分更高的置换，因为置换已经是最后一个用于5,4，和1 - 它是按递减顺序。
• 所以，你必须改变2，以更大的东西 - 其实，以最小的数字大于它在541的一部分，即4
• 现在，一旦你已经决定，置换将开始为34，该号码的其余部分应该按升序排列，所以答案是34125。

该算法是pcisely实现$ P $的推理：

The algorithm is to implement precisely that line of reasoning:

1. 找到最长的尾巴，即有序的递减顺序排列。 （以下简称541的一部分。）
2. 只是尾部（2），以最小的数目大于它的尾部之前更改号码（4）。
3. 在排序中为了增加尾部。

可以做（1）高效率地由起始于端和倒退只要previous元件不大于当前元素小。你可以这样做（2）由刚换了4与2，所以你必须34521。一旦你这样做，你能避免使用排序算法（3），因为尾巴过去是，仍然是（想一想），按照降序排列，所以只需要得到扭转。

You can do (1.) efficiently by starting at the end and going backwards as long as the previous element is not smaller than the current element. You can do (2.) by just swapping the "4" with the '2", so you'll have "34521". Once you do this, you can avoid using a sorting algorithm for (3.), because the tail was, and is still (think about this), sorted in decreasing order, so it only needs to be reversed.

在C + + code的确precisely这个（看看 / usr / include目录/ C ++ / 4.0.0 /位/ stl_algo.h 源在系统上，或参阅这篇文章）;它应该是简单的把它翻译成你的语言：[阅读BidirectionalIterator的指针，如果你不熟悉C ++迭代器。在code返回假如果没有接下来的置换，也就是说，我们已经在递减的顺序。]

The C++ code does precisely this (look at the source in /usr/include/c++/4.0.0/bits/stl_algo.h on your system, or see this article); it should be simple to translate it to your language: [Read "BidirectionalIterator" as "pointer", if you're unfamiliar with C++ iterators. The code returns false if there is no next permutation, i.e. we are already in decreasing order.]

template <class BidirectionalIterator>
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 ） - 固定的时间 - 每置换

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes O(n!) time for all permutations in total, so only O(1) -- constant time -- per permutation.

的好处是，当你有一个序列重复元素的算法的工作，即使：有，比如说，232254421，它会发现尾部为54421，交换了2和4（这样232454221），反向的其余部分，给予232412245，这是下一个置换

The good thing is that the algorithm works even when you have a sequence with repeated elements: with, say, "232254421", it would find the tail as "54421", swap the "2" and "4" (so "232454221"), reverse the rest, giving "232412245", which is the next permutation.

这篇关于生成排列懒洋洋地的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！