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.