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?

You ask interesting questions but the way you format the code is virtually incomprihensible ;-P Using => greatly hurts readability here. — t3chb0t
– t3chb0t, Commented Aug 26, 2019 at 5:29
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
– t3chb0t, Commented Aug 26, 2019 at 6:23
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) — t3chb0t
– t3chb0t, Commented Aug 26, 2019 at 8:23
@t3chb0t Rolled back. The revision history contains the updated code, if you wish to make a self-answer instead. — dfhwze
– dfhwze, Commented Aug 26, 2019 at 8:28
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. — lemonskunnk
– lemonskunnk, Commented Aug 27, 2019 at 2:11

Peter Taylor · Accepted Answer · 2019-08-26 07:27:06Z

English language

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

The verb corresponding to permutation is permute.
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.

t3chb0t · Accepted Answer · 2019-08-26 05:43:44Z

8

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() };
        }
    }
}

answered Aug 26, 2019 at 5:43

t3chb0t

44.7k9 gold badges84 silver badges191 bronze badges

\$\begingroup\$ 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# \$\endgroup\$

Dmitry Nogin
– Dmitry Nogin

2019-08-26 06:04:18 +00:00
Commented Aug 26, 2019 at 6:04
\$\begingroup\$ @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. \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 06:10:32 +00:00
Commented Aug 26, 2019 at 6:10
\$\begingroup\$ @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. \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 06:16:53 +00:00
Commented Aug 26, 2019 at 6:16
\$\begingroup\$ @DmitryNogin have you considered writing such utilities in F#? I bet it would satisfy both your functional needs and my good taste of code ;-] \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 06:19:35 +00:00
Commented Aug 26, 2019 at 6:19
1

\$\begingroup\$ 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. \$\endgroup\$

dfhwze
– dfhwze

2019-08-26 06:19:38 +00:00
Commented Aug 26, 2019 at 6:19

Add a comment |

dfhwze · Accepted Answer · 2019-08-26 06:43:04Z

4

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 :-)}

edited Aug 26, 2019 at 6:43

answered Aug 26, 2019 at 6:30

dfhwze

14.2k3 gold badges40 silver badges101 bronze badges

2

\$\begingroup\$ 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 \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 06:36:00 +00:00
Commented Aug 26, 2019 at 6:36
2

\$\begingroup\$ 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. \$\endgroup\$

dfhwze
– dfhwze

2019-08-26 06:40:22 +00:00
Commented Aug 26, 2019 at 6:40
1

\$\begingroup\$ ok, now with the mini-comment, I can +1 it ;-] \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 06:47:12 +00:00
Commented Aug 26, 2019 at 6:47

Add a comment |

Dmitry Nogin · Accepted Answer · 2019-08-26 08:27:40Z

2

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)));
}

answered Aug 26, 2019 at 8:27

Dmitry Nogin

6,1313 gold badges21 silver badges40 bronze badges

\$\begingroup\$ 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? \$\endgroup\$

t3chb0t
– t3chb0t

2019-08-26 08:43:33 +00:00
Commented Aug 26, 2019 at 8:43
1

\$\begingroup\$ @t3chb0t, there's also a ToArray() in line 6. It's not a wholehearted acceptance of my advice, but it is less buggy. \$\endgroup\$

Peter Taylor
– Peter Taylor

2019-08-26 08:54:43 +00:00
Commented Aug 26, 2019 at 8:54
2

\$\begingroup\$ @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 :) :) \$\endgroup\$

Dmitry Nogin
– Dmitry Nogin

2019-08-26 08:57:34 +00:00
Commented Aug 26, 2019 at 8:57
\$\begingroup\$ 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! \$\endgroup\$

Vogel612
– Vogel612

2019-08-26 19:11:45 +00:00
Commented Aug 26, 2019 at 19:11

Add a comment |

Stack Exchange Network

LINQ for generating all possible permutations

4 Answers 4

English language

Code

You must log in to answer this question.

Hot Network Questions

LINQ for generating all possible permutations

4 Answers 4

English language

Code

You must log in to answer this question.

Related

Hot Network Questions