1
$\begingroup$

Suppose we have $N$ elements that we distribute over $K$ bins. We define a state of our system as $n = (n_1, \ldots, n_K)$ with $\sum_{i=1}^{K} n_i = N$. Given an input state $m = (m_1, \ldots, m_K)$ and an output $n = (n_1, \ldots, n_K)$, how can we efficiently find all the possible ways of taking the state $m$ and redistributing the $N$ elements into the new state $n$?

We can formalise this problem by defining a transition flux $F(i \rightarrow j)$ as the number of elements that were in bin $i$ initially and are redistributed into bin $j$. We then have $\sum_{j=1}^{K} F(i \rightarrow j) = m_i$ and $\sum_{i=1}^{K} F(i \rightarrow j) = n_j$, as well as $\sum_{i=1}^{K} \sum_{j=1}^{K} F(i \rightarrow j) = N$. This somewhat reminds me of a magic square, except that the sums of the rows and columns are fixed at arbitrary values rather than the same value for each and the numbers don't have to be consecutive.

Is there an efficient way of obtaining the set of possible $F(i \rightarrow j)$? So far I've only been able to come up with a brute-force algorithm that tries all redistributions and only selects those for which the output state is $n$.

$\endgroup$
0
$\begingroup$

Algorithm:

  1. Calculate the element-to-element difference between output and input.
  2. Sort the differences from negative to positive and keeping the indices (in a new field).
  3. Redistribute the negatives in the positives.

Example:

Input: (3,7,5,9,2) Sum: 26

Output: (4,1,3,8,10) Sum: 26

Difference: (1, -6, -2, -1,8) Sum: 0

Ordered with index: [(-6,2), (-2,3), (-1,4), (1,1), (8,5)]

Redistribute:

6 from 2 to 5

2 from 3 to 5

1 from 4 to 1

To count the total number of ways to do it is much more difficult.

In this example it is easy:

How many ways to move 6 red balls, 2 green balls and 1 blue ball to 2 bags, the first size 1 and the second size 8?

The answer is 3, the color of the ball that goes to the first bag.

To obtain the list of all possible optimal redistributions, you can calculate the list of all the permutations with repetition of the sum of the negative numbers (or positive ones)

For example, if we have the balls {6,2,1} as in the previous example, that gives us a list of 252 elements (9! / (6! 2! 1!)) That form the permutations with repetition.

From that list of 252 elements of size 9:

aaaaaabbc

aaaaaabcb

aaaaababc

...

We start in 1 and 8, and we have the list of 252 elements:

a | aaaaabbc

a | aaaaabcb

a | aaaababc

...

And rearranging each sub-element, the list of 252 remains:

a | aaaaabbc

a | aaaaabbc

a | aaaaabbc

...

Eliminating the repeated ones, we have a list of 3 elements:

a | aaaaabbc

b | aaaaaabc

c | aaaaaabb

The third redistribution is that of the example above.

The basic and main idea of ​​all this algorithm is that the difference of the input and output, ordered, and with possible sign substitution before ordering, is the discriminant of the problem.

That is, if ordered (A - B) = ordered (C - D) or ordered (D - C) the problem is the same (with substitution of indices).

For example:

Input: (4,8,1,1,9) Sum: 23

Output: (3,9,3,7,1) Sum: 23

It is the same problem as the previous example. And the same solution (except the movement indexes).

(3,9,3,7,1) - (4,8,1,1,9) = (-1,1,2,6, -8)

Ordered: (-8, -1,1,2,6)

It is the same problem since the discriminant, as it has been defined, is the same.

$\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.