Csharp/C#教程:一组给定数字的排列分享


一组给定数字的排列

有人可以解释一个好的算法,以有效的方式找到给定数字集的所有排列吗?

最简单的方法是递归方法,即可执行伪代码;

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意味着“我们都完成了,再见!”。

在不同的性能轴上有一些更好的方法,但第一个里程碑是确保你完全熟悉基本的递归方法并彻底理解它 - 所以我现在停在这里。 如果你完全理解这种方法,为什么它会很好,花花公子, 以及如何以及为什么它在性能上看起来不是最佳,我会很乐意扩展这个答案! - )

https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

我对Alex的伪代码的实现:

  private int length; private List> permutations; public List> Generate(List list) { length = list.Count; permutations = new List>(); foreach(List subperms in Recursive(list)) permutations.Add(subperms); return permutations; } private List> Recursive(List list) { List> subperms = new List>(); 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 tail = new List(list); tail.RemoveAt(0); List head = new List(); head.Add(list[0]); foreach (List subperm in Recursive(tail)) { List headCopy = new List(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; } 

你看过Knuth的“计算机编程艺术”吗? 第3卷,排序和搜索涵盖了它,这是有道理的,因为排序会创建数据的特定排列。

警惕找到所有组合或排列的组合(和置换)算法。 它们具有非常昂贵的Big-O表示法成本。

上述就是C#学习教程:一组给定数字的排列分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/cdevelopment/1000328.html

(0)
上一篇 2021年12月27日
下一篇 2021年12月27日

精彩推荐