Dado um vetor dimensional com entradas reais, encontre uma permutação mais próxima de (1,2, ..., n) com relação à distância l_1 .$n$$v$$p$$(1,2,...,n)$$l_1$

Detalhes

• Se for mais conveniente, você pode usar permutações de $(0,1,...,n-1)$ . Se houver várias permutações mais próximas, você poderá produzir qualquer uma ou, alternativamente, todas elas.
• A distância $l_1$ entre dois vetores $u,v$ é definida como $$d(u,v) = \sum_i \vert u_i-v_i\vert.$$
• Se desejar, você pode assumir que a entrada consiste apenas em números inteiros.

Exemplos

[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 oitava para gerar mais exemplos.

Python 2 , 60 bytes

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

Experimente online!

Usa indexação zero.

Um algoritmo rápido com uma ideia simples. Se em vez precisam permutar a lista de entrada para torná-lo tão perto de $(1,2,...,n)$ que possível, devemos apenas uma espécie, como comprovado abaixo. Desde que nós estamos permutando vez $(1,2,...,n)$ , nós escolhemos a permutação daquele ordenado da mesma forma que a lista de entrada, como no meu desafio Imitar uma ordenação (exceto a entrada pode ter repete). (Edit: miles apontou esse desafio mais idêntico , onde Dennis tem a mesma resposta .)

Reivindicação: Uma permutação da lista $l$ que minimiza a sua distância a $(1,2,...,n)$ é $l$ classificados.

Prova: considere alguma outra permutação $l'$ de $l$ . Vamos provar que não pode ser melhor do que $l$ resolvi.

Escolha dois índices $i,j$ que $l'$ está fora de ordem, que é onde $i<j$ mas $l'_i > l'_j$ . Mostramos que a troca deles não pode aumentar a distância de $(1,2,...,n)$ . Observamos que o swap altera a contribuição desses dois elementos da seguinte maneira:

$$|l'_i - i | + |l'_j - j | \to |l'_i - j | + |l'_j - i|.$$

Aqui está uma maneira elegante de mostrar que isso não pode ser um aumento. Considere duas pessoas andando em uma linha numérica, uma que vai de $l'_i$ para $i$ a outra de $l'_j$ para $j$ . A distância total que andam é a expressão à esquerda. Como $i<j$ mas $l'_i > l'_j$ , eles trocam quem é mais alto na linha numérica, o que significa que devem atravessar em algum momento de suas caminhadas, chame de $p$ . Mas quando eles atingem $p$, eles poderiam trocar seus destinos e percorrer a mesma distância total. E então, não pode ser pior para eles terem caminhado para seus destinos trocados desde o início, em vez de usar $p$ como um waypoint, o que fornece a distância total no lado direito.

Assim, dois elementos de triagem para fora-de-fim em $l'$ faz com que o seu raio de $(1,2,...,n)$ menor ou o mesmo. Repetindo este processo irá classificar $l$ eventualmente. Portanto, $l$ classificado é pelo menos tão bom quanto $l'$ para qualquer escolha de $l'$ , o que significa ótimo ou vinculado ao ideal.

Note-se que a única propriedade de $(1,2,...,n)$ que usamos é que ele é classificado, de modo que o mesmo algoritmo iria trabalhar para permutar qualquer lista dada para minimizar o seu raio de qualquer lista fixa.

No código, o único objetivo de z=zip(l,range(len(l)))é diferenciar os elementos de entrada, ou seja, evitar vínculos, mantendo as mesmas comparações entre elementos desiguais. Se a entrada que garantimos não tiver repetições, poderíamos removê-la e apenas ter lambda l:map(sorted(l).index,l).

05AB1E , 7 bytes

āœΣαO}н

Experimente online!

Explicação

ā              # 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

Perl 6 , 44 bytes

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

Experimente online!

Codeblock anônimo que retorna a primeira permutação mínima com indexação 0.

Explicação:

{                                          }   # 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

Eu acho que também posso me livrar .sume classificar apenas pela lista de valores absolutos, mas não tenho certeza se isso é realmente correto, apesar de passar nos meus casos de teste atuais.

Geléia , 8 bytes

LŒ!ạS¥ÐṂ

Experimente online!

Geléia , 5 bytes

Œ¿œ?J

Um link monádico que aceita uma lista de números que produz uma lista de números inteiros.

Experimente online! Ou veja a suíte de testes .

Quão?

Œ¿œ?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(comprimento de) funcionaria no lugar do Jdado œ?dado um número inteiro;, nà direita, implicitamente aumentaria o intervalo [1..n]para trabalhar, mas Jé explícito.

Ruby , 63 60 bytes

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

Experimente online!

Há um truque de matemática aqui que também pode ser útil em outras respostas - em vez de minimizar a soma dos valores absolutos das diferenças, maximizamos a soma dos produtos. Por que isso funciona?

Minimizar a soma de (x-y) squarednão é equivalente a minimizar a soma de |x-y|, mas sempre dará uma resposta válida, apenas prioriza a redução de grandes diferenças em relação às pequenas, enquanto o desafio real é indiferente entre as duas.

Mas (x-y)*(x-y)= x*x+y*y-2*x*y. Como os termos quadrados sempre aparecem em algum lugar da soma de qualquer permutação, eles não afetam o resultado, para que possamos simplificá-lo -2*x*y. Os 2fatores fora, para que possamos simplificar -x*y. Então, se mudarmos de minimizado para maximizado, podemos simplificar para x*y.

Intuitivamente, isso é semelhante à observação de que, se você estiver tentando maximizar a metragem quadrada usando um conjunto de paredes horizontais e verticais, é melhor emparelhar paredes com tamanho aproximado umas das outras para criar salas que sejam o mais próximo possível da praça. 3*3 + 4*4 = 25enquanto 3*4 + 4*3 = 24.

Editar: salvou três bytes gerando e avaliando uma sequência de formato em vez de usar zip e soma.

Gaia , 13 bytes

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

Experimente online!

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)

JavaScript (ES6), 61 bytes

Baseado no insight do xnor .

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

Experimente online!

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

Não  deve ser  definitivamente é uma forma mais direta ...

Indexado a 0.

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

Experimente online! (com saída indexada 1)

Quão?

A função auxiliar $g$ calcula todas as permutações de $(0,...,n-1)$, Onde $n$ é o comprimento implícito da matriz de entrada $a[\;]$.

Para cada permutação $p$, calculamos:

Eventualmente, retornamos a permutação que leva ao menor $k$.

Wolfram Language (Mathematica) , 14 bytes

#@*#&@Ordering

Experimente online!

Baseado no insight do xnor .

Python 2 , 149 126 112 bytes

-23 bytes graças a Mr. Xcoder

-14 bytes graças ao 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)))

Experimente online!

Usa permutações de (0 ... n-1).

sem qualquer pacote de permutação

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]

Experimente online!

Wolfram Language (Mathematica) , 57 bytes

f@n_:=MinimalBy[Permutations@Range@Length@n,Tr@Abs[n-#]&]

Experimente online!

Japonês -g , 12 bytes

Êõ á ñÈíaU x

Tente

Para indexado 0, substitua os 2 primeiros bytes por m,para mapear a matriz para seus í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

J , ²⁵ bytes 8

#\/:@/:]

Experimente online!

Uma resposta muito mais curta, com base na brilhante ideia do xnor.

resposta original

J , 25 bytes

(0{]/:1#.|@-"1)i.@!@#A.#\

Experimente online!