Generating Permutations using LINQ

Question

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

Answer 1

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.

Answer 2

Note: the Comparer<T> is entirely optional. If you provide one, the permutations will be returned in lexical order. If you don't, but the original items are ordered, it will still enumerate in lexical order. Ian Griffiths played with this 6 years ago, using a simpler algo (that does not do lexical ordering, as far as I remember): http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate.

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

It uses the algorithm that Knuth calls "Algorithm L". It is non-recursive, fast, and is used in the C++ Standard 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: 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();
    }
}

Answer 3

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

• Permutations, Combinations, and Variations using C# Generics
• By Adrian Akison | 23 May 2008
• Discusses the six major types of combinatorial collections, with examples and formulas for counting. Expands with a C# Generics-based set of classes for enumerating each meta-collection.
• Inserted from http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 4

Here's a simple permutation extension method for C# 7 (value tuples and inner methods). It's derived from @AndrasVaas's answer, but uses only a single level of laziness (preventing bugs due to mutating items over time), loses the IComparer feature (I didn't need it), and is a fair bit 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: 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);
        }
    }
}

Answer 5

1. create another array of length 2^n where n is the number of products
2. count in binary from 0 to 2^n and fill in the array with each count. for example if n=3 the array will look like this :

000 001 010 011 100 101 110 111

1. loop through the binary array and find the ones 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 6

Today I stumbled upon this and figured I could share my implementation.

For all integers between N and M you have to make an array first:

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 output from the answer of Mr Lippert can be seen as all the possible distributions of elements among 0 and 2 in 4 slots.
For instance
0 3 1
reads as "no 0, three 1 and one 2"
This is nowhere near as elegant as the answer of Mr Lippert, but at least not less efficient

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