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之外产生另一个;对于我来说,在查询语法中重写它是困难的部分.
我读过这个答案：
但我想这对我来说不是解决方案..
我尝试了各种方法,并认为这样做并不容易.我怎么能完成它？
(Exchange方法是另一个问题,我问过一个问题：
How to exchange the items of enumeration by interating only once?
但我想这不是问题..)
解决方法
单线解决方案,无递归
我已经重新创建了核心方法(来自本答案中的下一个解决方案),所以现在它不再是递归的了.现在很容易从中做出单线解决方案.
我不得不使用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 permutations CreateIndices(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 ]
递归的想法是每个级别都基于前一个级别构建.
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 elements
var result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations
).ToArray(); // pay to get the permutations
如果我们只列举一半的排列,这使我们只需支付一半的费用.
