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

Question

我试图编写一个方法,尽可能简单地返回给定枚举的排列.代码:

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#字符串排列

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

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

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

如何只通过一次交换来交换枚举项？

但我想这不是问题..)

Answer 1

编辑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(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, 1, 0 ]
  [ 2, 0, 1 ]
• 将元素2(n-1) 添加到每个先前排列的位置 1
  [ 1, 2, 0 ]
  [ 0, 2, 1 ]
• 将元素2(n-1) 添加到每个先前排列的位置 2
  [ 1, 0, 2 ]
  [ 0, 1, 2 ]

接下来发生什么

现在我们有了每个排列的索引，我们可以使用它们来构建值的真实排列。这就是泛型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

如果我们只枚举一半的排列，这使得我们只需支付一半的成本。