12

Considere dos ordenados arrays de enteros y de tamaño y , respectivamente, con . Por ejemplo , . $X$ $Y$ $m$ $n$ $m < n$ $X = (1,4)$ $Y = (2,10,11)$

Se dice que un juego es algún modo de emparejamiento de cada elemento de con un elemento de de tal manera que no hay dos elementos de están emparejados con el mismo elemento de . El costo de una coincidencia es solo la suma de los valores absolutos de las diferencias en los pares. $X$ $Y$ $X$ $Y$

Por ejemplo, con , podemos hacer los pares que luego han costado . Si hubiéramos formado los pares el costo habría sido . Si hubiéramos hecho los pares el costo habría sido . $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$

Como otro ejemplo, tome , . Podemos hacer los pares por un costo de . Los pares cuestan . $X = (7,11,14)$ $Y = (2,10,11,18)$ $(7,2), (11,10), (14,11)$ $9$ $(7,10), (11,11), (14,18)$ $7$

La tarea es escribir código que, dados dos arreglos ordenados de enteros e , calcule una coincidencia de costo mínimo. $X$ $Y$

Casos de prueba

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

¿X o Y alguna vez tendrán valores repetidos?

@Mnemonic No, no lo harán

Anush

2

Para ser claros, devolvemos la correspondencia con el costo mínimo, no el costo mínimo.

Giuseppe

1

¿Podemos tener más ejemplos?

dylnan

¿Podemos suponer que solo hay una coincidencia que tiene un costo mínimo?

dylnan

4

Brachylog , 16 bytes

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

Pruébalo en línea!

Explicación

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

Como nos unificamos Ia un número entero desde el principio, intentamos cosas desde valores pequeños Ihasta valores grandes de I, lo que significa que la primera vez que tendrá éxito será necesariamente para el emparejamiento con las diferencias absolutas más pequeñas.

Fatalizar
fuente

4

Jalea , 15 14 12 11 bytes

Œ!ż€IASƊÞḢṁ

Pruébalo en línea!

-1 byte gracias a Jonathan Allan
-1 byte gracias al Sr. Xcoder
-2 bytes gracias a un editor anónimo

Fuerza bruta. Toma de entrada como entonces . $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
fuente

¿ L}Funcionaría en lugar de ⁹L¤?

Sr. Xcoder

@ Mr.Xcoder Sí, gracias!

dylnan

ÐṂḢ-> ÞḢpara guardar un byte.

Jonathan Allan

3

Haskell, 78 77 76 bytes

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

TIO no tiene Data.Lists, así que no hay enlace.

Básicamente, el mismo algoritmo que se ve en la respuesta de @ dylnan .

Editar: -1 byte gracias a @BMO.

nimi
fuente

2

JavaScript (ES7), 121 bytes

Toma las 2 matrices en sintaxis 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

Pruébalo en línea!

Arnauld
fuente

2

J , 24 bytes

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

Pruébalo en línea!

Explicación / Demostración:

Un verbo diádico x f y

-/ encuentra las diferencias

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

(0{]#~1>])"1 para cada fila, mantenga solo los valores no positivos y tome el primero:

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

[:,@: aplana la lista (para que coincida con la forma del argumento izquierdo)

[-restar el min. diferencias con el argumento izquierdo

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

[,. coserlos al argumento izquierdo:

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

Galen Ivanov
fuente

1

Pyth , 18 bytes

t#h.msaMbm.T,dvz.p

Pruébalo aquí!

Sr. Xcoder
fuente

1

Octava , 66 bytes

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

Función anónima que toma vectores de fila X, Ycomo entradas y salidas de una matriz de 2 filas donde cada columna es un par de coincidencia.

Pruébalo en línea!

Luis Mendo
fuente

1

Pyth , 16 bytes

hosaMNCM*.pQ.cEl

Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

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
fuente

1

MATL , 16 bytes

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

Las entradas son X, entonces Y.

La coincidencia se genera con los primeros valores de cada par (es decir, X) en la primera línea y los segundos valores de cada par en la segunda línea.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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
fuente

1

Jalea , (10?) 12 bytes

^{10 bytes si solo se requieren los elementos de Y (ver comentarios); sin embargo, no estoy seguro de si está permitido por la especificación (y tal vez no debería serlo ya que otras respuestas ya implementan este detalle).

Esto se puede lograr eliminando el final⁸ż .}

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

Un enlace diádico que acepta X a la izquierda e Y a la derecha.
( œc⁹L¤ạS¥ÞḢż@y los 10 bytes œc⁹L¤ạS¥ÞḢhacen lo mismo con Y a la izquierda y X a la derecha).

Pruébalo en línea!

¿Cómo?

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
fuente

1

JavaScript (ES7), 100 bytes

Nuevo aquí; cualquier consejo / correcciones sería apreciado! Un intento anterior pasó por alto las complicaciones al ordenar una matriz que contiene un NaNvalor, por lo que espero no haber perdido nada esta vez.

(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

Espera dos argumentos como X , Y , respectivamente. Pruébalo en línea!

Parece ser similar a la solución de @ Arnauld

Explicación

Se basa en el hecho de que dado X , Y están ordenados, existe una solución de coincidencias de costo mínimo donde si todos los pares están dispuestos para preservar el orden de los elementos de X , todos los elementos Y en el arreglo también conservan su orden.

(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

redundancia
fuente

Encuentre la coincidencia de costo mínimo entre matrices de enteros

Casos de prueba

Respuestas:

Brachylog , 16 bytes

Explicación

Jalea , 15 14 12 11 bytes

Haskell, 78 77 76 bytes

JavaScript (ES7), 121 bytes

J , 24 bytes

Explicación / Demostración:

Pyth , 18 bytes

Octava , 66 bytes

Pyth , 16 bytes

MATL , 16 bytes

Explicación

Jalea , (10?) 12 bytes

¿Cómo?

JavaScript (ES7), 100 bytes

Explicación