Skip to content

partitions(0) does not return empty set #79

Open
@jessebett

Description

@jessebett

Currently

julia> partitions(0)|>collect
1-element Array{Any,1}:
 #undef

This is unexpected because the partition of the empty set is the empty set so I would expect

patitions(0)|>collect == [[]]

This results in unexpected behviour here:

julia> [length(b) for b in partitions(1)]
1-element Array{Int64,1}:
 1

julia> [length(b) for b in partitions(0)]
1-element Array{Int64,1}:
 4492284592

# I expect this
julia> [length(b) for b in [[]]]
1-element Array{Int64,1}:
 0

Activity

jessebett

jessebett commented on Jul 11, 2019

@jessebett
Author

I don’t know enough about defining Iterators to solve this 😞

I believe that the bug is

function Base.iterate(p::IntegerPartitions, xs = Int[])
    length(xs) == p.n && return
    xs = nextpartition(p.n,xs)
    (xs, xs)
end

since length(xs)==0 this returns nothing. I don't know how to have iterate here return [[]] only once.

mschauer

mschauer commented on Jul 11, 2019

@mschauer
Member

This does the trick, needs some test etc.

function Base.iterate(p::IntegerPartitions, xs = Int[])
    length(xs) >= p.n + (p.n == 0) && return nothing
    xs = nextpartition(p.n,xs)
    (xs, xs)
end

Ah, no, this returns [0] which is not wrong but not "normalized"

simonschoelly

simonschoelly commented on Jul 12, 2019

@simonschoelly

Then maybe add this as a second function:

function Base.iterate(p::IntegerPartitions)
   p.n == 0 && return (Int[], Int[])
  return iterate(p, Int[])
end

and change the signature of the other function from function Base.iterate(p::IntegerPartitions, xs = Int[]) to function Base.iterate(p::IntegerPartitions, xs).

linked a pull request that will close this issue on Jul 27, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      Participants

      @mschauer@jessebett@simonschoelly

      Issue actions

        partitions(0) does not return empty set · Issue #79 · JuliaMath/Combinatorics.jl