惰性生成排列
我正在寻找一种算法来生成一组排列,以便我可以在 Clojure 中制作它们的惰性列表。 即我想迭代一个排列列表,其中每个排列在我请求之前不会被计算,并且所有排列不必立即存储在内存中。
或者,我正在寻找一种算法,其中给定某个集合,它将返回该集合的“下一个”排列,以这种方式,在其自己的输出上重复调用该函数将循环遍历原始集合的所有排列,一些顺序(顺序是什么并不重要)。
有这样的算法吗? 我见过的大多数排列生成算法都倾向于一次生成它们(通常是递归地),这不能扩展到非常大的集合。 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).
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.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
是的,有一个“下一个排列”算法,而且它也很简单。 C++ 标准模板库 (STL) 甚至有一个名为
next_permutation
的函数。该算法实际上找到了下一个排列——字典顺序上的下一个排列。 这个想法是这样的:假设给你一个序列,比如“32541”。 下一个排列是什么?
如果你仔细想想,你会发现它是“34125”。 你的想法可能是这样的:在“32541”中,
该算法旨在精确地实现该推理:
只要前一个元素不小于当前元素,您就可以通过从末尾开始并向后移动来有效地执行 (1.)。 你可以通过将“4”与“2”交换来完成(2.),这样你就会得到“34521”。一旦你这样做了,你就可以避免对(3.)使用排序算法,因为尾部过去和现在(想想这一点)都按降序排序,因此只需颠倒
C++ 代码即可做到这一点(请查看
/usr/include/c++/4.0.0/ 中的源代码。 bits/stl_algo.h
在您的系统上,或参阅本文 ); 将其翻译成您的语言应该很简单:[如果您不熟悉 C++ 迭代器,请将“Bi DirectionIterator”读作“指针”,如果没有下一个排列,则代码将返回false
,即我们已经按降序排列。]看起来每个排列可能需要 O(n) 时间,但是如果您更仔细地考虑一下,您可以证明所有排列总共需要 O(n!) 时间,所以每次排列只需 O(1) —— 常数时间。
好处是,即使你有一个包含重复元素的序列,算法也能工作:比如,“232254421”,它会发现尾部为“54421”。 ”,交换“2”和“4”(即“232454221”),反转其余部分,得到“232412245”,这是下一个排列。
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
.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?
If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",
The algorithm is to implement precisely that line of reasoning:
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.
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 returnsfalse
if there is no next permutation, i.e. we are already in decreasing order.]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.
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.
假设我们正在讨论排列值的字典顺序,则可以使用两种通用方法:
n< /code>th 排列,同时从 0 向上计数
n
。对于那些不会说 c++ 的人(像我一样;-),方法 1 可以通过以下伪代码实现,假设数组的从零开始索引,索引为零在“左侧”(替换一些其他结构) ,例如列表,被“留作练习”;-):
这是一个以 CADB 的当前排列开始的示例:
对于第二种方法(直接计算第 n 个排列),请记住有
N!
个N
元素的排列。 因此,如果您要排列N
元素,则第一个(N-1)!
排列必须从最小元素开始,即下一个(N-1)!
排列必须从第二小的排列开始,依此类推。 这导致了以下递归方法(同样是伪代码,从 0 开始对排列和位置进行编号):例如,ABCD 的第 13 个排列如下所示:
顺便说一句,元素的“删除”可以表示为布尔值的并行数组,指示哪些元素仍然可用,因此无需在每次递归调用时创建新数组。
因此,要迭代 ABCD 的排列,只需从 0 数到 23 (4!-1) 并直接计算相应的排列。
Assuming that we're talking about lexicographic order over the values being permuted, there are two general approaches that you can use:
n
th permutation, while countingn
from 0 upward.For those (like me ;-) who don't speak c++ as natives, approach 1 can be implemented from the following pseudo-code, assuming zero-based indexing of an array with index zero on the "left" (substituting some other structure, such as a list, is "left as an exercise" ;-):
Here's an example starting with a current permutation of CADB:
For the second approach (direct computation of the
n
th permutation), remember that there areN!
permutations ofN
elements. Therefore, if you are permutingN
elements, the first(N-1)!
permutations must begin with the smallest element, the next(N-1)!
permutations must begin with the second smallest, and so on. This leads to the following recursive approach (again in pseudo-code, numbering the permutations and positions from 0):So, for example, the 13th permutation of ABCD is found as follows:
Incidentally, the "removal" of elements can be represented by a parallel array of booleans which indicates which elements are still available, so it is not necessary to create a new array on each recursive call.
So, to iterate across the permutations of ABCD, just count from 0 to 23 (4!-1) and directly compute the corresponding permutation.
您应该查看 wikipeda 上的排列文章。 此外,还有Factoradic数字的概念。
无论如何,这道数学题还是挺难的。
在
C#
中,您可以使用迭代器
,并使用yield
停止排列算法。 这样做的问题是你不能来回移动,也不能使用索引
。You should check the Permutations article on wikipeda. Also, there is the concept of Factoradic numbers.
Anyway, the mathematical problem is quite hard.
In
C#
you can use aniterator
, and stop the permutation algorithm usingyield
. The problem with this is that you cannot go back and forth, or use anindex
.生成它们的排列算法的更多示例。
资料来源:http://www.ddj.com/architect/201200326
1.
2.
3.
More examples of permutation algorithms to generate them.
Source: http://www.ddj.com/architect/201200326
1.
2.
3.
clojure.contrib.lazy_seqs 中的排列函数已经声称可以做到这一点。
the permutations function in clojure.contrib.lazy_seqs already claims to do just this.
它在 2022 年看起来很死灵,但我还是要分享它
这里 C++ 的实现
next_permutation< Java 中的 /code> 可以找到。 在 Clojure 中使用它的想法可能类似于
免责声明:我是该项目的作者和维护者
It looks necromantic in 2022 but I'm sharing it anyway
Here an implementation of C++
next_permutation
in Java can be found. The idea of using it in Clojure might be something likedisclaimer: I'm the author and maintainer of the project