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

单线解决方案,无递归

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

我不得不使用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 ]

它是一种递归方法,仅基于可枚举扩展和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 elements
var result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations
    ).ToArray(); // pay to get the permutations

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