Varargs of vectors and scalars under modulo

Specific Domains
, ,
1

How would I go about expanding the following code for any number of vectors (possibly using Iterators or @nloops)? My code below shows it working for the first three vectors.

function list_span(u̲::Vector{T}, v̲::Vector{T}, modulo::Int) where T <: Number
	span = Vector{T}[]
	
	for λ in 0:(modulo - 1), γ in 0:(modulo - 1)
		w̲ = mod.(λ*u̲ + γ*v̲, modulo)
		if w̲ ∉ span
			push!(span, w̲)
		end
	end
	
	return span
end
​
function list_span(u̲::Vector{T}, v̲::Vector{T}, t̲::Vector{T}, modulo::Int) where T <: Number
	span = Vector{T}[]
	
	for λ in 0:(modulo - 1), γ in 0:(modulo - 1), α in 0:(modulo - 1)
		w̲ = mod.(λ*u̲ + γ*v̲ + α*t̲, modulo)
		if w̲ ∉ span
			push!(span, w̲)
		end
	end
​
	return span
end
2

I would first switch the order of modulo and the vectors, replace the list of vectors by a single vector argument followed by trailing dots, get the number of vectors with length(u̲) and replace the loop accordingly.

Something like this:

function list_span(modulo::Int, u̲::Vector{T}...) where T <: Number
	span = Vector{T}[]
    n_vec = length(u̲)

    for j in 0:modulo^n_vec-1
        λ = digits(j, base=modulo, pad=n_vec)
        w̲ =mod.(sum(λ .* u̲), modulo)
		if w̲ ∉ span
			push!(span, w̲)
		end        
    end	
	return span
end
3

An alternative way is to loop over the number of vectors and keep adding the multiples of each vector to the span of the previous vectors:

function list_span_alt(modulo::Int, u̲::Vector{T}...) where T <: Number
    n_vec = length(u̲)
    span = Vector{T}[zero(u̲[1])]
    for n=1:n_vec
        new_span = copy(span)
        for v in span, λ=1:modulo-1
            w̲ = mod.(v + λ * u̲[n], modulo)
            if w̲ ∉ new_span
                push!(new_span, w̲)
            end
        end
        span = new_span
    end
	return span
end

It seems more efficient:

julia> @btime list_span(3, [1,2,1], [3,1,2]);
  12.523 μs (106 allocations: 7.77 KiB)

julia> @btime list_span_alt(3, [1,2,1], [3,1,2]);
  2.272 μs (33 allocations: 3.47 KiB)

julia> Set(list_span(3, [1,2,1], [3,1,2])) == Set(list_span_alt(3, [1,2,1], [3,1,2]))
true

But the other way with digits and was cooler, rsrsrs.

4

If you like the other way of ordering the input arguments, you can make an outer method

span_list(args...) = list_span(last(args), args[1:end-1])

and then you get to pass the modulo after all the vectors.

5

Nice.

Hmm, but then you don’t get to enforce the type of each argument.

6

You enforce it in the inner function.