Generating all permutations of a list … how hard can that be?

While reading an article that had nothing in common with programming I came upon a sudden need to find a way to generate all the permutations of a list, or more exactly a string (it is just a list of characters). As lazy as I am I tried to google a few examples of C# code that does exactly that. I was horrified that programmers could come up with the complicated ways I found. Not to mention programmers writing a ton of unit test and classes before actualy writing the code that solves to problem.

The problem is naturally recursive. All the permutations of a list of n items consit of each of the n items combined with all the permutations of the list without the actual item. So if you have a list of let’s say items (a,b,c), all the permutations are (a+permutation((b,c)) + (b+permutations((a,c))) + (c+permutations((a,b)).

First I came up with F# code to solve it, after some yield googling:

let rec permutations (input: 'a list) = seq {
    if (input.IsEmpty) then 
        yield []
    else
        
            for i in input do
            yield! input
                    |> List.filter (fun x-> x<> i) 
                    |> permutations
                    |> Seq.map (fun x->i::x)
    }

When I started to think about a C# solution I got stuck. The functional solution was still resonating in my head so I ended up basically rewriting F# to C#:

public IEnumerable<IEnumerable<T>> Permutation<T>(IEnumerable<T> input)
{            
    if (input == null || !input.Any()) yield break;
    if (input.Count() == 1) yield return input;

    foreach (var item in input)
    {
        var next  = input.Where(l => !l.Equals(item)).ToList();
        foreach (var perm in Permutation(next))
        {
            yield return (new List<T>{item}).Concat(perm);
        }
    }
}

Looking for other functional solutions I found a realy neat way to generate permutations in Haskell, thanks to the generators

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]