有人可以解释一个好的算法来以有效的方式找到给定数字集的所有排列吗?
问问题
2244 次
4 回答
8
最简单的方法是递归方法,即在可执行伪代码中;
def permute(theseq):
if len(theseq) <= 1:
yield theseq
return
for i in range(len(theseq)):
theseq[0], theseq[i] = theseq[i], theseq[0]
for subperm in permute(theseq[1:]):
yield theseq[:1] + subperm
theseq[0], theseq[i] = theseq[i], theseq[0]
如果您不熟悉可执行伪代码,符号[1:]
和[:1]
旨在表示“切片”(分别为“除第一个之外的所有”和“仅第一个”),并且两个相同的分配执行“交换第 0 个”的任务以及第 i 个项目”和“将它们放回原处”(即再次交换它们;-)。 yield
表示“提供此结果,但在迭代时准备好继续”,而return
表示“我们都完成了,再见!”。
沿着不同的性能轴有一些更好的方法,但第一个里程碑是确保您完全熟悉基本的递归方法并彻底理解它——所以我现在就停在这里。如果并且当您完全理解这种方法时,为什么它会很好用,花花公子,以及它如何以及为什么在性能上看起来并不是最佳的,我很乐意扩展这个答案!-)
于 2009-10-31T06:36:54.270 回答
6
于 2009-10-31T05:53:35.313 回答
3
我对 Alex 的伪代码的 c# 实现:
private int length;
private List<List<string>> permutations;
public List<List<string>> Generate(List<string> list)
{
length = list.Count;
permutations = new List<List<string>>();
foreach(List<string> subperms in Recursive(list))
permutations.Add(subperms);
return permutations;
}
private List<List<string>> Recursive(List<string> list)
{
List<List<string>> subperms = new List<List<string>>();
if (list.Count <= 1)
{
subperms.Add(list);
return subperms;
}
for (int i = 0; i < list.Count; i++)
{
string temp = list[0];
list[0] = list[i];
list[i] = temp;
List<string> tail = new List<string>(list);
tail.RemoveAt(0);
List<string> head = new List<string>();
head.Add(list[0]);
foreach (List<string> subperm in Recursive(tail))
{
List<string> headCopy = new List<string>(head);
headCopy.AddRange(subperm);
if (headCopy.Count == length)
permutations.Add(headCopy);
else
subperms.Add(headCopy);
}
temp = list[0];
list[0] = list[i];
list[i] = temp;
}
return subperms;
}
于 2012-07-13T10:56:43.457 回答
0
你看过 Knuth 的“计算机编程艺术”吗?第 3 卷,排序和搜索涵盖了它,这是有道理的,因为排序会创建数据的特定排列。
警惕可以找到所有组合或排列的组合(和排列)算法。他们有非常昂贵的 Big-O 符号成本。
于 2009-10-31T05:59:08.080 回答