Iterating over integer arrays with fixed sum in Julia

Question

I am looking for an algorithm to iterate over all arrays of length n whose entries are integers between 0 and d and whose sum is k*d. It would be even better if there is a way to do this with built-in Julia functions and iterators. The algorithm should be non-recursive and memory efficient as I am hoping to use this for reasonable values of n.

For small values of n, d, and k, I've written down all such arrays in lexicographical ordering, but I haven't been able to come up with code for iterating through all such arrays.

"built-in Julia" (do you mean only functions in Base?) is an odd restriction... Regardless, you appear to want a constrained variant of partitions(n, m) from Combinatorics.jl. partitions returns an iterator object, but you would need to instantiate the arrays to test your conditions (I think), which won't be efficient. I suspect the solution is a custom implementation of partitions that incorporates your constraints. Hopefully a dev from that package shows up, because it looks very non-trivial to me! — Colin T Bowers
Sorry for the confusion. I'd love to use any existing Julia code, not limited to Base. Yes, I agree it looks very similar to partitions(n,m) but with the added sum constraint. I'm not sure how to handle it. Perhaps I'll look inside the Combinatorics.jl package more to see how partitions(n,m) is coded. — Chris Harshaw
This is not an easy combinatorics question. And the solution has something to do with Catalan numbers and permutations of Catalan arrangements. Hmm interesting problem though — xiaodai

xiaodai xiaodai · Accepted Answer · 2019-03-19T05:45:24

I think this should work but it requires Combinatorics.jl and ResumableFunctions.jl

using Combinatorics, ResumableFunctions
@resumable function gen_all(n, k, d)
    for x in partitions(k*d + n, n)
        x = x .- 1
        if all(x .<= d) 
            ys = Set(permutations(x))
            for y in ys
                @yield y
            end
        end
    end
end


for ga in gen_all(5, 2, 2)
    println(ga)
end

gives

[2, 0, 0, 2, 0]
[2, 0, 0, 0, 2]
[0, 0, 2, 2, 0]
[0, 2, 2, 0, 0]
[2, 0, 2, 0, 0]
[0, 2, 0, 2, 0]
[2, 2, 0, 0, 0]
[0, 0, 0, 2, 2]
[0, 0, 2, 0, 2]
[0, 2, 0, 0, 2]
[0, 2, 0, 1, 1]
[0, 1, 1, 0, 2]
[0, 1, 2, 0, 1]
[0, 1, 1, 2, 0]
[2, 1, 1, 0, 0]
[2, 1, 0, 0, 1]
[0, 0, 1, 1, 2]
[1, 2, 1, 0, 0]
[1, 2, 0, 0, 1]
[0, 1, 2, 1, 0]
[0, 1, 0, 1, 2]
[1, 0, 0, 1, 2]
[0, 2, 1, 1, 0]
[2, 0, 0, 1, 1]
[1, 0, 2, 0, 1]
[1, 2, 0, 1, 0]
[0, 1, 0, 2, 1]
[2, 0, 1, 0, 1]
[0, 2, 1, 0, 1]
[1, 0, 1, 2, 0]
[0, 0, 1, 2, 1]
[1, 0, 0, 2, 1]
[2, 1, 0, 1, 0]
[1, 1, 0, 0, 2]
[1, 0, 2, 1, 0]
[1, 0, 1, 0, 2]
[1, 1, 0, 2, 0]
[0, 0, 2, 1, 1]
[2, 0, 1, 1, 0]
[1, 1, 2, 0, 0]
[1, 1, 1, 0, 1]
[1, 1, 0, 1, 1]
[1, 0, 1, 1, 1]
[1, 1, 1, 1, 0]
[0, 1, 1, 1, 1]

Iterating over integer arrays with fixed sum in Julia

1 Answers