需要递归地生成文件数组的每个唯一组合
我研究过很多类似的请求,但没有什么是我需要的。
这是我的问题。 我正在使用C#,我有一个FileInfo []数组,其中包含未知数量的元素。
FileInfo[] files = new FileInfo[] { new FileInfo(@"C:\a.jpg"), new FileInfo(@"C:\b.jpg"), new FileInfo(@"C:\c.jpg"), new FileInfo(@"C:\d.jpg"), new FileInfo(@"C:\e.jpg"), new FileInfo(@"C:\f.jpg"), new FileInfo(@"C:\g.jpg"), new FileInfo(@"C:\h.jpg"), new FileInfo(@"C:\i.jpg"), }; // Using 9 elements for this example
我需要生成这些文件的每个可能的重新排序组合的列表,而不重复文件。
所以,我的一些结果将是这样的(例子不是代码格式):
a, b, c, d, e, f, g, h, i a, b, c, d, e, f, g, i, h // i & h switched a, b, c, d, e, f, h, g, i // last 3 elements switched a, a, b, b, c, c, d, d, e // THIS IS NOT ACCEPTED, because elements are duplicated
等等,直到我想出了所有可能的组合
因此,结果总数应该是数组中元素数量的阶乘。 在这个例子中,有9个元素,因此应该有9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880种可能的组合。
我已经把这个搞乱了几天了,而我无法绕过它。 任何帮助表示赞赏,特别是代码示例!
谢谢!
Linq很容易:
IEnumerable permutations = from a in files from b in files.Except(new[] { a }) from c in files.Except(new[] { a, b }) from d in files.Except(new[] { a, b, c }) from e in files.Except(new[] { a, b, c, d }) from f in files.Except(new[] { a, b, c, d, e }) from g in files.Except(new[] { a, b, c, d, e, f }) from h in files.Except(new[] { a, b, c, d, e, f, g }) from i in files.Except(new[] { a, b, c, d, e, f, g, h }) select new[] { a, b, c, d, e, f, g, h, i };
编辑:
这是一个通用的解决方案,适用于任意数量的项目:
static class ExtensionMethods { public static IEnumerable> GetPermutations(this IEnumerable source, int count) { IEnumerable> result = new[] { Enumerable.Empty () }; for (int i = 0; i < count; i++) { result = from seq in result from item in source.Except(seq) select seq.Concat(new[] { item }); } return result; } }
使用方法如下:
IEnumerable> permutations = files.GetPermutations(9);
(此解决方案的灵感来自Eric Lippert关于笛卡尔产品的文章 。)
编辑2:
这是使用Aggregate
的变体:
static class ExtensionMethods { public static IEnumerable> GetPermutations2(this IEnumerable source, int count) { IEnumerable> seed = new[] { Enumerable.Empty () }; return Enumerable.Repeat(source, count) .Aggregate( seed, (accumulator, sequence) => from acc in accumulator from item in sequence.Except(acc) select acc.Concat(new[] { item })); } }
有各种算法可用于此。 下面的页面列出了3个不同的页面:
计算并列出所有排列
你真的想要集合的所有排列。
- http://www.codeproject.com/KB/recipes/Combinatorics.aspx
- http://blogs.msdn.com/b/updownroundnround/archive/2009/12/14/generating-all-permutations-c-enumerator-implementation.aspx
编辑:以下是您正在谈论的一个示例: http : //www.codeproject.com/KB/recipes/Premutations.aspx