algorithm - 在 Julia 中迭代具有固定总和的整数数组

Question

我正在寻找一种算法来遍历所有长度为 n 的数组，这些数组的条目是 0 到 d 之间的整数，其总和是 k*d。如果有一种方法可以使用内置的 Julia 函数和迭代器来做到这一点，那就更好了。该算法应该是非递归和内存高效的，因为我希望将其用于合理的 n 值。

对于较小的 n、d 和 k 值，我已经按照字典顺序记下了所有此类数组，但我无法想出迭代所有此类数组的代码。

Answer 1

我认为这应该可行，但它需要 Combinatorics.jl 和 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

给予

[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]