Biorąc pod uwagę $n$ wymiarowy wektor $v$ z rzeczywistymi wpisami, znajdź najbliższą permutację $p$ wynoszącą w odniesieniu do odległości .$(1,2,...,n)$$l_1$

Detale

• Jeśli jest to wygodniejsze, możesz zamiast tego użyć permutacji . Jeśli istnieje wiele najbliższych kombinacji, możesz wyprowadzić dowolną lub alternatywnie wszystkie z nich.$(0,1,...,n-1)$
• odległość pomiędzy dwoma wektorami jest zdefiniowana jako$l_1$$u,v$ $$d(u,v) = \sum_i \vert u_i-v_i\vert.$$
• Jeśli chcesz, możesz założyć, że dane wejściowe składają się wyłącznie z liczb całkowitych.

Przykłady

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

Skrypt Octave do generowania większej liczby przykładów.

Python 2 , 60 bajtów

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

Wypróbuj online!

Wykorzystuje indeksowanie zerowe.

Szybki algorytm z prostym pomysłem. Gdybyśmy zamiast tego trzeba permutacji listę wejściowy, aby go jak najbliżej $(1,2,...,n)$ , jak to możliwe, powinniśmy po prostu rodzaj to, jak udowodniono poniżej. Ponieważ jesteśmy zamiast permutacji $(1,2,...,n)$ , wybieramy permutacji że zamówione w ten sam sposób jak listy wejściowej, jak w moim wyzwaniem Naśladuj uporządkowanie (z wyjątkiem wejścia mogą mieć powtórzeń). (Edycja: mile wskazało na to bardziej identyczne wyzwanie , na które Dennis ma tę samą odpowiedź ).

Twierdzenie: permutacją lista $l$ , która minimalizuje jej odstęp $(1,2,...,n)$ jest $l$ sortowane.

Dowód: Zastanów się nad inną permutacją $l'$ z $l$ . Będziemy udowodnić, że nie może być lepiej niż $l$ sortowane.

Wybierz dwa indeksy $i,j$ że $l'$ ma kolejność, czyli gdzie $i<j$ ale $l'_i > l'_j$ . Możemy zobaczyć, że ich wymiany nie może zwiększyć odległość $(1,2,...,n)$ . Zwracamy uwagę, że zmienia wymiany wkładu tych dwóch elementów w następujący sposób:

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

Oto fajny sposób, aby pokazać, że nie może to być wzrost. Rozważmy dwie osoby idące po linii liczbowej, jedna biegnie od $l'_i$ do $i$ a druga od $l'_j$ do $j$ . Całkowity dystans, jaki pokonują, jest wyrażeniem po lewej stronie. Ponieważ $i<j$ ale $l'_i > l'_j$ , zmieniają, kto jest wyższy na linii liczbowej, co oznacza, że ​​muszą przejść w pewnym momencie podczas spacerów, nazywają to $p$ . Ale kiedy osiągną $p$, mogliby następnie zamienić swoje miejsca docelowe i przejść ten sam łączny dystans. A potem nie może być gorsze, że od samego początku szli do zamienionych miejsc docelowych, zamiast używać $p$ jako punktu pośredniego, co daje całkowity dystans po prawej stronie.

Tak więc, dwie sortowania poza kolejnością elementów w $l'$ sprawia, że jej odległość do $(1,2,...,n)$ mniejsze lub sam. Powtarzając ten proces będzie sortować $l$ ostatecznie. Tak więc, sortowane $l$ jest co najmniej tak dobre jak $l'$ dla dowolnego wyboru $l'$ , co oznacza, że ​​jest tak optymalne lub powiązane dla optymalnego.

Należy pamiętać, że tylko własność $(1,2,...,n)$ , które użyliśmy jest to, że sortowane, tak samo algorytm będzie działać do permutacji dowolną listę zminimalizować dystans do dowolnej ustalonej listy.

W kodzie jedynym celem z=zip(l,range(len(l)))jest rozróżnienie elementów wejściowych, czyli uniknięcie powiązań, przy jednoczesnym zachowaniu tych samych porównań między nierównymi elementami. Jeśli dane wejściowe gwarantujemy, że nie będziemy powtarzać, możemy to usunąć i po prostu mieć lambda l:map(sorted(l).index,l).

05AB1E , 7 bajtów

āœΣαO}н

Wypróbuj online!

Wyjaśnienie

ā              # 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 bajtów

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

Wypróbuj online!

Anonimowy blok kodu, który zwraca pierwszą minimalną permutację z 0 indeksowaniem.

Wyjaśnienie:

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

Myślę, że mógłbym również pozbyć się .sumi posortować według listy wartości bezwzględnych, ale nie jestem pewien, czy to rzeczywiście jest poprawne, choć przechodzi moje obecne przypadki testowe.

Galaretka , 8 bajtów

LŒ!ạS¥ÐṂ

Wypróbuj online!

Galaretka , 5 bajtów

Œ¿œ?J

Monadyczny link akceptujący listę liczb, która daje listę liczb całkowitych.

Wypróbuj online! Lub zobacz pakiet testowy .

W jaki sposób?

Œ¿œ?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

Uwaga L(długość) działałaby zamiast Jod œ?podanej liczby całkowitej n, po prawej domyślnie tworzyłby zakres [1..n]do pracy, ale Jjest jawny.

Rubin , 63 60 bajtów

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

Wypróbuj online!

Jest tutaj sztuczka matematyczna, która może być pomocna także w innych odpowiedziach - zamiast minimalizować sumę wartości bezwzględnych różnic, maksymalizujemy sumę produktów. Dlaczego to działa?

Minimalizowanie sumy (x-y) squarednie jest równoważne z minimalizowaniem sumy |x-y|, ale zawsze da prawidłową odpowiedź, po prostu priorytetem jest zmniejszenie dużych różnic nad małymi, podczas gdy rzeczywiste wyzwanie jest obojętne między nimi.

Ale (x-y)*(x-y)= x*x+y*y-2*x*y. Ponieważ wyrażenia kwadratowe zawsze pojawiają się gdzieś w sumie dla dowolnej permutacji, nie wpływają one na wynik, więc możemy to uprościć -2*x*y. Te 2czynniki out, więc możemy uprościć do -x*y. Następnie, jeśli zmienimy minimalizację na maksymalizację, możemy to uprościć x*y.

Intuicyjnie jest to podobne do obserwowania, że ​​jeśli próbujesz zmaksymalizować materiał kwadratowy za pomocą zestawu ścian poziomych i zestawu ścian pionowych, najlepiej sparować ściany o rozmiarach zbliżonych do siebie, aby stworzyć pomieszczenia, które są jak najbliżej kwadratu, jak to możliwe. 3*3 + 4*4 = 25, podczas gdy 3*4 + 4*3 = 24.

Edycja: Zapisano trzy bajty, generując i oceniając ciąg formatu zamiast używać zip i sumy.

Gaia , 13 bajtów

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

Wypróbuj 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 bajtów

Na podstawie wglądu xnor .

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

Wypróbuj online!

Skomentował

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 bajtów

Nie  musi być  na pewno jest bardziej bezpośredni sposób ...

0-indeksowane.

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

Wypróbuj online! (z wyjściem 1-indeksowanym)

W jaki sposób?

Funkcja pomocnika $g$ oblicza wszystkie permutacje $(0,...,n-1)$, gdzie $n$ jest niejawną długością tablicy wejściowej $a[\;]$.

Dla każdej permutacji $p$obliczamy:

W końcu zwracamy permutację, która prowadzi do najmniejszej $k$.

Wolfram Language (Mathematica) , 14 bajtów

#@*#&@Ordering

Wypróbuj online!

Na podstawie wglądu xnor .

Python 2 , 149 126 112 bajtów

-23 bajty dzięki Mr. Xcoder

-14 bajtów dzięki 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)))

Wypróbuj online!

Wykorzystuje permutacje (0 ... n-1).

bez żadnego pakietu permutacji

Python 3 , 238 bajtów

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]

Wypróbuj online!

Wolfram Language (Mathematica) , 57 bajtów

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

Wypróbuj online!

Japt -g , 12 bajtów

Êõ á ñÈíaU x

Spróbuj

W przypadku indeksowania 0 zamień pierwsze 2 bajty m,na, aby zamiast tego zamapować tablicę na jej indeksy.

Êõ á ñÈí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 , ²⁵ 8 bajtów

#\/:@/:]

Wypróbuj online!

Znacznie krótsza odpowiedź oparta na genialnym pomyśle Xnora.

oryginalna odpowiedź

J , 25 bajtów

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

Wypróbuj online!