使用LINQ生成置换 [英] Generating Permutations using LINQ
问题描述
我有一组必须安排产品。有每个索引从1 p系列产品设为P.每个产品可以安排成一个时间段0到T我需要构造产品时间表满足以下约束的所有排列：
如果p1.Index＆GT; p2.Index然后p1.Schedule＆GT; = p2.Schedule。
我奋力构建迭代器。我知道如何通过LINQ做到这一点，当产品的数量是一个已知常量，但我不知道如何生成此查询时，产品的数量是输入参数。
理想我想用产量的语法来构建这个迭代器。
公共类PotentialSchedule（）
{
公共PotentialSchedule（INT [] schedulePermutation）
{
_schedulePermutation = schedulePermutation;
}
私人只读INT [] _schedulePermutation;
}
私人INT _numberProducts = ...;
公众的IEnumerator＆LT; PotentialSchedule＆GT;的GetEnumerator（）
{
INT [] =置换新INT [_numberProducts]
//这里生成所有排列组合 - 怎么样？
产量返回新PotentialSchedule（置换）;
}
编辑：例如，当_numberProducts = 2
公开的IEnumerable＆LT; PotentialSchedule＆GT;的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＆LT; T＆GT; prePEND＆LT; T＆GT;（T第一，IEnumerable的＆LT; T＆GT;休息）
{
第一个产生回报;
的foreach（静止无功项）
产生回报的项目;
} 静态的IEnumerable＆LT;＆IEnumerable的LT; INT＆GT;＆GT; M（INT P，INT T1，T2 INT）
{
如果（P == 0）
产量返回Enumerable.Empty＆LT;＆诠释GT;（）;
其他
对于（INT第一= T1;第一＆LT; = 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＆LT; T＆GT;辛格尔顿＆LT; T＆GT;（T第一）
{
第一个产生回报;
}静态的IEnumerable＆LT;＆IEnumerable的LT; INT＆GT;＆GT; M（INT P，INT T1，T2 INT）
{
返回p == 0？ 辛格尔顿（Enumerable.Empty＆LT; INT＆GT;（））： 从第一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生成置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
