编辑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(),
(s, 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, 0, 1 ]
// [ 1, 2, 0 ]
// [ 0, 2, 1 ]
// [ 1, 0, 2 ]
// [ 0, 1, 2 ]
它是一种递归方法,仅基于可枚举扩展和 LINQ 语法查询。
递归的想法是每个级别都基于前一个级别构建。
CreateIndices(n)
在所有可用位置将元素添加n-1
到由 , 返回的排列中。CreateIndices(n-1)
递归的根是CreateIndices(0)
返回一个空的排列集。
一步一步解释:CreateIndices(3)
1. 让我们从创建结果开始CreateIndices(0)
:
2. 那么结果CreateIndices(1)
:
- 在位置 0 [ 0 ]将元素
0
(n-1) 添加到每个先前的排列
3. 那么结果CreateIndices(2)
1
在位置 0
[ 1, 0 ]将元素(n-1) 添加到每个先前的排列
1
在位置 1
[ 0, 1 ]将元素(n-1) 添加到每个先前的排列
4. 那么结果CreateIndices(3)
2
在位置 0
[ 2, 1, 0 ]
[ 2, 0, 1 ]将元素(n-1) 添加到每个先前的排列
2
在位置 1
[ 1, 2, 0 ]
[ 0, 2, 1 ]将元素(n-1) 添加到每个先前的排列
2
在位置 2
[ 1, 0, 2 ]
[ 0, 1, 2 ]将元素(n-1) 添加到每个先前的排列
接下来发生什么
现在我们有了每个排列的索引,我们可以使用它们来构建值的真实排列。这就是泛型Get
方法的作用。
另请注意,该Get
方法是将源序列具体化为数组的唯一方法。只是一个枚举器CreateIndices
,没有任何真实对象......所以您只需在枚举序列时支付成本,在调用时Get
您需要支付创建源序列数组的费用。
这解释了为什么在调用Get
示例之后,我必须具体化结果,以便我们可以使用它:
var items = new[] { "0", "1", "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
如果我们只列举一半的排列,这允许我们只支付一半的成本。