GrayCodeIterator.jl
GrayCodeIterator.jl provides an iterator for all binary vectors of length
julia> for v in GrayCode(4,2)
println(v)
end
[0, 0, 1, 1]
[0, 1, 1, 0]
[0, 1, 0, 1]
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
julia> for v in GrayCode(4,2,[1,0])
println(v)
end
[1, 0, 0, 1]
[1, 0, 1, 0]
The vector can be modified in-place to save allocations:
julia> using BenchmarkTools
julia> @btime sum(maximum(v) for v in GrayCode(23,13))
54.801 ms (1144073 allocations: 261.86 MiB)
1144066
julia> @btime sum(maximum(v) for v in GrayCode(23,13,mutate=true))
15.782 ms (7 allocations: 1.12 KiB)
1144066
Note that this only saves allocations for Julia 1.8+.
References
The algorithm is based on the following paper:
Bitner, J. R., Ehrlich, G., & Reingold, E. M. (1976). Efficient generation of the binary reflected Gray code and its applications. Communications of the ACM, 19(9), 517-521.