算法生成一个列表的所有可能的排列？ [英] Algorithm to generate all possible permutations of a list?

问题描述

说我有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]].

我在读这在这里 <一href="http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations">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.

推荐答案

基本上，用于从每个元素从左到右，生成剩余元素的所有排列。 （如果你喜欢疼痛或反复），你可以做到这一点递归，直到你到最后一个元素，此时只有一种可能的顺序。

Basically, for each element from left to right, you generate all the permutations of the remaining elements. You can do this recursively, (or iteratively if you like pain) until you get to the last element at which point there is only one possible order.

所以，对于一个列表： [1,2,3,4]

So, given a list: [1,2,3,4]

您刚刚生成从1开始的所有排列，那么所有先从2的排列，然后用3和4。

You just generate all permutations that start with 1, then all the permutations that start with 2, then with 3 and 4.

这有效地发现有四个元素的列表排列的三个元素列表中的一个降低的问题。一旦你继续减少至2，然后1元，你把所有的人。

This effectively reduces the problem from one of finding permutations of a list of four elements to a list of three elements. Once you continue reducing to 2 and then 1 element, you have all of them.

这篇关于算法生成一个列表的所有可能的排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！