Find the minimum cost matching between arrays of integers

Question

Consider two sorted arrays of integers \$X\$ and \$Y\$ of size \$m\$ and \$n\$ respectively with \$m < n\$. For example \$ X = (1,4)\$, \$Y = (2,10,11)\$.

We say that a matching is some way of pairing each element of \$X\$ with an element of \$Y\$ in such a way that no two elements of \$X\$ are paired with the same element of \$Y\$. The cost of a matching is just the sum of the absolute values of the differences in the pairs.

For example, with \$X = (7,11)\$, \$Y = (2,10,11)\$ we can make the pairs \$(7,2), (11,10)\$ which then has cost \$5+1 = 6\$. If we had made the pairs \$(7,10), (11,11)\$ the cost would have been \$3+0 = 3\$. If we had made the pairs \$(7,11), (11,10)\$ the cost would have been \$4+1 = 5\$.

As another example take \$X = (7,11,14)\$, \$Y = (2,10,11,18)\$. We can make the pairs \$(7,2), (11,10), (14,11)\$ for a cost of \$9\$. The pairs \$(7,10), (11,11), (14,18)\$ cost \$7\$.

The task is to write code that, given two sorted arrays of integers \$X\$ and \$Y\$, computes a minimum cost matching.

Test cases

[1, 4],      [2, 10, 11]     => [[1, 2], [4, 10]]
[7, 11],     [2, 10, 11]     => [[7, 10], [11, 11]]
[7, 11, 14], [2, 10, 11, 18] => [[7, 10], [11, 11], [14, 18]]

Answer 1

Brachylog, 16 bytes

∧≜I&pᵐz₀.-ᵐȧᵐ+I∧

Try it online!

Explanation

∧
 ≜I                   Take an integer I = 0, 1, -1, 2, -2, 3, -3, …
   &pᵐ                Permute each sublist
      z₀.             Zip the sublists together. The result of the zip is the output
         -ᵐȧᵐ         Absolute differences of each pair
             +I       The sum of these differences must be I
               ∧

Since we unify I to an integer at the very beginning, we try things from small values of I to large values of I, which means the first time it will succeed will necessarily be for the pairing with smallest absolute differences.

Answer 2

Jelly, 15 14 12 11 bytes

Œ!ż€IASƊÞḢṁ

Try it online!

• -1 byte thanks to Jonathan Allan
• -1 byte thanks to Mr. Xcoder
• -2 bytes thanks to an anonymous editor

Brute force. Takes input as \$Y\$ then \$X\$.

Œ!ż€IASƊÞḢṁ
Œ!                 All permutations of Y.
  ż€               Zip each of the permutations with X.

       ƊÞ          Sort by:
    I              Difference of each pair.
     A             Absolute value.
      S            Sum.
         Ḣ         Take the first matching.
          ṁ        Mold the result like X. Keeps only values up to the length 
                   of X which removes unpaired values from Y.

Answer 3

Haskell, 78 77 76 bytes

import Data.Lists
(argmin(sum.map(abs.uncurry(-))).).(.permutations).map.zip

TIO doesn't have Data.Lists, so no link.

Basically the same algorithm as seen in @dylnan's answer.

Edit: -1 byte thanks to @BMO.

Answer 4

JavaScript (ES7), 121 bytes

Takes the 2 arrays in currying syntax (x)(y).

x=>y=>(m=P=(b,[x,...a],s=0,o=[])=>1/x?b.map((v,i)=>P(b.filter(_=>i--),a,s+(x-v)**2,[[x,v],...o])):m<s||(r=o,m=s))(y,x)&&r

Try it online!

Answer 5

J, 24 bytes

[,.[-[:,@:(0{]#~1>])"1-/

Try it online!

Explanation/Demonstration:

A dyadic verb, x f y

-/ finds the differences

 7 11 14 -/ 2 10 11 18
 5 _3 _4 _11
 9  1  0  _7
12  4  3  _4

(0{]#~1>])"1 for each row keep only the non-positive values and take the first one:

   7 11 14 ([:(0{]#~1>])"1-/) 2 10 11 18
_3 0 _4

[:,@: flattens the list (to match the shape of the left argument)

[- subtract the min. differences from the left argument

    7 11 14 ([-[:,@:(0{]#~1>])"1-/) 2 10 11 18
10
11
18

[,. stitch them to the left argument:

   7 11 14 ([,.[-[:,@:(0{]#~1>])"1-/) 2 10 11 18
 7 10
11 11
14 18

Answer 6

Pyth, 18 bytes

t#h.msaMbm.T,dvz.p

Try it here!

Answer 7

Octave, 66 bytes

@(X,Y)[X;C([~,r]=min(sum(abs(X-(C=perms(Y)(:,1:numel(X)))),2)),:)]

Anonymous function that takes row vectors X, Y as inputs and outputs a 2-row matrix where each column is a pair of the matching.

Try it online!

Answer 8

Pyth, 16 bytes

hosaMNCM*.pQ.cEl

Try it online here, or verify all test cases at once here.

hosaMNCM*.pQ.cEl   Implicit: Q=evaluated 1st input, E=evaluated 2nd input
               l   Length of 1st input (trailing Q inferred)
            .cE    All combinations of 2nd input of the above length
         .pQ       All permutations of 1st input
        *          Cartesian product
      CM           Transpose each of the above
 o                 Order the above using:
   aMN               Take the absolute difference of each pair
  s                  ... and take their sum
h                  Take the first element of the sorted list, implicit print

Answer 9

MATL, 16 bytes

yn&Y@yy&1ZP&X<Y)

Inputs are X, then Y.

The matching is output with the first values of each pair (that is, X) in the first line, and the second values of each pair in the second line.

Try it online! Or verify all test cases.

Explanation

y       % Implicit inputs: X, Y. Duplicate from below
        % STACK: [7 11], [2 10 11], [7 11]
n       % Number of elements
        % STACK: [7 11], [2 10 11], 2
&Y@     % Variations without repetition
        % STACK: [7 11], [2 10; 2 11; 10 2; 10 11; 11 2; 11 10]
yy      % Duplicate top two elements
        % STACK: [7 11], [2 10; ...; 11 10], [7 11], [2 10; ...; 11 10]
&1ZP    % Compute cityblock distance between rows of the two input matrices
        % STACK: [7 11], [2 10;...; 11 10], [6 5 12 3 13 5]
&X<     % Argmin (first index of occurrences of the minimum)
        % STACK: [7 11], [2 10; 2 11; 10 2; 10 11; 11 2; 11 10], 4
Y)      % Row indexing. Implicit display
        % STACK: [7 11], 10 11]

Answer 10

Jelly, (10?) 12 bytes

^{10 bytes if just the elements of Y are required (see comments) - not sure if it's allowed by spec yet though (and maybe it shouldn't be since other answers already implement this detail).
This may be achieved by removing the trailing ⁸ż.}

Lœc@ạS¥Þ⁸Ḣ⁸ż

A dyadic link accepting X on the left and Y on the right.
(œc⁹L¤ạS¥ÞḢż@ and the 10 byte œc⁹L¤ạS¥ÞḢ do the same with Y on the left and X on the right).

Try it online!

How?

Lœc@ạS¥Þ⁸Ḣ⁸ż - Link: sorted list of integers X, sorted list of integers Y
L            - length
   @         - with swapped arguments:
 œc          -   combinations (chosen as if picked left-to-right
             -      e.g. [2,5,7,9] œc 2 -> [[2,5],[2,7],[2,9],[5,7],[5,9],[7,9]] )
        ⁸    - chain's left argument (to be on right of the following...)
       Þ     -   sort by:
      ¥      -     last two links as a dyad:
    ạ        -       absolute difference (vectorises)
     S       -       sum
         Ḣ   - head (since sorted this is just the first minimal choices from Y)
          ⁸  - chain's left argument
           ż - zip with (the chosen Y elements)

Answer 11

JavaScript (ES7), 100 bytes

New here; any tips/corrections would be appreciated! A previous attempt overlooked complications with sorting an array containing a NaN value, so hopefully I haven't missed anything this time.

(x,y,q=Infinity)=>y.map((u,j)=>(p=0,s=x.map((t,i)=>(u=y[i+j],p+=(t-u)**2,[t,u])),p)<q&&(q=p,r=s))&&r

Expects two arguments as X, Y, respectively. Try it online!

Appears to be similar to @Arnauld's solution

Explanation

Relies on the fact that given X, Y are sorted, there exists a solution of minimum cost matches where if all pairs are arranged to preserve the order of elements of X, all Y elements in the arrangement also preserve their order.

(x, y, q = Infinity) =>
    y.map((u, j) =>                   // iterate over indices of y
        (
            p=0,
            s=x.map((t, i) => (       // map each element of x to...
                    u = y[i+j],       // an element of y offset by j
                    p += (t-u)**2,    // accumulate the square of the difference
                    [t, u]            // new element of s
                )),
            p
        ) < q                         // if accumulated cost less than previous cost...
                                      // (if p is NaN, any comparison will return false and short circuit)
        && (q=p, r=s)                 // save cost, pair values respectively
    ) && r                            // return lowest-cost pairs