All permutations of a list

Question

I'd like to be able to take a list like this

var list=new List<int>{0, 1, 2};

And get a result like this

var result=
    new List<List<int>>{
        new List<int>{0, 1, 2},
        new List<int>{0, 2, 1},
        new List<int>{1, 0, 2},
        new List<int>{1, 2, 0},
        new List<int>{2, 0, 1},
        new List<int>{2, 1, 0}
    };

I'm not interested in sets with missing numbers, just combinations of the numbers that exist. Any ideas?

Also, I've looked into solutions like Getting all possible combinations from a list of numbers already, and they don't fit.

That one gives me something like this

var result=
    new List<List<int>> {
        // [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
        // serialized the result to JSON so it would be quicker.
    };

And it doesn't spit out all of the combinations.

What you're looking for is all the _Permutations_ of your list. This was asked plenty of times here before :) Here is a very similar question: http://stackoverflow.com/questions/3319586/getting-all-possible-permutations-from-a-list-of-numbers — Benjamin Gruenbaum, Mar 01 '13 at 03:46
That result doesn't include all the items, and it include permutations that exclude items. Tried them both and neither fit. I haven't been able to find any kind of working example that doesn't operate like the one you linked. — Kelly Elton, Mar 01 '13 at 03:47
How are duplicates handled? What if you were given `0, 1, 1, 1, 2, 2`? — yoozer8, Mar 01 '13 at 03:53
`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]` exactly, and in my program I start with 1 instead of 0 — Kelly Elton, Mar 01 '13 at 03:57
Check this answer out, http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer?rq=1. You should be able to extrapolate it out to use a collection instead. — lc., Mar 01 '13 at 03:58
You are confusing the terminology. The Powerset is this: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] while you are asking for all the Permutations. The Combinations are of a degree, and would comprise the sub-set of the Powerset with number of elements equal to the degreee of the Combination, so the Combinations of degree 2 (ie, combinations of 3 choose 2) woudl be {1,2}, {2,3}, and {1,3}. — Pieter Geerkens, Mar 01 '13 at 04:36
Here is a nice article on permutations in C# [http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G](http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G) — terjetyl, Mar 01 '13 at 03:56
Voted to reopen the question as this q is about permutations while q marked as duplicate is about combinations. — nawfal, Jun 24 '15 at 09:19
I have code similar to the accepted answer and it is amazingly slow. The accepted answer is also amazingly slow. Did you ever find anything that is usefully fast? — cedd, Sep 02 '16 at 12:28

score 15 · Accepted Answer · edited Feb 22 '21 at 21:35

15

Try these extension methods on for size:

public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> sequence)
{
    if (sequence == null)
    {
        yield break;
    }

    var list = sequence.ToList();

    if (!list.Any())
    {
        yield return Enumerable.Empty<T>();
    }
    else
    {
        var startingElementIndex = 0;

        foreach (var startingElement in list)
        {
            var index = startingElementIndex;
            var remainingItems = list.Where((e, i) => i != index);

            foreach (var permutationOfRemainder in remainingItems.Permute())
            {
                yield return permutationOfRemainder.Prepend(startingElement);
            }

            startingElementIndex++;
        }
    }
}

edited Feb 22 '21 at 21:35

mmuginov

28
4

answered Mar 01 '13 at 04:28

Jesse C. Slicer

19,901
3
68
87

2

Yeah, I think you win. – Kelly Elton Mar 01 '13 at 04:37
This looks good but where did you get the AllExcept method from? – Christian Findlay Jan 29 '19 at 08:23
@MelbourneDeveloper I honestly don't remember from half a dozen years ago, my apologies. – Jesse C. Slicer Jan 29 '19 at 13:47
1

I realize this is a bit late, but do note that the `AllExcept` method presented here can be entirely replaced with `list.Where((e,i) => i != startingElementIndex)`, which is significantly faster than manual iteration. Edit: And also doesn't suffer from problems if you execute the resulting enumerable multiple times – Mike Caron Apr 17 '19 at 14:56
@MikeCaron elegant and succinct. Good call! – Jesse C. Slicer Apr 17 '19 at 16:34

All permutations of a list

1 Answers1

Linked