LINQ for generating all possible permutations

Question

Permutate() is supposed to generate all possible permutations of the source sequence:

foreach(var s in "abc".Permutate())
 Console.WriteLine(s); // abc 
 // acb 
 // bac 
 // bca 
 // cab 
 // cba

Where:

 public static IEnumerable<string> Permutate(this string source) =>
 source.AsEnumerable().Permutate().Select(a => new string(a));
 public static IEnumerable<T[]> Permutate<T>(this IEnumerable<T> source)
 {
 return permutate(source, Enumerable.Empty<T>());
 IEnumerable<T[]> permutate(IEnumerable<T> reminder, IEnumerable<T> prefix) =>
 !reminder.Any() ? new[] { prefix.ToArray() } :
 reminder.SelectMany((c, i) => permutate(
 reminder.Take(i).Concat(reminder.Skip(i+1)).ToArray(),
 prefix.Append(c)));
 }

Any optimizations? Could it be shorter?

• t3chb0t: You ask interesting questions but the way you format the code is virtually incomprihensible ;-P Using => greatly hurts readability here.
• t3chb0t: Another possible optimization would be a custom Skip extension. I'm not sure you remember... but the built-in one doesn't recognize IList so it always enumerates from the beginning. I use SkipFast where this matters.
• t3chb0t: We do not add updated code to the question... please turn it into a self-answer... otherwise a rollback is on its way ;-] (keep in mind that we'll need a summary of changes too)
• dfhwze: @t3chb0t Rolled back. The revision history contains the updated code, if you wish to make a self-answer instead.
• lemonskunnk: Hey man, all code-hate aside, i love using => ultra condensed code. I think it's super clean, and in most cases actually easier to follow. The only optimization that i know off hand is not calling the LINQ functions, breaking it into raw code with no function, but i doubt it would be worth it unless you permuting massive multidimensional arrays.

Answer 1

English language

These are relatively minor issues, but fixing them might help other people to use / maintain your code.

1. The verb corresponding to permutation is permute.
2. I'm pretty sure that reminder is intended as remainder.

Code

 public static IEnumerable<T[]> Permutate<T>(this IEnumerable<T> source)
 {
 return permutate(source, Enumerable.Empty<T>());
 IEnumerable<T[]> permutate(IEnumerable<T> reminder, IEnumerable<T> prefix) =>
 !reminder.Any() ? new[] { prefix.ToArray() } :
 reminder.SelectMany((c, i) => permutate(
 reminder.Take(i).Concat(reminder.Skip(i+1)).ToArray(),
 prefix.Append(c)));
 }

To return a permutation of source it is necessary to find all of the elements of source, so I think this is a case where the first thing the method should do is to fully evaluate source (e.g. with ToList() or ToArray()), and then work with that list rather than source. Apart from the efficiency benefits, that guarantees that all of the permutations will be permutations of the same size and elements, even if source has side-effects.

There are a couple of things you can then do with a list to make it much more efficient. Either you can use a standard "next permutation" algorithm (see Wikipedia: for arbitrary inputs it can be done by permuting an array of integers and copying the operations on the array of T) or you can recursively select an element from the first k, swap it to position k, recurse on k-1, and then swap it back. When k==0 you instead copy the entire array and yield the copy. This avoids building up chains of Append and the overheads of Take/Skip/Concat. I expect that the most efficient would be the "next permutation" approach, because it is non-recursive and so doesn't wrap coroutine in coroutine.

Answer 2

Using line breaks and {} in code is not a crime :-P Only because we have the nice => doesn't mean we have to use it everywhere. The code is so condensed that it's hard to say where anything begins and ends.

I find you should first try to write this function in such a way that it is easy to read and one can see what and where could be optimized.

So, I think in this case the Permutate extension would benefit from the query syntax and two let helpers. This would shorten the calls and make it also easier to format and read. Now we can try to use @dfhwze suggestions.

How about this?

public static IEnumerable<string> Permutate(this string source)
{
 return
 source
 .AsEnumerable() // <-- not necessary, string is already IEnumerable<char>
 .Permutate()
 .Select(a => new string(a));
}
public static IEnumerable<T[]> Permutate<T>(this IEnumerable<T> source)
{
 return permutate(source, Enumerable.Empty<T>());
 IEnumerable<T[]> permutate(IEnumerable<T> reminder, IEnumerable<T> prefix)
 {
 if (reminder.Any())
 {
 return
 from t in reminder.Select((r, i) => (r, i))
 let nextReminder = reminder.Take(t.i).Concat(reminder.Skip(t.i + 1)).ToArray()
 let nextPrefix = prefix.Append(t.r)
 from permutation in permutate(nextReminder, nextPrefix)
 select permutation;
 }
 else
 {
 return new[] { prefix.ToArray() };
 }
 }
}

• Dmitry Nogin: AsEnumerable() helps preventing Permutate(this string source) to call itself instead of Permutate<T>(this IEnumerable<T> source). And I personally spend more time reading longer code than a shorter one - FP programming can be very different stylistically from an imperative approach. Your version of code does not look like FP - it is a way more verbose as a typical imperative code will be for sure :) Good examples to compare would be Scala and C#
• t3chb0t: @DmitryNogin I like functional style too but using this style just for the sake of using it does more harm than good. We have the luxary to pick a style that better suites the current situation. Since C# is not pure functional, it consequently does not always results in nice code which this code is a good example of.
• t3chb0t: @DmitryNogin well, the comparison between Scala and C# is unfair. In scala they've just implemented the pure algorithm which would most probably fit into an extension like yours but instead, they've build an entire module with properties, validations, argument checking etc etc. I'm not really sure what is the point of these examples.
• t3chb0t: @DmitryNogin have you considered writing such utilities in F#? I bet it would satisfy both your functional needs and my good taste of code ;-]
• dfhwze: I can't find an intersection for these questions: (1) Any optimizations? (2) Could it be shorter? Each of these questions deserves a completely different answer.

Answer 3

You did also ask for a shortened version. I believe readability should not be a concern here (meaning the code should aim at being functional, not readable). Remove the local recursive function and allow the public API to have an optional parameter.

public static IEnumerable<T[]> Permutate<T>(
 this IEnumerable<T> source, IEnumerable<T> prefix = null) => 
 !source.Any() ? new[] { (prefix ?? Enumerable.Empty<T>()).ToArray() } :
 source.SelectMany((c, i) =>
 source.Take(i).Concat(source.Skip(i+1)).ToArray().Permutate(
 prefix.Append(c)));

^{use in production code at own risk :-)}

• t3chb0t: this'll be the first time where I don't agree. The ternary operator is barely visible and the optional parameter just makes me scratch my head asking myself what do they need from me here? :-\ you could name it placebo or like in the emails do_not_use_this_argument :-P similar to no-replay
• dfhwze: As pointed out, the shortened version has nothing to do with readability, and I would never use it in production code. But it provides a solution only using functional programming (no additional statements with ; delimited) which is what OP requested. It's more of a Code Golf answer.
• t3chb0t: ok, now with the mini-comment, I can +1 it ;-]

Answer 4

An updated version, please see an accepted answer for details.

public static IEnumerable<string> Permute(this string source) =>
 source.AsEnumerable().Permute().Select(a => new string(a));
public static IEnumerable<T[]> Permute<T>(this IEnumerable<T> source)
{
 return permute(source.ToArray(), Enumerable.Empty<T>());
 IEnumerable<T[]> permute(IEnumerable<T> remainder, IEnumerable<T> prefix) =>
 !remainder.Any() ? new[] { prefix.ToArray() } :
 remainder.SelectMany((c, i) => permute(
 remainder.Take(i).Concat(remainder.Skip(i+1)).ToArray(),
 prefix.Append(c)));
}

• t3chb0t: mhmm... the only difference I can see is Permutate became Permute - I'm not sure this is worth posting :-\ have you possibly posted the wrong code?
• Peter Taylor: @t3chb0t, there's also a ToArray() in line 6. It's not a wholehearted acceptance of my advice, but it is less buggy.
• Dmitry Nogin: @t3chb0t Permute, remainder, source.ToArray(). P. S. Intensively looking for a new interesting job - here comes a lot of interview preparation questions adapted to FP, some snippets could be useful latter to copy/paste, so trying to have a clean version ready :) :)
• Vogel612: Comments are not for extended discussion, let alone for soliciting job interviews and well-meaning banter. For that purpose there's Code Review Chat. Please use it. Thanks!