JuliaMath / JuliaMath/Combinatorics.jl
Multisets?
- 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.