使用LINQ生成置换

使用LINQ生成置换

本文介绍了使用LINQ生成置换的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一组必须安排产品。有每个索引从1 p系列产品设为P.每个产品可以安排成一个时间段0到T我需要构造产品时间表满足以下约束的所有排列:

 如果p1.Index> p2.Index然后p1.Schedule> = p2.Schedule。

我奋力构建迭代器。我知道如何通过LINQ做到这一点,当产品的数量是一个已知常量,但我不知道如何生成此查询时,产品的数量是输入参数。

理想我想用产量的语法来构建这个迭代器。

 公共类PotentialSchedule()
{
      公共PotentialSchedule(INT [] schedulePermutation)
      {
             _schedulePermutation = schedulePermutation;
      }
      私人只读INT [] _​​schedulePermutation;
}
私人INT _numberProducts = ...;
公众的IEnumerator< PotentialSchedule>的GetEnumerator()
{
     INT [] =置换新INT [_numberProducts]
     //这里生成所有排列组合 - 怎么样?
     产量返回新PotentialSchedule(置换);
}

编辑:例如,当_numberProducts = 2

 公开的IEnumerable< PotentialSchedule>的GetEnumerator()
{
    VAR的查询=从P1在Enumerable.Range(0,T)
                从在Enumerable.Range P2(P2,T)的
                选择新{P1 = P1,P2 = P2};    的foreach(查询VAR结果)
          产量返回新PotentialSchedule(新INT [] {result.P1,result.P2});
}


解决方案

如果我明白的问题:你正在寻找的长度P,其中组中的每个整数为0和T之间的整数所有序列,序列是的单调非减的。这是否正确?

编写这样使用迭代器阻止程序很简单:

 使用系统;
使用System.Collections.Generic;
使用System.Linq的;静态类节目
{
    静态的IEnumerable< T> prePEND< T>(T第一,IEnumerable的< T>休息)
    {
        第一个产生回报;
        的foreach(静止无功项)
            产生回报的项目;
    }    静态的IEnumerable<&IEnumerable的LT; INT>> M(INT P,INT T1,T2 INT)
    {
        如果(P == 0)
            产量返回Enumerable.Empty<&诠释GT;();
        其他
            对于(INT第一= T1;第一< = T2 ++第一)
                的foreach(VAR休息M(对 - 1,首先,T2))
                    产量返回prePEND(第一,休息);
    }    公共静态无效的主要()
    {
        的foreach(在M(4,0变种序列,2))
            Console.WriteLine(的string.join(,,序列));
    }
}

其中产生所需的输出:通过2非降从0拉伸长度为4的序列

  0,0,0,0
0,0,0,1
0,0,0,2
0,0,1,1
0,0,1,2
0,0,2,2
0,1,1,1
0,1,1,2
0,1,2,2
0,2,2,2
1,1,1,1
1,1,1,2
1,1,2,2-
1,2,2,2-
2,2,2,2-

需要注意的是乘法嵌套迭代器连接时将使用是的,但谁在乎呢?你已经是产生的指数数字序列,因此,有一个多项式的事实在发电机效率基本上是无关紧要的。

的子程序M生成长度为p的整数,其中整数是t1和t2之间的所有单调非减的序列。它这样做递归,用一个简单的递归。基础案例是,有长度为零,即空序列的正好一个序列。递归情况下是,在为了计算,假设P = 3中,t1 = 0,T2 = 2,则计算:

   - 所有序列从0开始后跟0绘制2长度为2的序列。
- 从1开始的所有序列随后绘制从1到2长度为2的序列。
- 从2的所有序列随后绘制从2到2长度为2的序列。

这就是结果。

另外,你可以使用查询COM prehensions而不是迭代器块的主要递归方法:

 静态的IEnumerable< T>辛格尔顿< T>(T第一)
{
    第一个产生回报;
}静态的IEnumerable<&IEnumerable的LT; INT>> M(INT P,INT T1,T2 INT)
{
    返回p == 0?        辛格尔顿(Enumerable.Empty< INT>()):        从第一Enumerable.Range(T1,T2 - T1 + 1)
        从静止并购(P - 1,首先,T2)
        选择prePEND(第一,休息);
}

这基本上做同样的事情;它只是移动循环到方法的SelectMany

I have a set of products that must be scheduled. There are P products each indexed from 1 to P. Each product can be scheduled into a time period 0 to T. I need to construct all permutations of product schedules that satisfy the following constraint:

If p1.Index > p2.Index then p1.Schedule >= p2.Schedule.

I am struggling to construct the iterator. I know how to do this via LINQ when the number of products is a known constant, but am not sure how to generate this query when the number of products is an input parameter.

Ideally I would like to use the yield syntax to construct this iterator.

public class PotentialSchedule()
{
      public PotentialSchedule(int[] schedulePermutation)
      {
             _schedulePermutation = schedulePermutation;
      }
      private readonly int[] _schedulePermutation;
}


private int _numberProducts = ...;
public IEnumerator<PotentialSchedule> GetEnumerator()
{
     int[] permutation = new int[_numberProducts];
     //Generate all permutation combinations here -- how?
     yield return new PotentialSchedule(permutation);
}

EDIT: Example when _numberProducts = 2

public IEnumerable<PotentialSchedule> GetEnumerator()
{
    var query = from p1 in Enumerable.Range(0,T)
                from p2 in Enumerable.Range(p2,T)
                select new { P1 = p1, P2 = p2};

    foreach (var result in query)
          yield return new PotentialSchedule(new int[] { result.P1, result.P2 });
}
解决方案

If I understand the question: you are looking for all sequences of integers of length P, where each integer in the set is between 0 and T, and the sequence is monotone nondecreasing. Is that correct?

Writing such a program using iterator blocks is straightforward:

using System;
using System.Collections.Generic;
using System.Linq;

static class Program
{
    static IEnumerable<T> Prepend<T>(T first, IEnumerable<T> rest)
    {
        yield return first;
        foreach (var item in rest)
            yield return item;
    }

    static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
    {
        if (p == 0)
            yield return Enumerable.Empty<int>();
        else
            for (int first = t1; first <= t2; ++first)
                foreach (var rest in M(p - 1, first, t2))
                    yield return Prepend(first, rest);
    }

    public static void Main()
    {
        foreach (var sequence in M(4, 0, 2))
            Console.WriteLine(string.Join(", ", sequence));
    }
}

Which produces the desired output: nondecreasing sequences of length 4 drawn from 0 through 2.

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 1, 1
0, 0, 1, 2
0, 0, 2, 2
0, 1, 1, 1
0, 1, 1, 2
0, 1, 2, 2
0, 2, 2, 2
1, 1, 1, 1
1, 1, 1, 2
1, 1, 2, 2
1, 2, 2, 2
2, 2, 2, 2

Note that the usage of multiply-nested iterators for concatenation is not very efficient, but who cares? You already are generating an exponential number of sequences, so the fact that there's a polynomial inefficiency in the generator is basically irrelevant.

The method M generates all monotone nondecreasing sequences of integers of length p where the integers are between t1 and t2. It does so recursively, using a straightforward recursion. The base case is that there is exactly one sequence of length zero, namely the empty sequence. The recursive case is that in order to compute, say P = 3, t1 = 0, t2 = 2, you compute:

- all sequences starting with 0 followed by sequences of length 2 drawn from 0 to 2.
- all sequences starting with 1 followed by sequences of length 2 drawn from 1 to 2.
- all sequences starting with 2 followed by sequences of length 2 drawn from 2 to 2.

And that's the result.

Alternatively, you could use query comprehensions instead of iterator blocks in the main recursive method:

static IEnumerable<T> Singleton<T>(T first)
{
    yield return first;
}

static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
{
    return p == 0 ?

        Singleton(Enumerable.Empty<int>()) :

        from first in Enumerable.Range(t1, t2 - t1 + 1)
        from rest in M(p - 1, first, t2)
        select Prepend(first, rest);
}

That does basically the same thing; it just moves the loops into the SelectMany method.

这篇关于使用LINQ生成置换的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 10:02