生成列表所有可能排列的算法?
假设我有一个包含 n 个元素的列表,我知道有 n 个!对这些元素进行排序的可能方法。生成此列表的所有可能排序的算法是什么?例如,我有列表 [a, b, c]。该算法将返回 [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b ,一]]。
我在这里读这个 但是
维基百科从来不擅长解释。我不太明白其中的很多内容。
Say I have a list of n elements, I know there are n! possible ways to order these elements. What is an algorithm to generate all possible orderings of this list? Example, I have list [a, b, c]. The algorithm would return [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].
I'm reading this here
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
But Wikipedia has never been good at explaining. I don't understand much of it.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(30)
基本上,对于从左到右的每一项,都会生成剩余项的所有排列(并且每一项都与当前元素相加)。这可以递归地完成(如果您喜欢痛苦,则可以迭代地完成),直到到达最后一项,此时只有一个可能的顺序。
因此,对于列表 [1,2,3,4],生成以 1 开头的所有排列,然后生成以 2 开头的所有排列,然后是 3,然后是 4。
这有效地减少了查找列表排列的问题四个项目到三个项目的列表。减少到 2 个,然后是 1 个项目列表后,将全部找到。
使用 3 个彩色球显示流程排列的示例:
(来自 https ://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)
Basically, for each item from left to right, all the permutations of the remaining items are generated (and each one is added with the current elements). This can be done recursively (or iteratively if you like pain) until the last item is reached at which point there is only one possible order.
So with the list [1,2,3,4] all the permutations that start with 1 are generated, then all the permutations that start with 2, then 3 then 4.
This effectively reduces the problem from one of finding permutations of a list of four items to a list of three items. After reducing to 2 and then 1 item lists, all of them will be found.
Example showing process permutations using 3 coloured balls:
(from https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)
下面是一个在数组上就地工作的 Python 算法:
您可以在这里亲自尝试代码:http://repl.it/J9v
Here is an algorithm in Python that works by in place on an array:
You can try the code out for yourself here: http://repl.it/J9v
这里已经有很多好的解决方案,但我想分享我如何自己解决这个问题,并希望这对那些也想得出自己的解决方案的人有所帮助。
经过一番思考这个问题后,我得出以下两个结论:
n
的列表总共有n!
种排列,因此我们得到n! /n=(n-1)!
每组中的排列。[a,b]
和[b,a]
。使用这两个简单的想法,我得出了以下算法:
以下是我在 C# 中实现此算法的方法:
There is already plenty of good solutions here, but I would like to share how I solved this problem on my own and hope that this might be helpful for somebody who would also like to derive his own solution.
After some pondering about the problem I have come up with two following conclusions:
L
of sizen
there will be equal number of solutions starting with L1, L2 ... Ln elements of the list. Since in total there aren!
permutations of the list of sizen
, we getn! / n = (n-1)!
permutations in each group.[a,b]
and[b,a]
.Using these two simple ideas I have derived the following algorithm:
Here is how I implemented this in C#:
对我来说,维基百科对“词典顺序”的回答在食谱风格中似乎非常明确。它引用了该算法的 14 世纪起源!
我刚刚用 Java 编写了维基百科算法的快速实现作为检查,这没有问题。但是你的 Q 中的例子不是“列出所有排列”,而是“所有排列的列表”,所以维基百科不会对你有太多帮助。您需要一种可以可行地构造排列列表的语言。相信我,数十亿长的列表通常不会用命令式语言处理。你确实想要一种非严格的函数式编程语言,其中列表是一流的对象,在不使机器接近宇宙热寂的情况下取出东西。
这很容易。在标准 Haskell 或任何现代 FP 语言中:
和
Wikipedia's answer for "lexicographic order" seems perfectly explicit in cookbook style to me. It cites a 14th century origin for the algorithm!
I've just written a quick implementation in Java of Wikipedia's algorithm as a check and it was no trouble. But what you have in your Q as an example is NOT "list all permutations", but "a LIST of all permutations", so wikipedia won't be a lot of help to you. You need a language in which lists of permutations are feasibly constructed. And believe me, lists a few billion long are not usually handled in imperative languages. You really want a non-strict functional programming language, in which lists are a first-class object, to get out stuff while not bringing the machine close to heat death of the Universe.
That's easy. In standard Haskell or any modern FP language:
and
正如旋风所说,你从头开始。
您将游标与每个剩余值交换,包括游标本身,这些都是新实例(我在示例中使用了
int[]
和array.clone()
)。然后对所有这些不同的列表执行排列,确保光标在右边。
当没有更多剩余值时(光标位于末尾),打印列表。这是停止条件。
As WhirlWind said, you start at the beginning.
You swap cursor with each remaining value, including cursor itself, these are all new instances (I used an
int[]
andarray.clone()
in the example).Then perform permutations on all these different lists, making sure the cursor is one to the right.
When there are no more remaining values (cursor is at the end), print the list. This is the stop condition.
递归总是需要一些脑力来维持。对于大数字,阶乘很容易变得很大,并且堆栈溢出很容易成为问题。
对于较小的数字(3 或 4,这是最常见的),多个循环非常简单且直接。不幸的是,带有循环的答案没有被投票通过。
让我们从枚举(而不是排列)开始。只需将代码视为伪 Perl 代码即可。
枚举比排列更常见,但如果需要排列,只需添加条件:
现在,如果您确实需要大列表的通用方法,我们可以使用基数方法。首先,考虑枚举问题:
基数增量本质上是数字计数(以列表元素数量为底)。
现在,如果您需要排列,只需在循环内添加检查:
编辑:上面的代码应该可以工作,但对于排列,radix_increment 可能会浪费。因此,如果时间是一个实际问题,我们必须将 radix_increment 更改为 permute_inc:
当然,现在这段代码在逻辑上更加复杂,我将留给读者练习。
Recursive always takes some mental effort to maintain. And for big numbers, factorial is easily huge and stack overflow will easily be a problem.
For small numbers (3 or 4, which is mostly encountered), multiple loops are quite simple and straight forward. It is unfortunate answers with loops didn't get voted up.
Let's start with enumeration (rather than permutation). Simply read the code as pseudo perl code.
Enumeration is more often encountered than permutation, but if permutation is needed, just add the conditions:
Now if you really need general method potentially for big lists, we can use radix method. First, consider the enumeration problem:
Radix increment is essentially number counting (in the base of number of list elements).
Now if you need permutaion, just add the checks inside the loop:
Edit: The above code should work, but for permutation, radix_increment could be wasteful. So if time is a practical concern, we have to change radix_increment into permute_inc:
Of course now this code is logically more complex, I'll leave for reader's exercise.
如果有人想知道如何在 javascript 中进行排列。
想法/伪代码
。 'a'+ 排列(bc)。 bc 的排列将是 bc & cb。现在将这两个相加将得到 abc、acb。类似地,选择 b + permute (ac) 将提供 bac、bca...并继续。
现在看一下代码
花点时间理解这一点。我从 (JavaScript 中的排列) 获得了这段代码
If anyone wonders how to be done in permutation in javascript.
Idea/pseudocode
for example. 'a'+ permute(bc). permute of bc would be bc & cb. Now add these two will give abc, acb. similarly, pick b + permute (ac) will provice bac, bca...and keep going.
now look at the code
Take your time to understand this. I got this code from (pertumation in JavaScript)
我用 ANSI C 编写了这个递归解决方案。Permutate 函数的每次执行都会提供一种不同的排列,直到所有排列完成为止。全局变量也可用于变量fact 和count。
I have written this recursive solution in ANSI C. Each execution of the Permutate function provides one different permutation until all are completed. Global variables can also be used for variables fact and count.
另一种Python语言,它不像@cdiggins那样到位,但我认为它更容易理解
Another one in Python, it's not in place as @cdiggins's, but I think it's easier to understand
我正在考虑编写一个代码来获取任何大小的任何给定整数的排列,即提供数字 4567,我们得到所有可能的排列,直到 7654...所以我研究了它并找到了一个算法并最终实现了它,在这里是用“c”编写的代码。
您可以简单地复制它并在任何开源编译器上运行。但有些缺陷有待调试。请欣赏。
代码:
I was thinking of writing a code for getting the permutations of any given integer of any size, i.e., providing a number 4567 we get all possible permutations till 7654...So i worked on it and found an algorithm and finally implemented it, Here is the code written in "c".
You can simply copy it and run on any open source compilers. But some flaws are waiting to be debugged. Please appreciate.
Code:
我创造了这个。也基于研究
排列(qwe, 0, qwe.length-1);
只是想让你知道,无论有没有回溯,你都可以做到这一点
I created this one. based on research too
permutate(qwe, 0, qwe.length-1);
Just so you know, you can do it with or without backtrack
这是一个玩具 Ruby 方法,其工作方式类似于
#permutation.to_a
,对于疯狂的人来说可能更容易理解。虽然很慢,但也需要 5 行。Here's a toy Ruby method that works like
#permutation.to_a
that might be more legible to crazy people. It's hella slow, but also 5 lines.Java
版本
输出:
Java version
E.g.
output:
在 PHP 中
in PHP
这是一个用于排列的java版本
this is a java version for permutation
下面是用 Python 编写的代码,用于打印列表的所有可能的排列:
我使用了字典顺序算法来获取所有可能的排列,但递归算法更有效。您可以在这里找到递归算法的代码:
Python 递归排列
Here is the code in Python to print all possible permutations of a list:
I have used a lexicographic order algorithm to get all possible permutations, but a recursive algorithm is more efficient. You can find the code for recursive algorithm here:
Python recursion permutations
在斯卡拉中
In Scala
这是 ColdFusion 的实现(需要 CF10,因为 ArrayAppend() 的合并参数):
基于上面 KhanSharp 的 js 解决方案。
Here's an implementation for ColdFusion (requires CF10 because of the merge argument to ArrayAppend() ):
Based on KhanSharp's js solution above.
我知道这是一个非常非常古老的问题,甚至在今天的 stackoverflow 中已经离题了,但我仍然想贡献一个友好的 javascript 答案,原因很简单,它在您的浏览器中运行。
我还添加了
debugger
指令断点,以便您可以单步执行代码(需要 chrome)来查看该算法的工作原理。在 Chrome 中打开开发控制台(Windows 中为F12
或 Mac 上为CMD + OPTION + I
),然后单击“运行代码片段”。这实现了 @WhirlWind 在他的答案中提出的完全相同的算法。您的浏览器应在
debugger
指令处暂停执行。使用F8
继续执行代码。单步执行代码,看看它是如何工作的!
I know this a very very old and even off-topic in today's stackoverflow but I still wanted to contribute a friendly javascript answer for the simple reason that it runs in your browser.
I've also added the
debugger
directive breakpoint so you can step through the code (chrome required) to see how this algorithm works. Open up your dev console in chrome (F12
in windows orCMD + OPTION + I
on mac) and then click "Run code snippet". This implements the same exact algorithm that @WhirlWind presented in his answer.Your browser should pause execution at the
debugger
directive. UseF8
to continue code execution.Step through the code and see how it works!
在下面的 Java 解决方案中,我们利用字符串不可变这一事实,以避免在每次迭代时克隆结果集。
输入将是一个字符串,例如“abc”,输出将是所有可能的排列:
代码:
相同的方法可以应用于数组(而不是字符串):
In the following Java solution we take advantage over the fact that Strings are immutable in order to avoid cloning the result-set upon every iteration.
The input will be a String, say "abc", and the output will be all the possible permutations:
Code:
Same approach can be applied to arrays (instead of a string):
这是我在Java上的解决方案:
It's my solution on Java:
如果不以 开创了这个想法。因此,为了完整起见,以下是在Scheme中可以完成的方法之一。
调用
(permof (list "foo" "bar" "baz"))
我们会得到:我不会深入讨论算法细节,因为它在其他帖子中已经得到了足够的解释。这个想法是一样的。
然而,递归问题在 Python、C 和 Java 等破坏性介质中往往更难建模和思考,而在 Lisp 或 ML 中则可以简洁地表达。
You can't really talk about solving a permultation problem in recursion without posting an implementation in a (dialect of) language that pioneered the idea. So, for the sake of completeness, here is one of the ways that can be done in Scheme.
calling
(permof (list "foo" "bar" "baz"))
we'll get:I won't go into the algorithm details because it's been explained enough in other posts. The idea is the same.
However, recursive problems tend to be much harder to model and think about in destructive medium like Python, C, and Java, while in Lisp or ML it can be concisely expressed.
当我在工程的第一年时,我想出了这些算法(一个是递归的,另一个是迭代的),并用 python 实现了它们(我为随机命名方案表示歉意):
第一个算法的特点:
和计算资源)。
ASCII 值。的字符。
其中 n 是输入中的字符数,i 是索引
任何重复的字符,m 是重复的次数
索引为 i 的字符。
第二种算法是递归的:
允许的递归深度是有限的。
I came up with these algorithms (one recursive and the other iterative) when I was in my first year of engineering and implemented them in python (I apologize for the random naming scheme):
Characteristics of the first algorithm:
and computing resources).
ASCII values. of the characters.
where n is the number of characters in the input, i is the index of
any character that is repeated, and m is the number of repetitions of
the character with index i.
The second algorithm is recursive:
the recursion depth allowed is finite.
这是 PHP 中的递归解决方案。 WhirlWind 的帖子准确地描述了这个逻辑。值得一提的是,生成所有排列都是在阶乘时间内运行的,因此使用迭代方法可能是一个好主意。
strDiff 函数接受两个字符串
s1
和s2
,并返回一个新字符串,其中包含s1
中的所有内容,但不含s2
中的元素代码>(重复内容)。所以,strDiff('finish','i') =>'fnish'
(第二个“i”未被删除)。Here is a recursive solution in PHP. WhirlWind's post accurately describes the logic. It's worth mentioning that generating all permutations runs in factorial time, so it might be a good idea to use an iterative approach instead.
The strDiff function takes two strings,
s1
ands2
, and returns a new string with everything ins1
without elements ins2
(duplicates matter). So,strDiff('finish','i')
=>'fnish'
(the second 'i' is not removed).这是 R 中的一个算法,以防有人需要像我一样避免加载额外的库。
用法示例:
Here is an algorithm in R, in case anyone needs to avoid loading additional libraries like I had to.
Example usage:
为了完整起见,C++
...
Just to be complete, C++
...
这是 C++ 中的非递归解决方案,它按升序提供下一个排列,类似于 std::next_permutation 提供的功能:
Here is a non-recursive solution in C++ that provides the next permutation in ascending order, similarly to the functionality provided by std::next_permutation:
在 C 中,创建单个矩阵(无符号字符)来快速轻松地访问从 1 到 6 的所有排列。基于 https://www.geeksforgeeks.org/heaps-algorithm 的代码-用于生成排列/。
In C, create a single matrix (unsigned char) to quickly and easily access all permutations from 1 to 6. Based on code from https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/.