Skip Menu |
Report information
Id: 130472
Status: open
Priority: 0/
Queue: perl6

Owner: Nobody
Requestors: perl6 [at] mscha.org
Cc:
AdminCc:

Severity: (no value)
Tag: (no value)
Platform: (no value)
Patch Status: (no value)
VM: (no value)



To: rakudobug [...] perl.org
Date: Sun, 1 Jan 2017 03:59:18 +0100
From: Michael Schaap <perl6 [...] mscha.org>
Subject: [LTA] permutations and combinations don't have a :distinct parameter
Download (untitled) / with headers
text/plain 713b
The permutations and combinations routines both give all possibilities, even if they're not distinct. Show quoted text
> <a b b>.permutations
((a b b) (a b b) (b a b) (b b a) (b a b) (b b a)) Show quoted text
> <a b b>.combinations(2)
((a b) (a b) (b b)) If you want distinct permutations or combinations, you have to do something like: Show quoted text
> <a b b>.permutations.unique(:with(&[eqv]))
((a b b) (b a b) (b b a)) Show quoted text
> <a b b>.combinations(2).unique(:with(&[eqv]))
((a b) (b b)) This is not ideal. It would be awesome if we could do something like: Show quoted text
> <a b b>.permutations(:distinct)
((a b b) (b a b) (b b a)) Show quoted text
> <a b b>.combinations(2, :distinct)
((a b) (b b)) (This potentially has better performance too, depending on the implementation.)
Subject: [RFC] permutations and combinations don't have a :distinct parameter
RT-Send-CC: perl6-compiler [...] perl.org
Download (untitled) / with headers
text/plain 1.6k
On Sat, 31 Dec 2016 18:59:43 -0800, perl6@mscha.org wrote: Show quoted text
> The permutations and combinations routines both give all possibilities, > even if they're not distinct. >
> > <a b b>.permutations
> ((a b b) (a b b) (b a b) (b b a) (b a b) (b b a))
> > <a b b>.combinations(2)
> ((a b) (a b) (b b)) > > If you want distinct permutations or combinations, you have to do > something like: >
> > <a b b>.permutations.unique(:with(&[eqv]))
> ((a b b) (b a b) (b b a))
> > <a b b>.combinations(2).unique(:with(&[eqv]))
> ((a b) (b b)) > > This is not ideal. It would be awesome if we could do something like: >
> > <a b b>.permutations(:distinct)
> ((a b b) (b a b) (b b a))
> > <a b b>.combinations(2, :distinct)
> ((a b) (b b)) >
To me this feels like opening a can of worms. For example, I assume you propose `:distinct` to use `eqv` for comparison, but that would mean <4> (the allomorph) and 4 (the Int) are different items and I can definitely see how some would wish for those to compare the same. We can make it take a comparator, but then we're saving just 8 characters of extra typing in a feature that's not used so commonly as to make those 8 extra chars a bother to type. Show quoted text
> (This potentially has better performance too, depending on the > implementation.)
Do you have suggestions for implementations that'd offer that? Both `.permutations` and `.unique` use lazy sequences, so `.permutations.unique[^5]` would generate just enough items to produce a list of 5. In fact, the most obvious way to implement `:distinct` is by returning a `:distinct`-less `.permutations` Seq with `.unique` call slapped on it. ------ -1 from me on this addition. YAGNI: You Ain't Gonna Need It
From: Michael Schaap <perl6 [...] mscha.org>
To: perl6-bugs-followup [...] perl.org
Date: Sun, 1 Jan 2017 15:57:41 +0100
Subject: Re: [perl #130472] [RFC] permutations and combinations don't have a :distinct parameter
Download (untitled) / with headers
text/plain 2.8k
On 1-Jan-17 7:16, Zoffix Znet via RT wrote: Show quoted text
> On Sat, 31 Dec 2016 18:59:43 -0800, perl6@mscha.org wrote:
>> The permutations and combinations routines both give all possibilities, >> even if they're not distinct. >>
>> > <a b b>.permutations
>> ((a b b) (a b b) (b a b) (b b a) (b a b) (b b a))
>> > <a b b>.combinations(2)
>> ((a b) (a b) (b b)) >> >> If you want distinct permutations or combinations, you have to do >> something like: >>
>> > <a b b>.permutations.unique(:with(&[eqv]))
>> ((a b b) (b a b) (b b a))
>> > <a b b>.combinations(2).unique(:with(&[eqv]))
>> ((a b) (b b)) >> >> This is not ideal. It would be awesome if we could do something like: >>
>> > <a b b>.permutations(:distinct)
>> ((a b b) (b a b) (b b a))
>> > <a b b>.combinations(2, :distinct)
>> ((a b) (b b)) >>
> To me this feels like opening a can of worms. > > For example, I assume you propose `:distinct` to use `eqv` for comparison, but that would mean <4> (the allomorph) and 4 (the Int) are different items and I can definitely see how some would wish for those to compare the same. We can make it take a comparator, but then we're saving just 8 characters of extra typing in a feature that's not used so commonly as to make those 8 extra chars a bother to type.
`eqv` probably makes the most sense, yes, since two permutations or combinations will never be `===` each other. But to be precise, I'm not interested in equality of the lists, but of the individual elements. And for those, `===` is probably the right default. That 4 !=== <4> may be unfortunate in some cases, but that is no different in most other Perl 6 constructs (e.g. sets), right? I can't really judge whether this would be used commonly. I just stumbled across this when doing Project Euler, specifically <https://projecteuler.net/problem=49>, but that's hardly a real life case. But I am sure that, if you deal with permutations or combinations of lists with multiple copies of the same element, in almost all cases you only want distinct permutations or combinations, and there should be a straightforward way to get those. (One could argue that it should even be the default.) Show quoted text
>> (This potentially has better performance too, depending on the >> implementation.)
> Do you have suggestions for implementations that'd offer that? Both `.permutations` and `.unique` use lazy sequences, so `.permutations.unique[^5]` would generate just enough items to produce a list of 5. In fact, the most obvious way to implement `:distinct` is by returning a `:distinct`-less `.permutations` Seq with `.unique` call slapped on it.
No, sorry, no implementation suggestions. I'm definitely not saying it would be easy, or worth it, but I'm sure it would be possible to implement <a b b b b b b b b Show quoted text
b>.permutations(:distinct) in a way that's faster than filtering 3628800
permutations back to 10. Show quoted text
> ------ > > -1 from me on this addition. YAGNI: You Ain't Gonna Need It >


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org