Combinations doesn't handle duplicate elements

[arminsumo]

reproduction steps

using Scala 2.13,

"aba".combinations(3).toSeq // returns Seq("aab"), should return Seq("aba")
"abaa".combinations(3).toSeq // returns Seq("aaa", "aab"), should return Seq("aaa", "aba")

https://scastie.scala-lang.org/V3sDnjcJTTSjVq3nfKXLzA

problem

Combinations method does not seem to gracefully handle input with duplicated elements. The output does not represent an ordered combination of the input, as the docs suggest it should do

Iterates over combinations. A _combination_ of length n is a subsequence of the original sequence, with the elements taken in order.

[SethTisue]

does scala/scala#9942 shed any light on this for you? cc @counter2015

[som-snytt]

Doc at https://www.scala-lang.org/api/current/scala/collection/StringOps.html#combinations(n:Int):Iterator[String]

with implementation at https://www.scala-lang.org/api/current/scala/collection/Seq.html#combinations(n:Int):Iterator[C]

It appears that, of the many uses of underscore, emphasis is not one.

"aba" has 2 * a and 1 * b, and index of a < index of b. Selecting 3 means taking 2 a then 1 b.

[som-snytt]

I see @SethTisue is up to his usual hijinks, with the emphasis on jinx.

The recent update didn't touch ArrayOps. The issue of how examples are presented is worth nailing down.

[arminsumo]

The updated docs makes it more in line with the current behavior, but I wonder if this is the most intuitive implementation? It's a rather surprising behavior, that only the first occurrence is considered for ordering purposes.

Ex, python implementation is more intuitive imo

import itertools
print(list(itertools.combinations('aba', 3))) // returns ['aba']

[som-snytt]

@arminsumo thanks for the heads up about expectations.

I'll submit a doc tweak before I forget what I just learned.

[SethTisue]

PR that documents the status quo: scala/scala#9947

That still leaves the question of whether the behavior should change. Not sure we can change the behavior in a 2.13.x point release, since it would be a design change and not merely fixing a "bug"?

[som-snytt]

If only there were a repo where contributors could add functionality.

Oh I see people do add issues at https://github.com/scala/scala-library-next/issues

Offhand, I can imagine 3 flavors:

• status quo (arbitrary sequences)
• multiset result
• filter of current sequence (so if I want 2x, 1y, "xyx" yields "xyx" not "xxy")

scala/scala-library-next#117

[counter2015]

I prefer multiset result. Mathematically speaking, combinations should not care about order.

Order is the thing that permutation should care.

"abaa".combinations(3) =
Set(
  Set('a', 'a', 'a'),
  Set('b', 'a', 'a')
)

However, in real world, when we compute a large number's combinations, it's better to use iterator rather than set which This will introduce the concept of order.

And the multiset result is not as easy to read or use than sequence result.