Pertimbangkan dua array yang diurutkan dari integer dan Y dengan ukuran m dan n masing-masing dengan m < n . Misalnya X = ( 1 , 4 ) , Y = ( 2 , 10 , 11 ) .$X$$Y$$m$$n$$m < n$$X = (1,4)$$Y = (2,10,11)$

Kami mengatakan bahwa pencocokan adalah cara memasangkan setiap elemen dengan elemen Y sedemikian rupa sehingga tidak ada dua elemen X yang dipasangkan dengan elemen Y yang sama . Biaya pencocokan hanyalah jumlah dari nilai absolut dari perbedaan pasangan.$X$$Y$$X$$Y$

Sebagai contoh, dengan , Y = ( 2 , 10 , 11 ) kita dapat membuat pasangan ( 7 , 2 ) , ( 11 , 10 ) yang kemudian memiliki biaya 5 + 1 = 6 . Jika kita membuat pasangan ( 7 , 10 ) , ( 11 , 11 ) biayanya adalah 3 + $X = (7,11)$$Y = (2,10,11)$$(7,2), (11,10)$$5+1 = 6$$(7,10), (11,11)$ . Jika kita membuat pasangan ( 7 , 11 ) , ( 11 , 10 ) biayanya adalah 4 + 1 = 5 .$3+0 = 3$$(7,11), (11,10)$$4+1 = 5$

Sebagai contoh lain, ambil , Y = ( 2 , 10 , 11 , 18 ) . Kita dapat membuat pasangan ( 7 , 2 ) , ( 11 , 10 ) , ( 14 , 11 ) dengan biaya 9 . Pasangan ( 7 , 10 ) , ( 11 , 11 ) $X = (7,11,14)$$Y = (2,10,11,18)$$(7,2), (11,10), (14,11)$$9$ biaya 7 .$(7,10), (11,11), (14,18)$$7$

Tugasnya adalah menulis kode yang, mengingat dua array diurutkan dari integer dan Y , menghitung pencocokan biaya minimum.$X$$Y$

Uji kasus

[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]]

Brachylog , 16 byte

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

Cobalah online!

Penjelasan

∧
 ≜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
               ∧

Karena kami menyatukan Ike integer di awal, kami mencoba berbagai hal mulai dari nilai kecil Ihingga nilai besar I, yang berarti pertama kali berhasil akan tentu untuk pasangan dengan perbedaan absolut terkecil.

Jelly , 15 14 12 11 byte

Œ!ż€IASƊÞḢṁ

Cobalah online!

• -1 byte terima kasih kepada Jonathan Allan
• -1 byte terima kasih kepada Tn. Xcoder
• -2 byte berkat editor anonim

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

Haskell, 78 77 76 byte

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

TIO tidak punya Data.Lists, jadi tidak ada tautan.

Pada dasarnya algoritma yang sama seperti yang terlihat pada jawaban @ dylnan .

Sunting: -1 byte berkat @BMO.

JavaScript (ES7), 121 byte

Mengambil 2 array dalam sintaks currying (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

Cobalah online!

J , 24 byte

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

Cobalah online!

Penjelasan / Demonstrasi:

Kata kerja diad, x f y

-/ menemukan perbedaan

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

(0{]#~1>])"1 untuk setiap baris hanya simpan nilai-nilai non-positif dan ambil yang pertama:

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

[:,@: ratakan daftar (untuk mencocokkan bentuk argumen kiri)

[-kurangi min. perbedaan dari argumen kiri

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

[,. jahit mereka ke argumen kiri:

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

Pyth , 18 byte

t#h.msaMbm.T,dvz.p

Coba di sini!

Oktaf , 66 byte

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

Fungsi anonim yang mengambil vektor baris X, Ysebagai input dan output matriks 2-baris di mana setiap kolom adalah pasangan yang cocok.

Cobalah online!

Pyth , 16 byte

hosaMNCM*.pQ.cEl

Cobalah online di sini , atau verifikasi semua uji sekaligus di sini .

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

MATL , 16 byte

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

Inputnya X, lalu Y.

Pencocokan adalah output dengan nilai pertama dari setiap pasangan (yaitu, X) di baris pertama, dan nilai kedua dari setiap pasangan di baris kedua.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

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]

Jelly , (10?) 12 byte

^{10 byte jika hanya elemen Y yang diperlukan (lihat komentar) - tidak yakin apakah itu diizinkan oleh spec (dan mungkin seharusnya tidak karena jawaban lain sudah mengimplementasikan detail ini).
Ini dapat dicapai dengan menghapus trailing⁸ż .}

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

Sebuah link diadik yang menerima X di sebelah kiri dan Y di kanan.
( œc⁹L¤ạS¥ÞḢż@dan 10 byte œc⁹L¤ạS¥ÞḢmelakukan hal yang sama dengan Y di sebelah kiri dan X di sebelah kanan).

Cobalah online!

Bagaimana?

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)

JavaScript (ES7), 100 byte

Baru disini; tips / koreksi apa pun akan dihargai! Upaya sebelumnya mengabaikan komplikasi dengan menyortir array yang mengandung NaNnilai, jadi semoga saya tidak melewatkan apa pun saat ini.

(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

Mengharapkan dua argumen masing-masing sebagai X , Y. Cobalah online!

Tampaknya mirip dengan solusi @ Arnauld

Penjelasan

Bergantung pada fakta bahwa diberikan X , Y disortir, terdapat solusi kecocokan biaya minimum di mana jika semua pasangan diatur untuk mempertahankan urutan elemen X , semua elemen Y dalam pengaturan juga mempertahankan pesanan mereka.

(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