5
$\begingroup$

Given a pair of integers n and k, I want to generate all lists of integers of length n, containing integers between -k and +k, such that the total of the list is equal to zero. How can I do this in the most performant way?

Naively, I could do something like

Select[Tuples[Range[-k,k],n],Total[#]==0&]

but this means I'm generating far more Tuples than I need, and for relatively small values of n and k, this fails with error SystemException[MemoryAllocationFailure]

I do not need all permutations. Is there a less wasteful way to generate all such lists?

$\endgroup$
0

1 Answer 1

13
$\begingroup$
f[n_, k_] := IntegerPartitions[0, {n}, Range[-k, k]]

f[4, 2]
(*    {{2, 2, -2, -2}, {2, 1, -1, -2}, {2, 0, 0, -2}, {2, 0, -1, -1},
       {1, 1, 0, -2}, {1, 1, -1, -1}, {1, 0, 0, -1}, {0, 0, 0, 0}}    *)

The fourth argument of IntegerPartitions allows you to get only a reduced number of solutions instead of all solutions.

If you need all permutations of these:

g[n_, k_] := Join @@ Permutations /@ f[n, k]

g[4, 2]
(*    {{2, 2, -2, -2}, {2, -2, 2, -2}, {2, -2, -2, 2},
       ...
       {-1, 1, 0, 0}, {-1, 0, 1, 0}, {-1, 0, 0, 1}, {0, 0, 0, 0}}    *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.