Modular Partitioning

Question

Given a list of non-negative integers say a₀,a₁,a₂, . . . ,a_n and a constant positive integer m. We want to generate all lists of non-negative integers of the form a'₀,a'₁,a'₂, . . . ,a'_n such that:

1. There exists an i such that a_i ≠ a'_i.
2. For all i, we have a_i ≥ a'_i
3. a₀ + a₁ + a₂ + . . . + a_n - a'₀ - a'₁ - a'₂ - . . . - a'_n is a multiple of m

In terms of time, what is the best algorithm for java. I have tried two different things.

1. For all km between 0 and the sum of the a_is: First generate all partitions of km into n parts. For each of these partitions, subtract it component wise from the original sequence of integers. The resulting list is valid if all of the components are non-negative.
2. Generate all the smaller positions and check if they satisfy condition 3.

Surprisingly, my second idea was significantly faster than the first idea but still fairly slow. How should I approach this? This question is similar in spirit to Generating the partitions of a number.

Answer 1

This can be solved in polynomial time O(nm²) using dynamic programming.

Let f (i, r) be the number of ways to build a sequence a'₀, a'₁, ..., a'_i such that

(a₀ + a₁, ... + a_i - a'₀ - a'₁ - ... - a'_i) mod m = r.

The choice of the first parameter is obvious: we will look at the sequence from left to right and record the result for prefixes of the sequence. The second parameter is the remainder of what we have so far modulo m, since in order to build all possible sequences, we have to consider all possible remainders in between, not just zero.

To calculate f (i, r), we will need to consider the possible choices of (a_i - a'_i) mod m and use the previously calculated f (i - 1, *).

• If (a_i - a'_i) mod m = 0, there are u = [a_i / m] + 1 such choices of a'_i: these are a_i, a_i - m, a'_i - 2 m, ..., a'_i - u m. So, we must add ([a_i / m] + 1) * f (i - 1, r) to our answer: for each possible answer of length i - 1 with total remainder r, we can choose each of the [a_i / m] + 1 possible values of a'_i such that the total remainder of the new sequence is also r.

• If (a_i - a'_i) mod m = m - 1, there are v = [(a_i - 1) / m] + 1 such choices of a'_i: these are a_i - 1, a_i - 1 - m, a'_i - 1 - 2 m, ..., a'_i - 1 - v m. So, we must add ([(a_i - 1) / m] + 1) * f (i - 1, (r + m - 1) mod m) to our answer: for each possible answer of length i - 1 with total remainder (r + m - 1) mod m, we can choose each of the [(a_i - 1) / m] + 1 possible values of a'_i such that the total remainder of the new sequence is now r.

• ...

• If (a_i - a'_i) mod m = 1, there are w = [(a_i - (m - 1)) / m] + 1 such choices of a'_i: these are a_i - (m - 1), a_i - (m - 1) - m, a'_i - (m - 1) - 2 m, ..., a'_i - (m - 1) - w m. So, we must add ([(a_i - (m - 1)) / m] + 1) * f (i - 1, (r + 1) mod m) to our answer: for each possible answer of length i - 1 with total remainder (r + 1) mod m, we can choose each of the [(a_i - (m - 1)) / m] + 1 possible values of a'_i such that the total remainder of the new sequence is now r.

To sum that up,

f (i, r) = sum {by s = 0 to m - 1} of ([(a_i - s) / m] + 1) * f (i - 1, (r + m - s) mod m).

We do that for all i and all r. The base will be f (-1, 0) = 1 (there is one empty sequence with total remainder 0) and f (-1, t) = 0 for t > 0 (there are no empty sequences with total remainder > 0). The answer will be f (n, 0) (the number of sequences a'₀, a'₁, ..., a'_i with total remainder 0).

When implementing, take care to round integer division down and take the non-negative modulo: in languages close to CPU (like C or C++ or even Java), integer division and remainder calculation is rounded towards zero by default, so an integer result of -1 / 2 will be 0 and -1 mod 2 will be -1, when we need -1 and 1, respectively.