Permutaciones disfrazadas

17

Dado un n vector -dimensional v con las entradas reales, encontrar una permutación más cercano pag de (1,2,...,norte) con respecto a la l1 -Distancia.

Detalles

  • Si es más conveniente, puede utilizar permutaciones de (0 0,1,...,norte-1) en su lugar. Si hay varias permutaciones más cercanas, puede generar una o, alternativamente, todas.
  • La distancia l1 entre dos vectores tu,v se define como
    re(tu,v)=yoEl |tuyo-vyoEl |.
  • 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.

falla
fuente
¿Estamos garantizados de que todos los elementos de v, serán mayores que 0? O, al menos, no 0?
Shaggy
1
No, las entradas de vpueden ser enteros. (Se agregaron algunos ejemplos más.)
flawr
Si pueden ser números reales, entonces [1.6 2]es un caso de prueba importante (el algoritmo codicioso / tipo lexicográfico da la respuesta incorrecta).
histocrat
2
¿Duplicado disfrazado?Sin embargo, no estoy seguro de que deba cerrarse como tal, porque no es obvio que sea la misma tarea (como lo demuestra ahora xnor).
Arnauld
1
(De hecho, no es la misma tarea, pero todas las soluciones del desafío vinculado son soluciones de esta)
Arnauld

Respuestas:

13

Python 2 , 60 bytes

def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

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,...,norte) como sea posible, debemos sólo una especie que, como lo demuestra a continuación. Ya que estamos en lugar permutando (1,2,...,norte) , 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 ).

Reclamación: una permutación de la lista l que minimiza su distancia a (1,2,...,norte) es l ordenadas.

Prueba: Considere alguna otra permutación l de l . Probaremos que no puede ser mejor quel ordenadas.

Elija dos índices yo,j que l tenga fuera de orden, que es donde yo<j pero lyo>lj . Se demuestra que el canje de ellos no puede aumentar la distancia a (1,2,...,norte) . Observamos que swap cambia la contribución de estos dos elementos de la siguiente manera:

El |lyo-yoEl |+El |lj-jEl |El |lyo-jEl |+El |lj-yoEl |.

Aquí hay una buena manera de mostrar que esto no puede ser un aumento. Considere a dos personas caminando en una recta numérica, una que va de lyo a yo y la otra de lj a j . La distancia total que caminan es la expresión de la izquierda. Como yo<j pero lyo>lj , cambian quién es más alto en la recta numérica, lo que significa que deben cruzar en algún momento durante sus caminatas, llámelo pag . Pero cuando alcanzan pag, podrían intercambiar sus destinos y caminar la misma distancia total. Y luego, no puede ser peor para ellos haber caminado a sus destinos intercambiados desde el principio en lugar de usarpag como punto de referencia, lo que da la distancia total en el lado derecho.

Así, la clasificación de dos elementos de fuera de la orden en l que hace que su distancia a (1,2,...,norte) menor o igual. La repetición de este proceso ordenará l eventualmente. Así, l ordenadas es al menos tan buena como l para cualquier elección de l , lo que significa que como óptimo o atadas para la óptima.

Tenga en cuenta que la única propiedad de (1,2,...,norte) 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 tener lambda l:map(sorted(l).index,l).

xnor
fuente
idea brillante
Jonás
Has simplificado esto para encontrar el pedido .
millas
@miles Eso es bastante divertido, me olvidé por completo de ese desafío a pesar de que escribí una respuesta, y Dennis tiene esta respuesta exacta de Python que ayudé al golf.
xnor
Esa "prueba visual" es clara. Tuve la misma idea, pero tuve que presentar cada caso de esa fórmula para probarlo. Como comentario adicional, en esta publicación se muestran algunas alternativas para obtener rangos en Python utilizando bibliotecas de terceros .
Joel
5

05AB1E , 7 bytes

āœΣαO}н

Pruébalo en línea!


Explicación

ā              # get the numbers 1 to len(input) + 1
 œ             # Permutations of this
  Σ  }         # Sort by ...
   α           # Absolute difference
    O          # Sum these
      н        # And get the first one 
               # implicitly print
Datos caducados
fuente
1
Cada vez que estoy sorprendido por esto, ¿qué 05AB1E no puede hacer?
El tipo al azar
55
@Therandomguy No hay muchas cosas que no se puedan hacer en 05AB1E, pero es bastante malo en: desafíos basados ​​en expresiones regulares; desafíos basados ​​en matrices (aunque esto se ha mejorado después de algunas nuevas incorporaciones); falta de números imaginarios; desafíos relacionados con la fecha / hora; etc. Sin embargo, aunque difícil, todavía se puede hacer generalmente. Para dar dos ejemplos: la cuenta regresiva del día laboral (ir al día siguiente y obtener el día de la semana se hace manualmente); Quine se genera en binario (la conversión UTF-8 se realiza manualmente).
Kevin Cruijssen
@Grimy debería arreglarse ahora :)
Datos
3

Perl 6 , 44 bytes

{permutations(+$_).min((*[]Z-$_)>>.abs.sum)}

Pruébalo en línea!

Codeblock anónimo que devuelve la primera permutación mínima con 0 indexación.

Explicación:

{                                          }   # Anonymous code block
 permutations(+$_)                             # From the permutations with the same length
                  .min(                   )    # Find the minimum by
                                      .sum       # The sum of
                                >>.abs           # The absolute values of
                       (*[]Z-$_)                 # The zip subtraction with the input

Creo que también podría deshacerme de ellos .sumy 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.

Jo King
fuente
1
Eso también me estaba rompiendo el cerebro (o la pregunta casi equivalente de "¿funciona un algoritmo codicioso para esto?"). El contraejemplo más simple es [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.
histocrat
2

Jalea , 5 bytes

Œ¿œ?J

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?

Œ¿œ?J - Link: list of numbers, X
Œ¿    - Index of X in a lexicographically sorted list of
         all permutations of X's items
    J - range of length of X
  œ?  - Permutation at the index given on the left of the
         items given on the right

NB L(longitud de) funcionaría en lugar de Jdado que œ?dado un número entero n, a la derecha implícitamente haría que el rango [1..n]funcione, pero Jes explícito.

Jonathan Allan
fuente
2

Ruby , 63 60 bytes

->v{[*1..v.size].permutation.max_by{|p|eval [p,0]*'*%p+'%v}}

Prué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) squaredno 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. Los 2factores, por lo que podemos simplificar a -x*y. Entonces, si cambiamos la minimización a la maximización, podemos simplificar a x*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.

histocrat
fuente
2
Minimizar la suma de (xy) al cuadrado no es equivalente a minimizar la suma de | xy |, pero siempre dará una respuesta válida. ¿Por qué es el caso? ¿No hayy que minimiza El |X-yEl | pero no (X-y)2?
Joel
1

Gaia , 13 bytes

e:l┅f⟪D†Σ⟫∫ₔ(

Pruébalo en línea!

e:		| eval and dup input
l┅f		| push permutations of [1..length(input)]
⟪   ⟫∫ₔ		| iterate over the permutations, sorting with minimum first
 D†Σ		| the sum of the absolute difference of the paired elements
       (	| and select the first (minimum)
Giuseppe
fuente
1

JavaScript (ES6), 61 bytes

Basado en la visión de xnor .

a=>[...a].map(g=n=>g[n]=a.sort((a,b)=>a-b).indexOf(n,g[n])+1)

Pruébalo en línea!

Comentado

a =>                    // a[] = input array
  [...a]                // create a copy of a[] (unsorted)
  .map(g = n =>         // let g be in a object; for each value n in the copy of a[]:
    g[n] =              //   update g[n]:
      a.sort(           //     sort a[] ...
        (a, b) => a - b //       ... in ascending order
      ).indexOf(        //     and find the position
        n,              //       of n in this sorted array,
        g[n]            //       starting at g[n] (interpreted as 0 if undefined)
      ) + 1             //     add 1
  )                     // end of map()

Javascript (ES6),  130  128 bytes

No  debe haber  duda es una forma más directa ...

0 indexado.

a=>(m=g=(k,p=[])=>1/a[k]?(h=i=>i>k||g(k+1,b=[...p],b.splice(i,0,k),h(-~i)))``:p.map((v,i)=>k+=(v-=a[i])*v)|k>m||(R=p,m=k))(0)&&R

Pruébalo en línea! (con salida indexada 1)

¿Cómo?

La función auxiliar sol calcula todas las permutaciones de (0 0,...,norte-1), dónde norte es la longitud implícita de la matriz de entrada un[].

Para cada permutación pag, calculamos:

k=norte-1+yo=0 0norte-1(pagyo-unyo)2
La única razón para liderar norte-1 es que reutilizamos el contador interno de sol para guardar algunos bytes, pero no tiene impacto en el resultado final.

Finalmente devolvemos la permutación que conduce a la más pequeña. k.

Arnauld
fuente
1

Python 2 , 149 126 112 bytes

-23 bytes gracias al Sr. Xcoder

-14 bytes gracias a xnor

from itertools import*
f=lambda a:min(permutations(range(len(a))),key=lambda x:sum(abs(a-b)for a,b in zip(x,a)))

Pruébalo en línea!

Utiliza permutaciones de (0 ... n-1).

Hiatsu
fuente
Puede cambiar a Python 2, para que ya no lo necesite functools.
Sr. Xcoder
reducegeneralmente es excesivo, especialmente aquí donde estás agregando cosas. Creo que solo puedes hacer sum(abs(p-q)for p,q in zip(x,a)).
xnor
0

sin paquete de permutación

Python 3 , 238 bytes

def p(a,r,l):
 if r==[]:l+=[a];return
 for i in range(len(r)):
  p(a+[r[i]],r[:i]+r[i+1:],l)
def m(l):
 s=(float("inf"),0);q=[];p([],list(range(len(l))),q)
 for t in q:D=sum(abs(e-f)for e,f in zip(l,t));s=(D,t)if D<s[0]else s
 return s[1]

Pruébalo en línea!

david
fuente
0

Japt -g , 12 bytes

Êõ á ñÈíaU x

Intentalo

Para 0 indexado, reemplace los primeros 2 bytes con m,para asignar la matriz a sus índices.

Êõ á ñÈíaU x     :Implicit input of array U
Ê                :Length
 õ               :Range [0,Ê]
   á             :Permutations
     ñÈ          :Sort by
       í U       :  Interleave with U
        a        :  Reduce each pair by absolute difference
           x     :  Reduce resulting array by addition
                 :Implicit output of first sub-array
Lanudo
fuente