c# - 使用 LINQ 生成排列

Question

我有一组必须安排的产品。有 P 个产品，每个产品的索引从 1 到 P。每个产品都可以安排到 0 到 T 的时间段。我需要构建满足以下约束的产品计划的所有排列:

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

我正在努力构建迭代器。我知道当产品数量是已知常量时如何通过 LINQ 执行此操作，但我不确定当产品数量是输入参数时如何生成此查询。

理想情况下，我想使用 yield 语法来构造此迭代器。

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

编辑:当 _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 });
}

Answer 1

如果我理解这个问题:你正在寻找长度为 P 的所有整数序列，其中集合中的每个整数都在 0 和 T 之间，并且序列是单调非递减。对吗？

使用迭代器 block 编写这样的程序很简单:

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

这会产生所需的输出:从 0 到 2 绘制的长度为 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

请注意，用于串联的多重嵌套迭代器的用法是 not very efficient ， 但谁在乎？您已经在生成指数数量的序列，因此生成器中存在多项式低效率这一事实基本上是无关紧要的。

方法 M 生成长度为 p 的所有单调非递减整数序列，其中整数介于 t1 和 t2 之间。它递归地这样做，使用一个简单的递归。基本情况是只有一个长度为零的序列，即空序列。递归的情况是，为了计算，比如说 P = 3，t1 = 0，t2 = 2，你计算:

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

这就是结果。

或者，您可以在主递归方法中使用查询推导式而不是迭代器 block :

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

这基本上是一样的；它只是将循环移动到 SelectMany 方法中。