Need to generate every unique combination of an array of files recursively

Question

I've researched and found LOTS of similar requests, but nothing was quite what I needed.

Here is my problem. I'm working in C#, and I have a FileInfo[] array with an unknown number of elements in it.

FileInfo[] files = new FileInfo[]
{
    new FileInfo(@"C:\a.jpg"),
    new FileInfo(@"C:\b.jpg"),
    new FileInfo(@"C:\c.jpg"),
    new FileInfo(@"C:\d.jpg"),
    new FileInfo(@"C:\e.jpg"),
    new FileInfo(@"C:\f.jpg"),
    new FileInfo(@"C:\g.jpg"),
    new FileInfo(@"C:\h.jpg"),
    new FileInfo(@"C:\i.jpg"),
}; // Using 9 elements for this example

And I need to generate a list of every possible reorder combination of these files, without repeating the files.

So, some of my results would be like this (example is not in code format):

a, b, c, d, e, f, g, h, i
a, b, c, d, e, f, g, i, h // i & h switched
a, b, c, d, e, f, h, g, i // last 3 elements switched

a, a, b, b, c, c, d, d, e // THIS IS NOT ACCEPTED, because elements are duplicated

And so on, until I've come up with every possible combination

So the total number of results should be the factorial of the number of elements in the array. In this example, there are 9 elements, so there should be 9*8*7*6*5*4*3*2*1=362,880 possible combinations.

I've been messing with this for a couple days now, and I just can't wrap my mind around it. Any help is appreciated, especially with code examples!

Thanks!

Answer 1

Easy with Linq:

IEnumerable<FileInfo[]> permutations =
    from a in files
    from b in files.Except(new[] { a })
    from c in files.Except(new[] { a, b })
    from d in files.Except(new[] { a, b, c })
    from e in files.Except(new[] { a, b, c, d })
    from f in files.Except(new[] { a, b, c, d, e })
    from g in files.Except(new[] { a, b, c, d, e, f })
    from h in files.Except(new[] { a, b, c, d, e, f, g })
    from i in files.Except(new[] { a, b, c, d, e, f, g, h })
    select new[] { a, b, c, d, e, f, g, h, i };

---

EDIT:

Here's a generic solution, for any number of items:

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; 
        for (int i = 0; i < count; i++)
        {
            result =  
                from seq in result 
                from item in source.Except(seq)
                select seq.Concat(new[] { item }); 
        } 
        return result;
    }
}

Use it as follows:

IEnumerable<IEnumerable<FileInfo>> permutations = files.GetPermutations(9);

(This solution is inspired by Eric Lippert's article about cartesian products.)

---

EDIT 2:

Here's a variant using Aggregate:

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations2<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> seed = new[] { Enumerable.Empty<T>() }; 
        return Enumerable.Repeat(source, count)
            .Aggregate(
                seed,
                (accumulator, sequence) =>
                    from acc in accumulator
                    from item in sequence.Except(acc)
                    select acc.Concat(new[] { item }));
    }
}

Answer 2

You really want all the Permutations of the set.

• http://www.codeproject.com/KB/recipes/Combinatorics.aspx
• http://blogs.msdn.com/b/updownroundnround/archive/2009/12/14/generating-all-permutations-c-enumerator-implementation.aspx

Edit: here is an example of exactly what you are talking about: http://www.codeproject.com/KB/recipes/Premutations.aspx

Answer 3

There are various algorithms available for doing this. The page below lists 3 different ones:

Counting And Listing All Permutations