Minimal Pairing

Question

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)

Answer 1

Scala, 222..187 180 bytes

-7 bytes thanks to user!

x=>y=>{var(a,b,r)=(x,y,Set[Any]())
while(a.sum>0){var?,m=a.max min b.max
var p,q= -1
while(p<0|q<0){if(p<0)p=a indexOf?
if(q<0)q=b indexOf?
? +=1}
a(p)-=m
b(q)-=m
r+=Seq(p,q,m)}
r}

Try it online!

Answer 2

JavaScript (ES6), 137 bytes

a=>g=(b,k=O=0,o=[],n,c)=>O=O&&!O[k]||a.map((p,i)=>b.map((q,j)=>b[a[i]-=n=p<q?p:q,b[j]-=n,n&&g(b,k+1,[...o,[i,j,c=n]]),a[i]=p,j]=q))|c?O:o

Try it online!

Commented

a =>                           // outer function taking the 1st list a[]
g = (                          // inner function taking:
  b,                           //   the 2nd list b[]
  k = O = 0,                   //   k = length of current solution, O = output
  o = [],                      //   o[] = current solution
  n,                           //   n is a local variable
  c                            //   c is a flag telling whether both lists are cleared
) =>                           //
  O =                          // update O:
    O &&                       //   abort if an output is already defined
    !O[k] ||                   //   and it's shorter than the current solution
    a.map((p, i) =>            //   otherwise, for each value p at position i in a[]:
      b.map((q, j) =>          //     for each value q at position j in b[]:
        b[                     //
          a[i] -=              //       subtract n from a[i]
            n = p < q ? p : q, //       where n = min(p, q)
          b[j] -= n,           //       subtract n from b[j]
          n && g(              //       if n > 0, do a recursive call:
            b,                 //         pass b[] unchanged
            k + 1,             //         increment k
            [ ...o,            //         update the solution o[]
              [i, j, c = n] ]  //         with the triplet [i, j, n]
                               //         and set the flag c
          ),                   //       end of recursive call
          a[i] = p,            //       restore a[i]
          j                    //
        ] = q                  //       restore b[j]
      )                        //     end of inner map()
    ) | c ?                    //   end of outer map(); if c is set:
      O                        //     leave O unchanged
    :                          //   else:
      o                        //     update O to o