cor*_*erm 13 c# linq permutation
我有一套必须安排的产品.有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 });
}
Eri*_*ert 52
如果我理解这个问题:你正在寻找长度为P的所有整数序列,其中集合中的每个整数都在0和T之间,并且序列是单调非减少的.那是对的吗？
使用迭代器块编写这样的程序很简单:
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
请注意,使用多重嵌套迭代器进行连接不是很有效,但是谁在乎呢？您已经在生成指数数量的序列,因此生成器中存在多项式低效的事实基本上是无关紧要的.
方法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.
这就是结果.
或者,您可以在主递归方法中使用查询推导而不是迭代器块:
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方法中.
注意:Comparer <T>完全是可选的.如果您提供一个,则排列将按词汇顺序返回.如果不这样做,但原始项目是按顺序排列的,它仍将按词汇顺序枚举.Ian Griffiths在6年前使用更简单的算法(据我记得不会进行词汇排序)玩这个:http://www.interact-sw.co.uk/iangblog/2004/09/16/ permuterate.
请记住,这段代码已经存在了几年,目标是.NET 2.0,因此没有扩展方法等(但应该很容易修改).
它使用Knuth称为"算法L"的算法.它是非递归的,快速的,并且在C++标准模板库中使用.
static partial class Permutation
{
/// <summary>
/// Generates permutations.
/// </summary>
/// <typeparam name="T">Type of items to permute.</typeparam>
/// <param name="items">Array of items. Will not be modified.</param>
/// <param name="comparer">Optional comparer to use.
/// If a <paramref name="comparer"/> is supplied,
/// permutations will be ordered according to the
/// <paramref name="comparer"/>
/// </param>
/// <returns>Permutations of input items.</returns>
public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items, IComparer<T> comparer)
{
int length = items.Length;
IntPair[] transform = new IntPair[length];
if (comparer == null)
{
//No comparer. Start with an identity transform.
for (int i = 0; i < length; i++)
{
transform[i] = new IntPair(i, i);
};
}
else
{
//Figure out where we are in the sequence of all permutations
int[] initialorder = new int[length];
for (int i = 0; i < length; i++)
{
initialorder[i] = i;
}
Array.Sort(initialorder, delegate(int x, int y)
{
return comparer.Compare(items[x], items[y]);
});
for (int i = 0; i < length; i++)
{
transform[i] = new IntPair(initialorder[i], i);
}
//Handle duplicates
for (int i = 1; i < length; i++)
{
if (comparer.Compare(
items[transform[i - 1].Second],
items[transform[i].Second]) == 0)
{
transform[i].First = transform[i - 1].First;
}
}
}
yield return ApplyTransform(items, transform);
while (true)
{
//Ref: E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997
//Find the largest partition from the back that is in decreasing (non-icreasing) order
int decreasingpart = length - 2;
for (;decreasingpart >= 0 &&
transform[decreasingpart].First >= transform[decreasingpart + 1].First;
--decreasingpart) ;
//The whole sequence is in decreasing order, finished
if (decreasingpart < 0) yield break;
//Find the smallest element in the decreasing partition that is
//greater than (or equal to) the item in front of the decreasing partition
int greater = length - 1;
for (;greater > decreasingpart &&
transform[decreasingpart].First >= transform[greater].First;
greater--) ;
//Swap the two
Swap(ref transform[decreasingpart], ref transform[greater]);
//Reverse the decreasing partition
Array.Reverse(transform, decreasingpart + 1, length - decreasingpart - 1);
yield return ApplyTransform(items, transform);
}
}
#region Overloads
public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items)
{
return Permute(items, null);
}
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items, IComparer<T> comparer)
{
List<T> list = new List<T>(items);
return Permute(list.ToArray(), comparer);
}
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items)
{
return Permute(items, null);
}
#endregion Overloads
#region Utility
public static IEnumerable<T> ApplyTransform<T>(
T[] items,
IntPair[] transform)
{
for (int i = 0; i < transform.Length; i++)
{
yield return items[transform[i].Second];
}
}
public static void Swap<T>(ref T x, ref T y)
{
T tmp = x;
x = y;
y = tmp;
}
public struct IntPair
{
public IntPair(int first, int second)
{
this.First = first;
this.Second = second;
}
public int First;
public int Second;
}
#endregion
}
class Program
{
static void Main()
{
int pans = 0;
int[] digits = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (var p in Permutation.Permute(digits))
{
pans++;
if (pans == 720) break;
}
sw.Stop();
Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
Console.ReadKey();
}
}
我使用这个库进行组合,发现它运行良好.示例程序有点令人困惑,但文章解释了使用代码所需的内容.