On Friday, August 22, 2014 6:23:45 PM UTC-4, K leo wrote:
>
> I want to find all the possible ways to fill a 1-dimensional array A (of
> size say 30) with only -1, 0, or 1 to each element, such that
> sum(abs(A)) is less than say 5. Simple loops don't seem to be very
> efficient. Any suggestions?
>
If you just want to count them, it seems like a straightforward
combinatorics problem: If the length of the array is N and the maximum
sumabs is K, then there can be P=0,1,...K nonzero elements. For each
choice of P nonzero elements, there are 2^P sign choices. So, the total
number of possibilities is (in Julia)
sum(P -> binomial(N, P) * (1<<P), 0:K)
For (N,K)=(30,4), this is 472761. (Maybe you can evaluate this sum
analytically in closed form; I didn't bother.)
To enumerate them, I would just use the "combinations" function, combined
with a gray code to loop over the sign choices, flipping one sign at a
time. For example, you could use:
function getcombos(N::Int, K::Int)
combos = Vector{Int}[]
for P=0:K
for nonzeros in combinations(1:N, P)
push!(combos, nonzeros)
gray = 0
while true
i = trailing_ones(gray) + 1 # component to flip
i > P && break
nonzeros[i] = -nonzeros[i]
push!(combos, copy(nonzeros))
gray += 1
end
end
end
return combos
end
getcombos(N::Integer, K::Integer) = getcombos(int(N),int(K))
This returns a list of lists of indices, where positive indices indicate
the location of the 1's and negative indices indicate the location of the
zeros, e.g. [-27,28,-29,-30] indicates a 1 in index 28, -1's in 27,29,30,
and 0's elsewhere.
For N,K = 30,4 (array length 30, sum < 5), this takes about 0.05 seconds on
my machine, which seems respectable.
--SGJ
