On 1-Jan-17 7:16, Zoffix Znet via RT wrote:
On Sat, 31 Dec 2016 18:59:43 -0800, [email protected] 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.)
(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
b>.permutations(:distinct) in a way that's faster than filtering 3628800
permutations back to 10.
------
-1 from me on this addition. YAGNI: You Ain't Gonna Need It
