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

[thchr]

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:

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:

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.

[thchr]

Maybe the cleanest current approach is to iterate over all partitions of shorter cardinality as well, i.e., something like:

function partitions_include_empty(v, n)
    ps = Vector{Combinatorics.FixedSetPartitions{typeof(v)}}(undef, n)
    for (i, nᵢ) in enumerate(n:-1:1)
        ps[i] = partitions(v, nᵢ)
    end
    return Iterators.flatten(ps)
end

Although this doesn't explicitly yield any of the empty sets; they're simply absent.