C# · 12月 23, 2021

c# – 如何使用查询语法创建排列?

我试图编写一个方法,尽可能简单地返回给定枚举的排列.代码: using System.Collections.Generic;public static partial class Permutable { static IEnumerable<IEnumerable<T>> PermuteIterator<T>( IEnumerable<T> source,int offset) { var count=0; foreach(var dummy in source) if(++count>offset) foreach( var sequence in Permutable.PermuteIterator( source.Exchange(offset,count-1),1+offset) ) yield return sequence; if(offset==count-1) yield return source; } public static IEnumerable<IEnumerable<T>> AsPermutable<T>( this IEnumerable<T> source) { return Permutable.PermuteIterator(source,0); } public static IEnumerable<T> Exchange<T>( this IEnumerable<T> source,int index1,int index2) { // exchange elements at index1 and index2 }}

由于代码在迭代器块中简化了,我试图使它只是LINQ的单个查询表达式.

使用此代码在嵌套的foreach中有一个递归,甚至可能在foreach之外产生另一个;对于我来说,在查询语法中重写它是困难的部分.

我读过这个答案:

C# String permutation

但我想这对我来说不是解决方案..

我尝试了各种方法,并认为这样做并不容易.我怎么能完成它?

(Exchange方法是另一个问题,我问过一个问题:

How to exchange the items of enumeration by interating only once?

但我想这不是问题..)

解决方法 编辑1:

单线解决方案,无递归

我已经重新创建了核心方法(来自本答案中的下一个解决方案),所以现在它不再是递归的了.现在很容易从中做出单线解决方案.

我不得不使用Enumerable方法和扩展方法来做到这一点.没有这些,我认为不可能做到这一点.

class Permutator{ private static IEnumerable<IEnumerable<int>> CreateIndices(int length) { var factorial = Enumerable.Range(2,length – 1) .Aggregate((a,b) => a * b); return (from p in Enumerable.Range(0,factorial) // creating module values from 2 up to length // e.g. length = 3: mods = [ p%2,p%3 ] // e.g. length = 4: mods = [ p%2,p%3,p%4 ] let mods = Enumerable.Range(2,length – 1) .Select(m => p % m).ToArray() select ( // creating indices for each permutation mods.Aggregate( new[] { 0 },(s,i) => s.Take(i) .Concat(new[] { s.Length }) .Concat(s.Skip(i)).ToArray()) )); } public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { var array = items.ToArray(); return from indices in CreateIndices(array.Length) select (from i in indices select array[i]); }}

现在是最终解决方案

结果就是这种怪异:

class Permutator{ public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { return from p in Enumerable.Range(0,Enumerable.Range(2,items.Count() – 1) .Aggregate((a,b) => a * b)) let mods = Enumerable.Range(2,items.Count() – 1) .Select(m => p % m).ToArray() select mods.Aggregate( items.Take(1).ToArray(),i) => s.Take(i) .Concat(items.Skip(s.Length).Take(1)) .Concat(s.Skip(i)).ToArray()); }}

以前的方案

我创造了一些你可能正在寻找的东西:

class Permutator{ private static IEnumerable<IEnumerable<int>> CreateIndices(int length) { return (from p in Enumerable.Range(0,length) select ( from s in Permutator.CreateIndices(length – 1) .DefaultIfEmpty(Enumerable.Empty<int>()) select s.Take(p) .Concat(new[] { length – 1 }) .Concat(s.Skip(p)) )) .SelectMany(i => i); } public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { var array = items.ToArray(); return from indices in CreateIndices(array.Length) select (from i in indices select array[i]); }}

如何使用它的示例:

var items = new[] { “0”,”1″,”2″ };var p = Permutator.Get(items);var result = p.Select(a=>a.ToArray()).ToArray();

这个怎么运作

核心是CreateIndices方法.它为每个排列创建一个包含源元素索引的序列.

最好用一个例子来解释:

CreateIndices(0);// returns no permutationsCreateIndices(1);// returns 1 permutation// [ 0 ]CreateIndices(2);// returns 2 permutations// [ 1,0 ]// [ 0,1 ]CreateIndices(3);// returns 6 permutations// [ 2,1,0 ]// [ 2,1 ]// [ 1,2,2 ]// [ 0,2 ]

它是一种递归方法,仅基于可枚举扩展和LINQ语法查询.

递归的想法是每个级别都基于前一个级别构建.

CreateIndices(n)将元素n-1添加到CreateIndices(n-1)在所有可用位置返回的排列.

递归的根是CreateIndices(0),返回一组空的排列.

逐步解释:CreateIndices(3)

1.让我们从创建CreateIndices(0)的结果开始:

>空的

2.然后是CreateIndices(1)的结果:

>将元素0(n-1)添加到位置0的每个先前排列
[0]

3.然后CreateIndices的结果(2)

>将元素1(n-1)添加到位置0的每个先前的排列中
[1,0]
>将元素1(n-1)添加到位置1的每个先前排列
[0,1]

4.然后CreateIndices的结果(3)

>将元素2(n-1)添加到位置0的每个先前排列
[2,0]
[2,1]
>将元素2(n-1)添加到位置1的每个先前排列
[1,0]
[0,1]
>将元素2(n-1)添加到位置2的每个先前排列
[1,2]
[0,2]

接下来发生什么

现在我们已经为每个排列设置了索引,我们可以使用它们来构建值的实际排列.这就是泛型Get方法的作用.

另请注意,Get方法是唯一一个将源序列具体化为数组的方法. CreateIndices只是一个枚举器,没有任何实际对象…因此,您只需支付成本,枚举序列,以及调用Get you pay来创建源序列数组.

这解释了为什么在示例中调用Get之后,我必须实现结果,以便我们可以使用它:

var items = new[] { “0”,”2″ };var p = Permutator.Get(items); // pay to create array from source elementsvar result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations ).ToArray(); // pay to get the permutations

如果我们只列举一半的排列,这使我们只需支付一半的费用.