Efficient representation of a set of digits 1-9

DigitSets.jl

# Represent a set of digits 1-9 as an Int16, where the binary digits of the
# integer form a mask determining whether the associated digit is present in
# the set
immutable DigitSet
    d::Int16
end

function DigitSet(a::AbstractArray)
    d = Int16(0)
    for n in a
        d |= 1 << (n - 1)
    end
    DigitSet(d)
end

# Allow iterating over the members of a digit set
Base.start(c::DigitSet) = (c.d, 0)
function Base.next(c::DigitSet, state)
    (d, n) = state
    while true
        n += 1
        if d % 2 == 1
            return (n, (d >> 1, n))
        else
            d >>= 1
        end
    end
end
Base.done(c::DigitSet, state) = state[1] <= 0
Base.length(c::DigitSet) = count_ones(c.d)

function Base.show(io::IO, s::DigitSet)
    print(io,"DigitSet")
    print(io,"([")
    state = start(s)
    if !done(s, state)
        (i, state) = next(s, state)
        print(io, i)

        while (!done(s, state))
            (i, state) = next(s, state)
            print(io, ",")
            print(io, i)
        end
    end
    print(io,"])")
end

# Set operations
Base.union(a::DigitSet, b::DigitSet) = DigitSet(a.d | b.d)
Base.intersect(a::DigitSet, b::DigitSet) = DigitSet(a.d & b.d)
Base.setdiff(a::DigitSet, b::DigitSet) = DigitSet(a.d & (~b.d))
Base.symdiff(a::DigitSet, b::DigitSet) = DigitSet((a.d&(~b.d))|(b.d&(~a.d)))

# There are only 2^9 = 512 combinations of the integers 1-9. Find the sums of
# each of them, and store them in a look up table
function buildlut()
    lut = Array(Vector{DigitSet}, 45, 9)
    for i in 1:45
        for j in 1:9
            lut[i, j] = DigitSet[]
        end
    end

    for c in 1:511
        d = DigitSet(c)
        push!(lut[sum(d), length(d)], d)
    end
    lut
end

const lut = buildlut()

# Now decomposing an integer into a sum of unique digits in the range
# 1-9 is just a table lookup
decompose(i, j) = lut[i, j]

# Benchmark finding the number with the most different decompositions:
function benchmark()
    s = 0
    maxset = DigitSet[]
    maxlen = length(maxset)
    for i in 1:45
        for j in 1:9
            ds = decompose(i, j)
            len = length(ds)
            if len > maxlen
                maxlen = len
                maxset = ds
            end
        end
    end
    maxset
end

The benchmark only takes a few microseconds once it is warmed up:

@time benchmark(); @time benchmark()
#0.004547 seconds (4.39 k allocations: 219.106 KB)
#0.000007 seconds (5 allocations: 224 bytes)

To be fair, we might want to also benchmark the time it takes to build the look up table:

@time buildlut(); @time buildlut()
#0.056881 seconds (58.28 k allocations: 2.758 MB)
#0.000098 seconds (1.11 k allocations: 40.750 KB)

So even building the look up table is also very fast: ~100 microseconds, and you only need to do it once, probably at module load time.