JuliaMath / JuliaMath/Combinatorics.jl

Allow & include empty partitions among sets from `partitions(::Vector, ::Int)`

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

Description

For some applications, it can be helpful to include in the set of partitions of a vector, the option of taking nothing, i.e., to include empty-partitions. Currently, however, `partitions(s::AbstractVector, m::Int)` will only consider non-empty partitions. I think it would be nice to allow the former as well, enabled e.g., by a keyword argument (e.g., `allow_empty`).

By example, this would turn the two following examples from:
```jl
julia> partitions([1,2,3], 2) |> collect
[[1, 2], [3]]
[[1, 3], [2]]
[[1], [2, 3]]

julia> partitions([1,2,3,4], 3) |> collect
[[1, 2], [3], [4]]
[[1, 3], [2], [4]]
[[1], [2, 3], [4]]
[[1, 4], [2], [3]]
[[1], [2, 4], [3]]
[[1], [2], [3, 4]]
```
to:
```jl
julia> partitions([1,2,3], 2; allow_empty=true) |> collect
[[1, 2], [3]]
[[1, 3], [2]]
[[1], [2, 3]]
[[1, 2, 3], []] # additional permutation

julia> partitions([1,2,3,4], 3; allow_empty=true) |> collect
[[1, 2], [3], [4]]
[[1, 3], [2], [4]]
[[1], [2, 3], [4]]
[[1, 4], [2], [3]]
[[1], [2, 4], [3]]
[[1], [2], [3, 4]]
[[1, 2, 3], [], [4]] # additional permutation
[[1, 2, 4], [3], []] # additional permutation
[[1, 2], [3, 4], []] # additional permutation
...
```

NB: This can currently be "simulated" by appending some token element, e.g., `0`, onto the input vector `m-1` times, and then considering token-elements as empty. I.e., `partitions(vcat(s, fill(0, m-1)), m)`. But this seems inelegant and generates redundant possibilities that need to be filtered out subsequently.

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.