Creating permutations using LINQ

Question

I have a set of products that should be planned. There are P products, each of which is indexed from 1 to P. Each product can be scheduled for a period of time from 0 to T. I need to build all permutations of product schedules that satisfy the following restriction:

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

I am trying to build an iterator. I know how to do this through LINQ when the number of products is a known constant, but I'm not sure how to generate this query when the number of products is an input parameter.

Ideally, I would like to use yield syntax to build 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 }); } 

Answer 1

If I understand the question: are you looking for all sequences of integers of length P, where each integer in the set is between 0 and T, and the sequence is monotonically non-decreasing. It is right?

Writing such a program using iterator blocks is simple:

 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 gives the desired result: non-decreasing sequences of length 4, taken from 0 to 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 

Please note that using multi-threaded iterators for concatenation is not very efficient , but who cares? You already generate the number of exponential sequences, so the fact of the absence of a polynomial in the generator does not matter.

Method M generates all monotone non-decreasing sequences of integers p, where integers are between t1 and t2. It does this recursively using direct recursion. The main case is that there is exactly one sequence of zero length, namely an empty sequence. The recursive case is that to calculate, say, P = 3, t1 = 0, t2 = 2, you calculate:

 - 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 what a result.

Alternatively, you can use query understanding 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); } 

It is basically the same; it just moves the loops into the SelectMany method.

Answer 2

Note: Comparer <T> is completely optional. If you provide it, permutations will be returned in lexical order. If you do not, but the source elements are ordered, it will still be listed in lexical order. Ian Griffiths played with this 6 years ago using a simpler algorithm (which, as far as I remember, does not perform lexical ordering): http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate .

Keep in mind that this code is several years old and it targets .NET 2.0, so no extension methods and the like (but should be trivial to change).

It uses an algorithm that Knut calls the "L algorithm." It is non-recursive, fast, and is used in the standard C ++ template library.

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

Answer 3

I used this library for combinations and found that it works well. The sample program is a bit confusing, but the article explains what is needed to use the code.

• Permutations, combinations, and variations using common C # features
• Adrian Akison | May 23, 2008
• Discusses six basic types of combinatorial collections with examples and formulas for counting. Extends with a set of classes based on C # Generics to enumerate each meta collection.
• Insert from http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 4

• create another array of length 2 ^ n, where n is the number of products
• calculate in binary format from 0 to 2 ^ n and fill the array with each quantity. for example, if n = 3, the array would look like this:

000 001 010 011 100 101 110 111

• go through the binary array and find them in each number, then add the product with the same index:

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

Example: if binaryNumber = 001, then permunation1 = product1 if binaryNumber = 101, then permunation1 = product3, product1

Answer 5

It uses a simple substitution extension method for C # 7 (tuple values ​​and internal methods). It is derived from the @AndrasVaas answer , but uses only one level of laziness (preventing errors due to mutating elements over time), loses the IComparer function (I didn 'need it), and it will be a little shorter.

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

Today I came across this and thought that I could share my implementation.

For all integers between N and M, you must first create an array:

 IEnumerable<int> Range(int n, int m) { for(var i = n; i < m; ++i) { yield return i; } } 

and run it through 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))); } 

Answer 7

The result of Mr. Lippert's answer can be considered as all possible distributions of elements among 0 and 2 in 4 slots.
for example
0 3 1
reads "no 0, three 1 and one 2"
It’s nowhere more elegant than Mr. Lippert’s answer, but at least no less effective.

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

Answer 8

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