# 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] ) ]``````
{"ft_lang_label":"__label__en","ft_lang_prob":0.8455508,"math_prob":0.86538166,"size":1788,"snap":"2019-35-2019-39","text_gpt3_token_len":445,"char_repetition_ratio":0.132287,"word_repetition_ratio":0.0,"special_character_ratio":0.2706935,"punctuation_ratio":0.11204482,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99559146,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-08-25T23:04:13Z\",\"WARC-Record-ID\":\"<urn:uuid:8927457a-c732-44b6-8405-4e4dd26a34a8>\",\"Content-Length\":\"24624\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7eeec173-4c24-4dae-b998-32d3f5be4a52>\",\"WARC-Concurrent-To\":\"<urn:uuid:c0dda758-9955-4e83-ae82-9dee3ab49dd4>\",\"WARC-IP-Address\":\"142.93.122.177\",\"WARC-Target-URI\":\"https://blog.kulman.sk/generating-all-permutations-of-a-list-how-hard-can-that-be/\",\"WARC-Payload-Digest\":\"sha1:5WWLF3PC33W4NZRZE3HONT3JLHGF7OHY\",\"WARC-Block-Digest\":\"sha1:VZISXS3ZDJI7NYMOBZ235YRWLMTSV5F5\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-35/CC-MAIN-2019-35_segments_1566027330907.46_warc_CC-MAIN-20190825215958-20190826001958-00325.warc.gz\"}"}