What is the preferred way to iterate through the Cartesian power of an iterable only available at runtime?

General Usage
7

e.g. something like:

function _recursive_iterator!(x, n, k, i)
    if i > k
        println(x)
    elseif i == k # unroll 1-loop base case for speed
        for j = 1:n
            x[i] = j
            println(x)
        end
    else
        for j = 1:n
            x[i] = j
            _recursive_iterator!(x, n, k, i+1)
        end
    end
end
function recursive_iterator(n, k)
    x = zeros(Int, k)
    _recursive_iterator!(x, n, k, 1)
end

for example:

julia> recursive_iterator(3,2)
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]

Note that this is type-stable and allocation-free in the inner loops because it re-uses the same vector x over and over, and by unrolling (“recursion coarsening”) a large enough base case (e.g. you could unroll for k==2 and k==3 as well) you can make it quite efficient.

If you want a type-stable container with an arbitrary length, just use a Vector, not a tuple.

2 Likes