使用 LINQ 生成排列
我有一套必须安排的产品。有 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 });
}
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 });
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(8)
注意:比较器
请记住,此代码已有几年历史并且面向 .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();
}
}
我使用这个库进行组合,发现它效果很好。示例程序有点令人困惑,但文章解释了使用代码需要什么。
- 使用 C# 泛型进行排列、组合和变体
- 作者:Adrian Akison | 2008 年 5 月 23 日
- 讨论组合集合的六种主要类型,并提供示例和计数公式。使用基于 C# 泛型的类集进行扩展,用于枚举每个元集合。
- 插入自 http://www.codeproject.com/KB/recipes/Combinatorics.aspx
这是 C# 7 的简单排列扩展方法(值元组和内部方法)。它源自@AndrasVaas的答案,但仅使用单一级别的惰性(防止由于随着时间的推移而改变项目而导致的错误),失去了 IComparer 功能(我不需要它),并且长度要短一些。
public static class PermutationExtensions
{
/// <summary>
/// Generates permutations.
/// </summary>
/// <typeparam name="T">Type of items to permute.</typeparam>
/// <param name="items">Array of items. Will not be modified.</param>
/// <returns>Permutations of input items.</returns>
public static IEnumerable<T[]> Permute<T>(this T[] items)
{
T[] ApplyTransform(T[] values, (int First, int Second)[] tx)
{
var permutation = new T[values.Length];
for (var i = 0; i < tx.Length; i++)
permutation[i] = values[tx[i].Second];
return permutation;
}
void Swap<U>(ref U x, ref U y)
{
var tmp = x;
x = y;
y = tmp;
}
var length = items.Length;
// Build identity transform
var transform = new(int First, int Second)[length];
for (var i = 0; i < length; i++)
transform[i] = (i, i);
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-increasing) order
var decreasingpart = length - 2;
while (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
var greater = length - 1;
while (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);
}
}
}
- 创建另一个长度为 2^n 的数组,其中 n 是从 0 到 2^n 的二进制产品计数
- ,并用每个计数填充数组。例如,如果 n=3
该数组将如下所示:
000 001 010 011 100 101 110 111
- 循环遍历二进制数组并找到每个数字中的数字,然后将具有相同索引的乘积相加:
对于 ar{ 中的每个二进制数 对于 i = 0 到 n-1{ 如果二进制数(i) = 1 排列.add(产品(i)) } permunations.add(排列) }
例子:
如果 binaryNumber= 001 则排列 1 = 产品 1
如果 binaryNumber= 101 则排列 1 = 产品 3,产品 1
今天我偶然发现了这一点,并认为我可以分享我的实现。
对于 N 到 M 之间的所有整数,您必须首先创建一个数组:
IEnumerable<int> Range(int n, int m) {
for(var i = n; i < m; ++i) {
yield return i;
}
}
然后通过 Permutations(Range(1, 10)) 运行它:
enum PermutationsOption {
None,
SkipEmpty,
SkipNotDistinct
}
private IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> elements, PermutationsOption option = PermutationsOption.None, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
var elementsList = new List<IEnumerable<T>>();
var elementsIndex = 0;
var elementsCount = elements.Count();
var elementsLength = Math.Pow(elementsCount + 1, elementsCount);
if (option.HasFlag(PermutationsOption.SkipEmpty)) {
elementsIndex = 1;
}
if (elements.Count() > 0) {
do {
var elementStack = new Stack<T>();
for (var i = 0; i < elementsCount; ++i) {
var ind = (int)(elementsIndex / Math.Pow(elementsCount + 1, i) % (elementsCount + 1));
if (ind == 0) {
continue;
}
elementStack.Push(elements.ElementAt(ind - 1));
}
var elementsCopy = elementStack.ToArray() as IEnumerable<T>;
if (option.HasFlag(PermutationsOption.SkipNotDistinct)) {
elementsCopy = elementsCopy.Distinct();
elementsCopy = elementsCopy.ToArray();
if (elementsList.Any(p => CompareItemEquality(p, elementsCopy, equalityComparer))) {
continue;
}
}
elementsList.Add(elementsCopy);
} while (++elementsIndex < elementsLength);
}
return elementsList.ToArray();
}
private bool CompareItemEquality<T>(IEnumerable<T> elements1, IEnumerable<T> elements2, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
if (equalityComparer == null) {
equalityComparer = EqualityComparer<T>.Default;
}
return (elements2.Count() == elements2.Count()) && (elements2.All(p => elements1.Contains(p, equalityComparer)));
}
Lippert先生的答案的输出可以看作是4个槽中0和2之间元素的所有可能分布。
例如
0 3 1
读作“没有 0,三个 1 和一个 2”
这远不如利珀特先生的回答那么优雅,但至少效率不低
public static void Main()
{
var distributions = Distributions(4, 3);
PrintSequences(distributions);
}
/// <summary>
/// Entry point for the other recursive overload
/// </summary>
/// <param name="length">Number of elements in the output</param>
/// <param name="range">Number of distinct values elements can take</param>
/// <returns></returns>
static List<int[]> Distributions(int length, int range)
{
var distribution = new int[range];
var distributions = new List<int[]>();
Distributions(0, length, distribution, 0, distributions);
distributions.Reverse();
return distributions;
}
/// <summary>
/// Recursive methode. Not to be called directly, only from other overload
/// </summary>
/// <param name="index">Value of the (possibly) last added element</param>
/// <param name="length">Number of elements in the output</param>
/// <param name="distribution">Distribution among element distinct values</param>
/// <param name="sum">Exit condition of the recursion. Incremented if element added from parent call</param>
/// <param name="distributions">All possible distributions</param>
static void Distributions(int index,
int length,
int[] distribution,
int sum,
List<int[]> distributions)
{
//Uncomment for exactness check
//System.Diagnostics.Debug.Assert(distribution.Sum() == sum);
if (sum == length)
{
distributions.Add(distribution.Reverse().ToArray());
for (; index < distribution.Length; index++)
{
sum -= distribution[index];
distribution[index] = 0;
}
return;
}
if (index < distribution.Length)
{
Distributions(index + 1, length, distribution, sum, distributions);
distribution[index]++;
Distributions(index, length, distribution, ++sum, distributions);
}
}
static void PrintSequences(List<int[]> distributions)
{
for (int i = 0; i < distributions.Count; i++)
{
for (int j = distributions[i].Length - 1; j >= 0; j--)
for (int k = 0; k < distributions[i][j]; k++)
Console.Write("{0:D1} ", distributions[i].Length - 1 - j);
Console.WriteLine();
}
}
public static IList<IList<T>> Permutation<T>(ImmutableList<ImmutableList<T>> dimensions)
{
IList<IList<T>> result = new List<IList<T>>();
Step(ImmutableList.Create<T>(), dimensions, result);
return result;
}
private static void Step<T>(ImmutableList<T> previous,
ImmutableList<ImmutableList<T>> rest,
IList<IList<T>> result)
{
if (rest.IsEmpty)
{
result.Add(previous);
return;
}
var first = rest[0];
rest = rest.RemoveAt(0);
foreach (var label in first)
{
Step(previous.Add(label), rest, result);
}
}
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
如果我理解这个问题:您正在寻找长度为 P 的所有整数序列,其中集合中的每个整数都在 0 和 T 之间,并且该序列是单调非递减。这是正确的吗?
使用迭代器块编写这样的程序非常简单:
它会产生所需的输出:从 0 到 2 绘制长度为 4 的非递减序列。
请注意,用于连接的多重嵌套迭代器的用法是 效率不高,但谁在乎呢?您已经生成了指数数量的序列,因此生成器中存在多项式效率低下的事实基本上是无关紧要的。
方法 M 生成长度为 p 的所有单调非递减整数序列,其中整数在 t1 和 t2 之间。它使用简单的递归来递归地执行此操作。基本情况是恰好存在一个长度为零的序列,即空序列。递归情况是,为了计算,假设 P = 3、t1 = 0、t2 = 2,您需要计算:
这就是结果。
或者,您可以在主递归方法中使用查询理解而不是迭代器块:
这基本上做同样的事情;它只是将循环移至 SelectMany 方法中。
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:
Which produces the desired output: nondecreasing sequences of length 4 drawn from 0 through 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:
And that's the result.
Alternatively, you could use query comprehensions instead of iterator blocks in the main recursive method:
That does basically the same thing; it just moves the loops into the SelectMany method.