Runtime: New method to get permutations of items in 1D collections

[varocarbas]

Getting all the possible permutations (understood in its widest sense) of elements in a given 1D collection is a somehow common requirement. For example (C# version):

List<int> items = new List<int>() { 1, 2, 3 };

//All permutations of 2
//a) No repeated elements and order doesn't matter (1-2 = 2-1)
//1-2, 1-3, 2-3
//b) No repeated elements and order matters (1-2 != 2-1) 
//1-2, 1-3, 2-1, 2-3, 3-1, 3-2
//c) Repeated elements and order doesn't matter
//1-1, 1-2, 1-3, 2-3, 2-2, 3-3
//d) Repeated elements and order matters 
//1-1, 1-2, 1-3, 2-1, 2-3, 2-2, 3-1, 3-2, 3-3

//All permutations of 3, etc.

With a constant number of elements (e.g., 3, as proposed in the aforementioned example), implementing an algorithm to deliver this functionality is quite straightforward (i.e., as many nested loops as elements). On the other hand, with a variable number of elements (e.g., any number between 3 and 10), the complexity is notably increased. Even in the first simpler scenario, being able to just type myPermutations = myCollection.Permutations(2); would be certainly helpful.

My proposal is to create a new method for 1D collections delivering all the possible permutations among its elements. It might be called "Permutations" and accept various arguments, like number of items per permutation or type of permutation (as shown in the example above). At least for the first version, I think that the best format for the output variable is a dictionary of integers (key) and collection of objects (value). By assuming that the first version will be included within the System.Array methods, I guess that the dictionary should be of type (C#) Dictionary<int, object[]>.

In case of deciding to go ahead with this proposal, I would like to implement it myself.

[svick]

From dotnet/corefx#6284:

I don't think that there is a proper mathematical name for the 4 proposed cases.

Actually, I believe there are:

a) No repeated elements and order doesn't matter

That's called combination.

b) No repeated elements and order matters

That's partial permutation.

c) Repeated elements and order doesn't matter

That's combination with repetition.

d) Repeated elements and order matters

That's permutation with repetition.

[varocarbas]

@svick Thanks for the info.

Honestly, I don't have any strong preference about the name. As said in the other thread to @JonHanna, I started this development as permutations with some practically-useful (and easy to deliver by the algorithm) extensions.

Note that the whole point of all my answers there was explaining the reason why I chose "permutations" (i.e., almost-intuitively assuming that it was more restricted than "combinations"); not defending my position as objectively better. Apparently, I was wrong and my proposal is related to both, combinations and permutations.

[karelz]

@mellinoe does it sound like reasonable Math API?

[mellinoe]

@karelz This isn't really a math API, at least not in the "System.Numerics" math sense.

This seems like useful, but very niche and narrow, functionality. I also suspect that whatever we tried to include might not necessarily be universally applicable because folks would want vaguely different sorts of combination and permutation types, just based on their domain or business needs. And it's not really that hard to implement something like this yourself based on the specific sorts of needs your app has.

[varocarbas]

@karelz @mellinoe
If I may, I want to share some ideas with both of you (understood as representing the .NET team).

I created this issue (7 months ago! Not that bad) when my impression about open .NET was quite different to what I think now.

What I think now is that perhaps this isn't for me. Since the start, my intention was having a positive contribution by assuming that I will be dealing with other programmers thinking like me. After having participated in various issues, what I have seen can be summarised in the following points:

• Having to systematically over-explain what I consider evident.
• Getting involved in discussions with people who don't seem to be pursuing the same goals than me (not wanting to properly understand, just looking for excuses to prove the invalidity of the request; usually, by relying on quite narrow-minded, partial and even random critics. Why? No idea).
• Really long waiting periods.
• Rarely having the impression that I am helping, but right the contrary (representing an additional work load for some people who have to deal with me?!).

The most descriptive-to-me result happened a couple of days ago in another issue (also assigned to mellinoe). After a quite long discussion where lots of aspects were improved/adapted/changed (honestly, I liked this whole evolution pretty much), it reached the API-discussion stage whose conclusions were certainly unsatisfactory. The still-not-replied answer which I wrote should be clear enough to anyone willing to properly-understand my position. I would have preferred a simple "sorry, but we don't want to do it" and ideally some months ago (what would have avoided me and others spending time on an apparently-going-anywhere discussion).

Let's take your last comments as an example: I do agree with mellinoe in his point of not seeing the original proposal as part of System.Numerics (on the other hand, it might be re-formulated to be exclusively focused on numeric aspects; but I will not be suggesting such a thing because of having learned from past errors :)). I don't fully agree with what he says about its narrow applicability; I have seen quite a few scenarios requiring it (mainly GUI-intensive and web-based apps). But I am not interested in further discussing about this issue (or any other one), unless having an actual point. That is: if you are already reasonably sure that this implementation will not go anywhere, I wouldn't find any problem in having the issue closed right away. I don't need to talk about my impressions neither to convince anyone of anything. Discussing/chatting/talking-about-abstract-aspects is neither my style nor my work. I am a programmer, and engineer, someone exclusively interested in coding and, eventually, working on directly-related-to-coding-aspects; an eminently-practical person not wanting to get involved in anything without a practical applicability. Do some people need help to understand my point? I can do a small effort. Some people aren't completely sure about the reasons for my suggestion and want to ask some questions/critic some aspects to clarify their ideas? I can also do a small effort. Are you completely sure (for whatever reason) that this will never happen? Please, be honest and don't waste my and others' time.

In summary, I am asking for an as straightforward as possible communication. I don't want to bother anyone, to unnecessarily extend discussions, to keep open issues which aren't meeting the current .NET team expectations, to criticise anyone or highlight limitations/problems, etc. All what I want is to have a positive contribution by assuming that we are on the same page. In case that this community, the .NET team, Microsoft or whoever for whatever reason thinks differently, I wouldn't find any problem in accepting it.

[SamuelEnglard]

@varocarbas I'm not on the .NET team or a Microsoft employee but I think I can help explain a bit what's going on

I would have preferred a simple "sorry, but we don't want to do it" and ideally some months ago (what would have avoided me and others spending time on an apparently-going-anywhere discussion).

They could have done that, but had they done so they would have been rejecting the original suggestion not the final one, which were very different. Also, they rejected doing most of it, not all. I suspect if you opened a new, smaller scoped issue with the stuff that they said they liked they might do accept it.

I do agree with mellinoe in his point of not seeing the original proposal as part of System.Numerics (on the other hand, it might be re-formulated to be exclusively focused on numeric aspects; but I will not be suggesting such a thing because of having learned from past errors :)). I don't fully agree with what he says about its narrow applicability; I have seen quite a few scenarios requiring it (mainly GUI-intensive and web-based apps).

Something a lot of us, including me, forget at times is the .NET Core code is shared with the Full Framework which ships on every Windows machine. So while in Core everything is packages and you only have to have a small subset of it, in Full adding something must be "worth it".

I don't want to bother anyone, to unnecessarily extend discussions, to keep open issues which aren't meeting the current .NET team expectations, to criticise anyone or highlight limitations/problems, etc

While I can't speak for the others I am willing to bet they don't feel bothered at all. If they did they're in the wrong jobs.

I think (though correct me if I'm wrong) you'd prefer to be coding over designing. In such a case I'd take a look at the "up for grabs" tag. Those are issues that the specification is done and just need the code written.

[varocarbas]

@SamuelEnglard Thanks for your post and suggestion, but I think that my message was quite self-explanatory. I wasn't blaming anyone of anything or intending to trigger any kind of change, that's why no justifications or alternatives are really required.

I have plainly shared my ideas in case someone is interested in knowing my general opinion about contributing here. This information might become handy to guess my likely behaviour under different conditions and/or know the kind of outputs which I (dis)like. It is completely up to anyone to properly understand, use or even plainly ignore such an information.

[khellang]

Something a lot of us, including me, forget at times is the .NET Core code is shared with the Full Framework which ships on every Windows machine.

Is this true? The code is shared?

So while in Core everything is packages and you only have to have a small subset of it, in Full adding something must be "worth it".

Does this mean full framework is holding .NET Core back? I thought .NET Core would be able to rev faster because it was all just NuGet packages :confused:

[SamuelEnglard]

@khellang they code is shared BUT Core is able to rev faster since release and bug fixes don't have to wait for the Full Framework. However, changes do impact it eventually. (If you see merges in the commits by the dotnet-bot from TFS those are usually the sync between the two)

[karelz]

@varocarbas Thanks for sharing your opinion. I'd like to react to a few points:

First, designing new APIs in frameworks which should survive long time is hard work. I have learned over time that discussions about APIs, what they mean, how they impact existing APIs, how they are consistent with the rest of the Framework, how they are usable and what is their value, is far away from simple. There are always many opinions and point of views and the API reviewers have to consider them all (BTW: we spent discussing 'the other issue' for 30 minutes to come to the conclusion/agreement between ~5 people, definitely not a cheap investment on our side and also sign it was not clear "no" answer).
For more context see api review process documentation.

From that point of view you should not expect that "hey, let's add API X" is going to be a smooth ride. It almost never is. Discussions (incl. long ones) are just part of the work, basically a tax everyone has to pay (including "us" - .NET team members). If long discussions are not your style of work (which is perfectly fine) and you still want to help, I would suggest to take the suggestion above and grab more actionable type of work - code improvements, bug fixes and test improvements. We have plenty of those (marked as up for grabs, just avoid those which design new APIs - typically with api-* label) and we welcome any help!

Really long waiting periods.

Yes, that is something the team is aware of and it is also something we started actively changing as of last week. My goal is to triage all areas during October (we started with Collections and Numerics), closing issues which don't require more action or we don't think are good ideas, and making sure we follow up where necessary. Also using "up for grabs" where applicable. We want to establish continuous triage as a habit on the team going forward.
I apologize on behalf of the team for the inconvenience that we didn't have this practice in place earlier which lead to long delays. Hopefully having it established late is better than never.

[karelz]

Given that we do not have clear proposal which would gain wider agreement, I am closing the issue.

@varocarbas if you are still passionate about permutation APIs, I would suggest to create ad-on library on top of .NET Core. If it gains popularity and is found really useful by wider audience, we can eventually consider including it back into .NET Core, or just leave it as a great Math ad-on library (similar to JSon.NET, MailKit and many other libraries).

[varocarbas]

@karelz Excellent reaction, thanks. Descriptive, to the point and with quick results.

My intention wasn't triggering a change of your proceedings, but I am happy if it was kind of helpful to spot certain weakness. At least for me, a quicker-closing-issues attitude would be really positive: the .NET team would be able to fully focus on actually relevant issues and it would help proposers to understand better how/what to propose.

I guess that your "...was not clear "no" answer" addresses my other concern. Although still not sure how to proceed on this front, just wait?

[karelz]

Although still not sure how to proceed on this front, just wait?

Let's take the discussion there ...