How to use query syntax to create permutations?

Question

I've tried to write a method which returns the permutation of a given enumerable as simple as possible. The code:

using System.Collections.Generic;

public static partial class Permutable {
    static IEnumerable<IEnumerable<T>> PermuteIterator<T>(
        IEnumerable<T> source, int offset) {
        var count=0;

        foreach(var dummy in source)
            if(++count>offset)
                foreach(
                    var sequence in
                        Permutable.PermuteIterator(
                            source.Exchange(offset, count-1), 1+offset)
                    )
                    yield return sequence;

        if(offset==count-1)
            yield return source;
    }

    public static IEnumerable<IEnumerable<T>> AsPermutable<T>(
        this IEnumerable<T> source) {
        return Permutable.PermuteIterator(source, 0);
    }

    public static IEnumerable<T> Exchange<T>(
        this IEnumerable<T> source, int index1, int index2) {
        // exchange elements at index1 and index2
    }
}

As the code has simplified within the iterator block, I'm trying to make it simply a single query expression of LINQ.

There's a recursion in the nested foreach with this code, even another possibly yield outside the foreach; and which is the difficult part for me to rewrite it in query syntax.

I've read this answer:

C# String permutation

But I guess it's not the solution for me ..

I tried various ways, and think it's not so easy to do. How can I get it done?

(The Exchange method is another problem, and I've asked a question:

How to exchange the items of enumeration by interating only once?

But I guess it's not the matter here .. )

Answer 1

Since you're looking for an answer that leverages the existing LINQ query operators, rather than using iterator blocks, here's one. Note that it won't be as efficient as some other solutions; the use of these query operators isn't as efficient as, say Eric Lippert's solution. (It is a lot shorter though.)

Also note that since this solution uses the overloads of SelectMany and Where that accept an index, those operators need to be called using method syntax, not query syntax, and several of the other operators don't have query syntax equivalents. I could change the one Select into query syntax, but for consistencies sake I did not.

public static IEnumerable<IEnumerable<T>> Permuatations<T>(
    this IEnumerable<T> source)
{
    var list = source.ToList();//becase we iterate it multiple times
    return list.SelectMany((item, i) => list.Where((_, index) => index != i)
            .Permuatations()
            .Select(subsequence => new[] { item }.Concat(subsequence)))
        .DefaultIfEmpty(Enumerable.Empty<T>());
}

So, to talk through what this is doing.

First it goes through the source sequence; for each item in that sequence it creates a sequence that is just like the source sequence but with the "current item" taken out. (This is the list.Where method).

Next it (recursively) gets all of the permutations of that subsequence.

After that it prepends the "removed" item to the beginning of each of those subsequences.

All of these subsequences are flattened together as they are all inside the SelectMany.

The DefaultIfEmpty is there to ensure that the outer sequence is never empty. Permuting an empty sequence results in a sequence with an empty sequence inside of it. This is effective the "base case" of the recursive operation.

Answer 2

EDIT 1:

Single-line solution without recursions

I have recreated the core method (from the Previous Solution below in this answer), so that now it is not recursive anymore. It is now easy to make a single-line solution from this.

I had to use Enumerable methods and extension methods to do it though. Without these, I think it is impossible to do this.

class Permutator
{
    private static IEnumerable<IEnumerable<int>> CreateIndices(int length)
    {
        var factorial = Enumerable.Range(2, length - 1)
            .Aggregate((a, b) => a * b);

        return (from p in Enumerable.Range(0, factorial)
                // creating module values from 2 up to length
                // e.g. length = 3: mods = [ p%2, p%3 ]
                // e.g. length = 4: mods = [ p%2, p%3, p%4 ]
                let mods = Enumerable.Range(2, length - 1)
                    .Select(m => p % m).ToArray()
                select (
                    // creating indices for each permutation
                    mods.Aggregate(
                        new[] { 0 },
                        (s, i) =>
                            s.Take(i)
                            .Concat(new[] { s.Length })
                            .Concat(s.Skip(i)).ToArray())
                    ));
    }

    public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
    {
        var array = items.ToArray();
        return from indices in CreateIndices(array.Length)
                select (from i in indices select array[i]);
    }
}

Now the final solution

The resulting thing is this monstrosity:

class Permutator
{
    public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
    {
        return
            from p in Enumerable.Range(0,
                Enumerable.Range(2, items.Count() - 1)
                    .Aggregate((a, b) => a * b))
            let mods = Enumerable.Range(2, items.Count() - 1)
                .Select(m => p % m).ToArray()
            select mods.Aggregate(
                items.Take(1).ToArray(),
                (s, i) =>
                    s.Take(i)
                    .Concat(items.Skip(s.Length).Take(1))
                    .Concat(s.Skip(i)).ToArray());
    }
}

Previous solution

I have created something that might be what you are looking for:

class Permutator
{
    private static IEnumerable<IEnumerable<int>> CreateIndices(int length)
    {
        return (from p in Enumerable.Range(0, length)
                select (
                    from s in Permutator.CreateIndices(length - 1)
                              .DefaultIfEmpty(Enumerable.Empty<int>())
                    select s.Take(p)
                           .Concat(new[] { length - 1 })
                           .Concat(s.Skip(p))
                    ))
                    .SelectMany(i => i);
    }

    public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
    {
        var array = items.ToArray();
        return from indices in CreateIndices(array.Length)
                select (from i in indices select array[i]);
    }
}

Example of how to use it:

var items = new[] { "0", "1", "2" };
var p = Permutator.Get(items);
var result = p.Select(a=>a.ToArray()).ToArray();

How it works

The core is the CreateIndices method. It creates a sequence that contains the indices of the source elements, for each permutation.

It is best to explain with an example:

CreateIndices(0);
// returns no permutations

CreateIndices(1);
// returns 1 permutation
// [ 0 ]

CreateIndices(2);
// returns 2 permutations
// [ 1, 0 ]
// [ 0, 1 ]

CreateIndices(3);
// returns 6 permutations
// [ 2, 1, 0 ]
// [ 2, 0, 1 ]
// [ 1, 2, 0 ]
// [ 0, 2, 1 ]
// [ 1, 0, 2 ]
// [ 0, 1, 2 ]

It is a recursive method, based only on enumerable extensions, and LINQ syntax queries.

The idea of the recursion is that each level builds based on the previous.

CreateIndices(n) adds the element n-1 to the permutations returned by CreateIndices(n-1), in all available positions.

The root of the recursion is CreateIndices(0) returning an empty set of permutations.

Explaining step by step: CreateIndices(3)

1. Lets start by creating the result of CreateIndices(0):

• empty

2. Then the result of CreateIndices(1):

• add element 0 (n-1) to each of previous permutations, at position 0
  [ 0 ]

3. Then the result of CreateIndices(2)

• add element 1 (n-1) to each of previous permutations, at position 0
  [ 1, 0 ]
• add element 1 (n-1) to each of previous permutations, at position 1
  [ 0, 1 ]

4. Then the result of CreateIndices(3)

• add element 2 (n-1) to each of previous permutations, at position 0
  [ 2, 1, 0 ]
  [ 2, 0, 1 ]
• add element 2 (n-1) to each of previous permutations, at position 1
  [ 1, 2, 0 ]
  [ 0, 2, 1 ]
• add element 2 (n-1) to each of previous permutations, at position 2
  [ 1, 0, 2 ]
  [ 0, 1, 2 ]

What happens next

Now that we have the indices for each of the permutations, we can use them to build the real permutations of values. This is what the generic Get method does.

Also note that the Get method is the only one that materializes the source sequence into an array. The CreateIndices is just an enumerator, without any real objects... so you only pay the cost, when enumerating the sequences, and when calling the Get you pay to create an array of the source sequence.

This explains why after calling Get in the example, I had to materialize the result, so that we can use it:

var items = new[] { "0", "1", "2" };
var p = Permutator.Get(items); // pay to create array from source elements
var result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations
    ).ToArray(); // pay to get the permutations

This allows us to pay only half of the cost, if we just enumerate half of the permutations.

Answer 3

Old as I am, I never like recursion when it's not necessary.

Since you need to iterate the source anyways, I simply store it in an array. I keep track of a 'swappings' array, that tells the program what to swap with what; the index is the source position of the swap, the index the destination position.

You can also do sub-permutations if you like.

If you really feel comfortable with lots of pain, I guess you can also change the swapping to a complex Exchange IEnumerable; I guess that's a good way to add a lot of complexity while at the same time making everything slower. :-)

I also reuse the array; it seems foolish to re-iterate everything every time, which saves you quite a bit of time copying data and doing recursion, when 'src' is large. It's quite efficient.

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> src)
{
    T[] array = src.ToArray();

    // Initialize
    int[] swappings = new int[array.Length];
    for (int j = 0; j < array.Length; ++j)
    {
        swappings[j] = j;
    }

    yield return array;

    int i = swappings.Length - 2;
    while (i >= 0)
    {
        int prev = swappings[i];
        Swap(array, i, prev);
        int next = prev + 1;
        swappings[i] = next;
        Swap(array, i, next);

        yield return array;

        // Prepare next
        i = swappings.Length - 1;
        while (i >= 0 && swappings[i] == array.Length - 1)
        {
            // Undo the swap represented by permSwappings[i]
            Swap(array, i, swappings[i]);
            swappings[i] = i;
            i--;
        }
    }
}

private static void Swap<T>(T[] array, int i, int next)
{
    var tmp = array[i];
    array[i] = array[next];
    array[next] = tmp;
}