1 of 2

# Efficiently generate all vector partitions

A vector partition is splitting a vector up a series of vectors such that their sum is the original. Here are a couple partitions:

[3, 1, 2] = [3, 1, 2]
[3, 1, 2] = [0, 0, 1] + [0, 0, 1] + [0, 1, 0] + [1, 0, 0] + [2, 0, 0]
[3, 1, 2] = [1, 1, 2] + [2, 0, 0]


Here vector addition is done element-wise. A valid partition does not contain any vectors with negative integers, or the all-zero vector.

Now the challenge is to write a program or function that generates all possible vector partitions given a target vector. This may sound relatively easy...

### ...but there is a twist. If the input vector has size L, you may not use more than O(L2) memory.

You may assume that an integer uses O(1) memory. This means that you must output the partitions as you generate them. On top of that, you must only output each partition exactly once. For example, these are the same partition:

[3, 1, 2] = [3, 0, 2] + [0, 1, 0]
[3, 1, 2] = [0, 1, 0] + [3, 0, 2]


If you were to output both your answer is invalid.

All partitions for [3, 2]:

[3, 2]
[0, 1] + [3, 1]
[0, 1] + [0, 1] + [3, 0]
[0, 1] + [0, 1] + [1, 0] + [2, 0]
[0, 1] + [0, 1] + [1, 0] + [1, 0] + [1, 0]
[0, 1] + [1, 0] + [2, 1]
[0, 1] + [1, 0] + [1, 0] + [1, 1]
[0, 1] + [1, 1] + [2, 0]
[0, 2] + [3, 0]
[0, 2] + [1, 0] + [2, 0]
[0, 2] + [1, 0] + [1, 0] + [1, 0]
[1, 0] + [2, 2]
[1, 0] + [1, 0] + [1, 2]
[1, 0] + [1, 1] + [1, 1]
[1, 1] + [2, 1]
[1, 2] + [2, 0]


To test your answer, run it on [3, 2, 5, 2]. It should generate 17939 partitions, all of which sum to [3, 2, 5, 2], and that are all unique (you can test for uniqueness by first sorting each partition lexicographically).

Shortest code in bytes wins.

 asked Dec 31 '16 at 1:00 orlp 37k66 gold badges6565 silver badges183183 bronze badges