12

Considérons deux tableaux triés d'entiers et de taille et respectivement avec . Par exemple, , . $X$ $Y$ $m$ $n$ $m < n$ $X = (1,4)$ $Y = (2,10,11)$

On dit qu'une adaptation est un moyen d'appariement de chaque élément de avec un élément de de telle sorte que deux éléments de sont jumelés avec le même élément de . Le coût d'un appariement n'est que la somme des valeurs absolues des différences dans les paires. $X$ $Y$ $X$ $Y$

Par exemple, avec , nous pouvons faire les paires qui ont alors coûté . Si nous avions fait les paires le coût aurait été . Si nous avions fait les paires le coût aurait été . $X = (7,11)$ $Y = (2,10,11)$ $(7,2), (11,10)$ $5+1 = 6$ $(7,10), (11,11)$ $3+0 = 3$ $(7,11), (11,10)$ $4+1 = 5$

Comme autre exemple, prenons , . On peut faire les paires pour un coût de . Les paires coûtent . $X = (7,11,14)$ $Y = (2,10,11,18)$ $(7,2), (11,10), (14,11)$ $9$ $(7,10), (11,11), (14,18)$ $7$

La tâche consiste à écrire du code qui, étant donné deux tableaux triés d'entiers et , calcule une correspondance de coût minimum. $X$ $Y$

Cas de test

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

code-golf number array-manipulation Anush
la source

X ou Y auront-ils jamais des valeurs répétées?

@Mnemonic Non, ils ne le feront pas

Anush

2

Pour être clair, nous renvoyons l'appariement avec le coût minimum, pas le coût minimum.

Giuseppe

1

Pouvons-nous avoir plus d'exemples?

dylnan

Pouvons-nous supposer qu'il n'y a qu'une seule correspondance qui a un coût minimal?

dylnan

4

Brachylog , 16 octets

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

Essayez-le en ligne!

Explication

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

Puisque nous nous unissons Ià un entier au tout début, nous essayons des choses de petites valeurs de Ià grandes valeurs de I, ce qui signifie que la première fois que cela réussira sera nécessairement pour l'appariement avec les plus petites différences absolues.

Fatalize
la source

4

Gelée , 15 14 12 11 octets

Œ!ż€IASƊÞḢṁ

Essayez-le en ligne!

-1 octet merci à Jonathan Allan
-1 octet merci à M. Xcoder
-2 octets grâce à un éditeur anonyme

Force brute. Prend entrée en tant que , puis . $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.

dylnan
la source

Fonctionnerait L}à la place de ⁹L¤?

M. Xcoder

@ Mr.Xcoder Oui, merci!

dylnan

ÐṂḢ-> ÞḢpour enregistrer un octet.

Jonathan Allan

3

Haskell, 78 77 76 octets

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

TIO n'en a pas Data.Lists, donc pas de lien.

Fondamentalement, le même algorithme que celui vu dans la réponse de @ dylnan .

Edit: -1 octet grâce à @BMO.

nimi
la source

2

JavaScript (ES7), 121 octets

Prend les 2 tableaux dans la syntaxe de curry (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

Essayez-le en ligne!

Arnauld
la source

2

J , 24 octets

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

Essayez-le en ligne!

Explication / démonstration:

Un verbe dyadique, x f y

-/ trouve les différences

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

(0{]#~1>])"1 pour chaque ligne, ne gardez que les valeurs non positives et prenez la première:

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

[:,@: aplatit la liste (pour correspondre à la forme de l'argument de gauche)

[-soustraire le min. différences avec l'argument de gauche

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

[,. les assembler à l'argument de gauche:

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

Galen Ivanov
la source

1

Pyth , 18 octets

t#h.msaMbm.T,dvz.p

Essayez-le ici!

M. Xcoder
la source

1

Octave , 66 octets

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

Fonction anonyme qui prend des vecteurs de ligne X, Ycomme entrées et sorties d'une matrice à 2 lignes où chaque colonne est une paire de correspondance.

Essayez-le en ligne!

Luis Mendo
la source

1

Pyth , 16 octets

hosaMNCM*.pQ.cEl

Essayez-le en ligne ici ou vérifiez tous les cas de test en même temps ici .

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

Sok
la source

1

MATL , 16 octets

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

Les entrées sont Xdonc Y.

La correspondance est sortie avec les premières valeurs de chaque paire (c'est-à-dire X) sur la première ligne et les secondes valeurs de chaque paire sur la deuxième ligne.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

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]

Luis Mendo
la source

1

Gelée , (10?) 12 octets

^{10 octets si seuls les éléments de Y sont requis (voir commentaires) - je ne sais pas encore si c'est autorisé par spec (et peut-être que cela ne devrait pas l'être car d'autres réponses implémentent déjà ce détail).

Cela peut être réalisé en supprimant le dernier⁸ż .}

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

Un lien dyadique acceptant X à gauche et Y à droite.
( œc⁹L¤ạS¥ÞḢż@et les 10 octets œc⁹L¤ạS¥ÞḢfont de même avec Y à gauche et X à droite).

Essayez-le en ligne!

Comment?

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)

Jonathan Allan
la source

1

JavaScript (ES7), 100 octets

Nouveau ici; tous les conseils / corrections seraient appréciés! Une tentative précédente a négligé les complications liées au tri d'un tableau contenant une NaNvaleur, donc j'espère que je n'ai rien manqué cette fois.

(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

Attend deux arguments comme X , Y , respectivement. Essayez-le en ligne!

Semble être similaire à la solution de @ Arnauld

Explication

S'appuie sur le fait que, étant donné que X , Y sont triés, il existe une solution de correspondances de coût minimum où si toutes les paires sont arrangées pour préserver l'ordre des éléments de X , tous les éléments Y dans l'arrangement préservent également leur ordre.

(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

redondance
la source

Trouver la correspondance de coût minimum entre les tableaux d'entiers

Cas de test

Réponses:

Brachylog , 16 octets

Explication

Gelée , 15 14 12 11 octets

Haskell, 78 77 76 octets

JavaScript (ES7), 121 octets

J , 24 octets

Explication / démonstration:

Pyth , 18 octets

Octave , 66 octets

Pyth , 16 octets

MATL , 16 octets

Explication

Gelée , (10?) 12 octets

Comment?

JavaScript (ES7), 100 octets

Explication