Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.
Your mission, should you choose to accept it, will be to pair up members of the first list with members of the second, outputting a list of triples of the form (i, j, n)
where i
is an index into the first input list, j
is an index into the second input list, and n
is the number of members of group i
from the first list who are paired up with a member of group j
from the second list.
Every member of both lists should be paired up in this way.
In pseudocode, ∀i, sum(n for (i1, _, n) in output if i1 == i) == first_list[i]
, and ∀j, sum(n for (_, j1, n) in output if j1 == j) == second_list[j]
, all(n > 0 and is_integer(n) for (_, _, n) in output)
, where first_list
and second_list
are the two input lists, and i
and j
range over valid indices into the respective inputs.
Your output list must have minimal length among all valid solutions. Zero-based and one-based indexing are both acceptable. Shortest answer wins.
Example
Input: [3, 4, 5] [5, 6, 1]
Possible optimal output: [(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)]
list 1 list 2 i j n
[ 3 0 0 ] [ 0 3 0 ] (0, 1, 3)
+ [ 0 3 0 ] [ 0 3 0 ] (1, 1, 3)
+ [ 0 1 0 ] [ 0 0 1 ] (1, 2, 1)
+ [ 0 0 5 ] [ 5 0 0 ] (2, 0, 5)
---------------------
= [ 3 4 5 ] [ 5 6 1 ]
Test cases
The test cases use zero-based indexing.
[3, 4, 5] [5, 6, 1] -> [(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)] (length 4 optimal)
[4, 3, 1, 5] [2, 1, 3, 7] -> [(1, 2, 3), (2, 1, 1), (0, 3, 4), (3, 3, 3), (3, 0, 2)] (length 5 optimal)
[1, 7, 5] [4, 5, 4] -> [(0, 0, 1), (1, 2, 4), (1, 0, 3), (2, 1, 5)] (length 4 optimal)
[4, 5, 5] [3, 7, 4] -> [(0, 2, 4), (1, 1, 5), (2, 0, 3), (2, 1, 2)] (length 4 optimal)
[4, 3] [3, 1, 3] -> [(0, 0, 3), (0, 1, 1), (1, 2, 3)] (length 3 optimal)
[4, 3, 2] [4, 5] -> [(0, 0, 4), (1, 1, 3), (2, 1, 2)] (length 3 optimal)
[] [] -> [] (length 0 optimal)