使用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 GetEnumerator() { int[] permutation = new int[_numberProducts]; //Generate all permutation combinations here -- how? yield return new PotentialSchedule(permutation); } 

编辑：_numberProducts = 2时的示例

 public IEnumerable 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之间，并且序列是单调的非递减 。 那是对的吗？

使用迭代器块编写这样的程序非常简单：

 using System; using System.Collections.Generic; using System.Linq; static class Program { static IEnumerable Prepend(T first, IEnumerable rest) { yield return first; foreach (var item in rest) yield return item; } static IEnumerable> M(int p, int t1, int t2) { if (p == 0) yield return Enumerable.Empty(); 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 Singleton(T first) { yield return first; } static IEnumerable> M(int p, int t1, int t2) { return p == 0 ? Singleton(Enumerable.Empty()) : from first in Enumerable.Range(t1, t2 - t1 + 1) from rest in M(p - 1, first, t2) select Prepend(first, rest); } 

这基本上是一回事; 它只是将循环移动到SelectMany方法中。

Answer 2

我使用这个库进行组合，发现它运行良好。 示例程序有点令人困惑，但文章解释了使用代码需要什么。

• 使用C＃generics的排列，组合和变体
• 作者：Adrian Akison | 2008年5月23日
• 讨论六种主要类型的组合集合，包括计数的示例和公式。 使用基于C＃Generics的类扩展，以枚举每个元集合。
• 插入自http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 3

注意：Comparer 完全是可选的。 如果您提供一个，则排列将按词汇顺序返回。 如果您没有，但原始项目已订购，它仍将按词汇顺序列举。 Ian Griffiths在6年前使用更简单的算法（就我记忆而言，没有进行词汇排序）玩这个： http ： //www.interact-sw.co.uk/iangblog/2004/09/16/ permuterate 。

请记住，这段代码已经存在了几年，目标是.NET 2.0，所以没有扩展方法之类的东西（但是应该很容易修改）。

它使用Knuth称为“算法L”的算法 。 它是非递归的，快速的，并且在C ++标准模板库中使用。

 static partial class Permutation { /// 
 /// Generates permutations. /// 
 /// Type of items to permute. /// Array of items. Will not be modified. /// Optional comparer to use. /// If a  is supplied, /// permutations will be ordered according to the ///  ///  /// Permutations of input items. public static IEnumerable> Permute(T[] items, IComparer 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: EW 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> Permute(T[] items) { return Permute(items, null); } public static IEnumerable> Permute(IEnumerable items, IComparer comparer) { List list = new List(items); return Permute(list.ToArray(), comparer); } public static IEnumerable> Permute(IEnumerable items) { return Permute(items, null); } #endregion Overloads #region Utility public static IEnumerable ApplyTransform( T[] items, IntPair[] transform) { for (int i = 0; i < transform.Length; i++) { yield return items[transform[i].Second]; } } public static void Swap(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(); } } 

Answer 4

1. 创建另一个长度为2 ^ n的数组，其中n是产品数量
2. 从0到2 ^ n的二进制计数，并用每个计数填充数组。 例如，如果n = 3，则数组将如下所示：

000 001 010 011 100 101 110 111

1. 循环遍历二进制数组并找到每个数字中的数字，然后添加具有相同索引的产品：

  for each binaryNumber in ar{ for i = 0 to n-1{ if binaryNumber(i) = 1 permunation.add(products(i)) } permunations.add(permutation) } 

例如：如果binaryNumber = 001则permunation1 = product1如果binaryNumber = 101则permunation1 = product3，product1

Answer 5

这是C＃7（值元组和内部方法）的简单置换扩展方法。 它来自@AndrasVaas的答案 ，但只使用一个级别的懒惰（防止因项目随时间变化而导致的错误），丢失IComparerfunction（我不需要它），并且相当短。

 public static class PermutationExtensions { /// 
 /// Generates permutations. /// 
 /// Type of items to permute. /// Array of items. Will not be modified. /// Permutations of input items. public static IEnumerable Permute(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(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: EW 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); } } } 

Answer 6

今天我偶然发现了这一点，并认为我可以分享我的实施。

对于N和M之间的所有整数，您必须首先创建一个数组：

 IEnumerable 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> Permutations(IEnumerable elements, PermutationsOption option = PermutationsOption.None, IEqualityComparer equalityComparer = default(IEqualityComparer)) { var elementsList = new List>(); 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(); 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; 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(IEnumerable elements1, IEnumerable elements2, IEqualityComparer equalityComparer = default(IEqualityComparer)) { if (equalityComparer == null) { equalityComparer = EqualityComparer.Default; } return (elements2.Count() == elements2.Count()) && (elements2.All(p => elements1.Contains(p, equalityComparer))); } 

Answer 7

Lippert先生的回答可以看作是4个时段中0和2之间所有可能的元素分布。
例如
0 3 1
读为“没有0，三个1和一个2”
这远不如Lippert先生的答案那么优雅，但至少效率不高

 public static void Main() { var distributions = Distributions(4, 3); PrintSequences(distributions); } /// 
 /// Entry point for the other recursive overload /// 
 /// Number of elements in the output /// Number of distinct values elements can take ///  static List Distributions(int length, int range) { var distribution = new int[range]; var distributions = new List(); Distributions(0, length, distribution, 0, distributions); distributions.Reverse(); return distributions; } /// 
 /// Recursive methode. Not to be called directly, only from other overload /// 
 /// Value of the (possibly) last added element /// Number of elements in the output /// Distribution among element distinct values /// Exit condition of the recursion. Incremented if element added from parent call /// All possible distributions static void Distributions(int index, int length, int[] distribution, int sum, List 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 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(); } } 

Answer 8

  public static IList> Permutation(ImmutableList> dimensions) { IList> result = new List>(); Step(ImmutableList.Create(), dimensions, result); return result; } private static void Step(ImmutableList previous, ImmutableList> rest, IList> 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); } }