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

前端之家收集整理的这篇文章主要介绍了c# – 如何使用查询语法创建排列?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我试图编写一个方法,尽可能简单地返回给定枚举的排列.代码
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# String permutation

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

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

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

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

但我想这不是问题..)

解决方法

编辑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(),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

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

猜你在找的C#相关文章