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

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
    }
}

由于代码在迭代器 block 中得到了简化，我试图使其成为简单的 LINQ 查询表达式。

在嵌套的foreach 中有一个递归与此代码，甚至在foreach 之外的另一个可能产生；这是我用查询语法重写它的困难部分。

我读过这个答案:

C# String permutation

但我想这不是我的解决方案..

我试过各种方法，觉得做起来不是那么容易。我怎样才能完成它？

(Exchange 方法是另一个问题，我问了一个问题:

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

但我想这不是这里的问题..)

Answer 1

由于您正在寻找一个利用现有 LINQ 查询运算符而不是使用迭代器 block 的答案，这里有一个。请注意，它不会像其他一些解决方案那样有效；这些查询运算符的使用效率不如 Eric Lippert 的解决方案。 (虽然它短了很多。)

另请注意，由于此解决方案使用接受索引的 SelectMany 和 Where 的重载，因此需要使用方法语法而不是查询语法来调用这些运算符，并且其他几个运算符没有等效的查询语法。我可以将 Select 更改为查询语法，但为了保持一致性我没有这样做。

public static IEnumerable<IEnumerable<T>> Permuatations<T>(
    this IEnumerable<T> source)
{
    var list = source.ToList();//becase we iterate it multiple times
    return list.SelectMany((item, i) => list.Where((_, index) => index != i)
            .Permuatations()
            .Select(subsequence => new[] { item }.Concat(subsequence)))
        .DefaultIfEmpty(Enumerable.Empty<T>());
}

所以，谈谈它在做什么。

首先它遍历源序列；对于该序列中的每个项目，它都会创建一个与源序列类似的序列，但会删除“当前项目”。 (这是 list.Where 方法)。

接下来它(递归地)获取该子序列的所有排列。

之后，它将“删除”的项目添加到每个子序列的开头。

所有这些子序列都被压平在一起，因为它们都在 SelectMany 中。

DefaultIfEmpty 用于确保外部序列永远不会为空。置换一个空序列会产生一个内部有一个空序列的序列。这是递归操作的有效“基本情况”。