JuliaMath / JuliaMath/Combinatorics.jl

Multisets?

Open
#21 3 comments 3 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
230
Forks
62
PR merge metrics
No merged PRs in 30d

Description

A user on stack overflow asked about whether Julia's `partitions` function could compute [multisets](http://stackoverflow.com/questions/37296557/re-partitions/37312100). It can't, and shouldn't.

But a `multisets(n, k)` iterator might actually be useful in some cases. A naive, eager implementation would be:

``` julia
multisets(n, k) = map(A -> [sum(A .== i) for i in 1:n],
with_replacement_combinations(1:n, k))

julia> multisets(2, 1)
2-element Array{Array{Int64,1},1}:
[1,0]
[0,1]

julia> multisets(3, 5)
21-element Array{Array{Int64,1},1}:
[5,0,0]
[4,1,0]
[4,0,1]
[3,2,0]
[3,1,1]
[3,0,2]
[2,3,0]
[2,2,1]
[2,1,2]
[2,0,3]

[1,2,2]
[1,1,3]
[1,0,4]
[0,5,0]
[0,4,1]
[0,3,2]
[0,2,3]
[0,1,4]
[0,0,5]
```

which is not so bad to write but horrible memory-wise. It'd probably be fine if `map` were lazy, but I couldn't find a decent lazy `map` implementation that did not make everything linked lists (and hence even worse).

Would there be room for such a function in this library? Alternatively, might we (or some other library) provide a fast lazy map, so that efficient versions of these functions can be written? I can prepare a pull request if there is demand.

(As an aside, I think `multiset_combinations` is named incorrectly: it means `combinations_of_multisets`. The current `with_replacement_combinations` is more akin to the multiset combinations (multichoose) operation.)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.