Dado un vector -dimensional con las entradas reales, encontrar una permutación más cercano de con respecto a la -Distancia.
Detalles
- Si es más conveniente, puede utilizar permutaciones de en su lugar. Si hay varias permutaciones más cercanas, puede generar una o, alternativamente, todas.
- La distancia entre dos vectores se define como
- Si lo desea, puede suponer que la entrada consiste únicamente en enteros.
Ejemplos
[0.5 1] -> [1 2], [2 1]
c*[1 1 ... 1] -> any permutation
[1 4 2 6 2] -> [1 4 3 5 2], [1 4 2 5 3]
[1 3 5 4 1] -> [2 3 5 4 1], [1 3 5 4 2]
[7 7 3 2 5 6 4 2] -> [8 7 3 2 5 6 4 1], [8 7 3 1 5 6 4 2], [7 8 3 2 5 6 4 1], [7 8 3 1 5 6 4 2]
[-2 4 5 7 -1 9 3] -> [1 4 5 6 2 7 3], [2 4 5 6 1 7 3], [1 4 5 7 2 6 3], [2 4 5 7 1 6 3]
[0 4 2 10 -1 10 5] -> [1 4 2 6 3 7 5], [1 4 3 6 2 7 5], [2 4 3 6 1 7 5], [3 4 2 6 1 7 5], [1 4 2 7 3 6 5], [1 4 3 7 2 6 5], [2 4 3 7 1 6 5], [3 4 2 7 1 6 5]
Script de octava para generar más ejemplos.
v
, serán mayores que0
? O, al menos, no0
?v
pueden ser enteros. (Se agregaron algunos ejemplos más.)[1.6 2]
es un caso de prueba importante (el algoritmo codicioso / tipo lexicográfico da la respuesta incorrecta).Respuestas:
Python 2 , 60 bytes
Pruébalo en línea!
Utiliza indexación cero.
Un algoritmo rápido con una idea simple. Si en lugar de necesitamos para permutar la lista de entrada para que sea lo más cercano a( 1 , 2 , . . . , N ) como sea posible, debemos sólo una especie que, como lo demuestra a continuación. Ya que estamos en lugar permutando ( 1 , 2 , . . . , N ) , se elige la permutación que se ordenaron de la misma forma que la lista de entrada, al igual que en mi reto Imitar un ordenamiento (excepto la entrada puede tener repeticiones). (Editar: millas señaló este desafío más idéntico , donde Dennis tiene esta misma respuesta ).
Tenga en cuenta que la única propiedad de( 1 , 2 , . . . , N ) que usamos es que está ordenada, por lo que el mismo algoritmo que trabajaría para permutar cualquier lista dada para reducir al mínimo su distancia a cualquier lista fija.
En el código, el único propósito de
z=zip(l,range(len(l)))
es hacer que los elementos de entrada sean distintos, es decir, evitar vínculos, mientras se mantienen las mismas comparaciones entre elementos desiguales. Si la entrada que garantizamos no tiene repeticiones, podríamos eliminar esto y simplemente tenerlambda l:map(sorted(l).index,l)
.fuente
05AB1E , 7 bytes
Pruébalo en línea!
Explicación
fuente
Perl 6 , 44 bytes
Pruébalo en línea!
Codeblock anónimo que devuelve la primera permutación mínima con 0 indexación.
Explicación:
Creo que también podría deshacerme de ellos
.sum
y ordenarlos solo por la lista de valores absolutos, pero no estoy seguro de que esto sea realmente correcto, aunque supera mis casos de prueba actuales.fuente
[0.6 1]
(suponiendo que estamos indexados a 0), donde si optimiza para el primer valor obtiene[1,0]
una puntuación de 1.4, pero si optimiza para todo el vector, el 1 es más valioso en la segunda posición para una puntuación de 0.6.Jalea , 8 bytes
Pruébalo en línea!
fuente
Jalea , 5 bytes
Un enlace monádico que acepta una lista de números que produce una lista de enteros.
Pruébalo en línea! O vea el conjunto de pruebas .
¿Cómo?
NB
L
(longitud de) funcionaría en lugar deJ
dado queœ?
dado un número enteron
, a la derecha implícitamente haría que el rango[1..n]
funcione, peroJ
es explícito.fuente
Ruby ,
6360 bytesPruébalo en línea!
Aquí hay un truco matemático que también podría ser útil en otras respuestas: en lugar de minimizar la suma de los valores absolutos de las diferencias, maximizamos la suma de los productos. ¿Por qué funciona eso?
Minimizar la suma de
(x-y) squared
no es equivalente a minimizar la suma de|x-y|
, pero siempre dará una respuesta válida, solo prioriza la reducción de grandes diferencias sobre las pequeñas, mientras que el desafío real es indiferente entre las dos.Pero
(x-y)*(x-y)
=x*x+y*y-2*x*y
. Dado que los términos cuadrados siempre aparecerán en algún lugar de la suma para cualquier permutación, no afectan el resultado, por lo que podemos simplificarlo-2*x*y
. Los2
factores, por lo que podemos simplificar a-x*y
. Entonces, si cambiamos la minimización a la maximización, podemos simplificar ax*y
.Intuitivamente, esto es similar a observar que si estás tratando de maximizar los pies cuadrados usando un conjunto de paredes horizontales y verticales, es mejor emparejar paredes que estén cerca en tamaño para crear habitaciones que sean tan cerca del cuadrado como sea posible.
3*3 + 4*4 = 25
, mientras3*4 + 4*3 = 24
.Editar: ahorró tres bytes al generar y evaluar una cadena de formato en lugar de usar zip y sum.
fuente
Gaia , 13 bytes
Pruébalo en línea!
fuente
JavaScript (ES6), 61 bytes
Basado en la visión de xnor .
Pruébalo en línea!
Comentado
Javascript (ES6),
130128 bytesNo
debe haberduda es una forma más directa ...0 indexado.
Pruébalo en línea! (con salida indexada 1)
¿Cómo?
La función auxiliarsol calcula todas las permutaciones de ( 0 , . . . , N - 1 ) , dónde norte es la longitud implícita de la matriz de entrada un [] .
Para cada permutaciónpag , calculamos:
Finalmente devolvemos la permutación que conduce a la más pequeña.k .
fuente
Wolfram Language (Mathematica) , 14 bytes
Pruébalo en línea!
Basado en la visión de xnor .
fuente
Python 2 ,
149126112 bytes-23 bytes gracias al Sr. Xcoder
-14 bytes gracias a xnor
Pruébalo en línea!
Utiliza permutaciones de (0 ... n-1).
fuente
functools
.reduce
generalmente es excesivo, especialmente aquí donde estás agregando cosas. Creo que solo puedes hacersum(abs(p-q)for p,q in zip(x,a))
.sin paquete de permutación
Python 3 , 238 bytes
Pruébalo en línea!
fuente
Wolfram Language (Mathematica) , 57 bytes
Pruébalo en línea!
fuente
Japt
-g
, 12 bytesIntentalo
Para 0 indexado, reemplace los primeros 2 bytes con
m,
para asignar la matriz a sus índices.fuente
J ,
258 bytesPruébalo en línea!
Una respuesta mucho más corta basada en la brillante idea de xnor.
respuesta original
J , 25 bytes
Pruébalo en línea!
fuente