Permutacje w przebraniu


17

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)l1

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,...,n1)
  • odległość pomiędzy dwoma wektorami jest zdefiniowana jakol1u,v
    d(u,v)=i|uivi|.
  • 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.


Czy gwarantujemy, że wszystkie elementy v, będą większe niż 0? A przynajmniej nie 0?
Shaggy

1
Nie, wpisami vmogą być dowolne liczby całkowite. (Dodano kilka innych przykładów.)
flawr

Jeśli mogą to być dowolne liczby rzeczywiste, [1.6 2]jest to ważny przypadek testowy (zachłanny algorytm / sortowanie leksykograficzne daje złą odpowiedź).
histocrat

2
Duplikat w przebraniu? Nie jestem jednak pewien, czy powinien być zamknięty jako taki, ponieważ nie jest oczywiste, że jest to to samo zadanie (jak teraz udowodnione przez xnor).
Arnauld,

1
(W rzeczywistości nie jest to to samo zadanie, ale wszystkie rozwiązania związanego z nim wyzwania są rozwiązaniami tego.)
Arnauld

Odpowiedzi:


13

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 ja,jot że l ma kolejność, czyli gdzie ja<jot ale li>lj . 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:

|lii|+|ljj||lij|+|lji|.

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 li do i a druga od lj do j . Całkowity dystans, jaki pokonują, jest wyrażeniem po lewej stronie. Ponieważ i<j ale li>lj , 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).


genialny wgląd
Jonah

Uprościliście to, szukając kolejności .
mile

@miles To całkiem zabawne, zupełnie zapomniałem o tym wyzwaniu, mimo że napisałem odpowiedź, a Dennis ma dokładnie taką odpowiedź w języku Python, której pomogłem w golfa.
xnor

Ten „dowód wizualny” jest zgrabny. Wpadłem na ten sam pomysł, ale musiałem przedstawić każdy przypadek tej formuły, aby to udowodnić. Na marginesie, w tym poście pokazano kilka alternatyw uzyskiwania rang w Pythonie przy użyciu bibliotek stron trzecich .
Joel

5

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

1
Za każdym razem, gdy mnie to dziwi, czego 05AB1E nie może zrobić?
Przypadkowy facet

5
@Therandomguy Nie ma wielu rzeczy, których nie można zrobić w 05AB1E, ale jest całkiem źle w: wyzwaniach opartych na wyrażeniach regularnych; wyzwania oparte na macierzach (chociaż zostało to poprawione po kilku nowych wbudowaniach); brak wyimaginowanych liczb; wyzwania związane z datą / czasem; itp. Jednak, chociaż trudne, nadal można to zrobić zwykle. Aby podać dwa przykłady: Odliczanie dnia roboczego (przejdź do następnego dnia, a dzień tygodnia zostanie wykonany ręcznie); Quine sam wyprowadza binarnie (konwersja UTF-8 odbywa się ręcznie).
Kevin Cruijssen

@Grimy należy teraz naprawić :)
Data wygasła

3

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.


1
To też łamało mi mózg (lub najczęściej równoważne pytanie „czy działa na to chciwy algorytm?”). Najprostszym kontrprzykładem jest [0.6 1](zakładając, że mamy indeks 0), gdzie jeśli zoptymalizujesz dla pierwszej wartości, uzyskasz [1,0]wynik 1,4, ale jeśli zoptymalizujesz dla całego wektora, 1 jest bardziej wartościowy na drugiej pozycji dla wyniku 0,6.
histocrat


2

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.


2

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.


2
Minimalizowanie sumy (xy) podniesionej do kwadratu nie jest równoważne z minimalizowaniem sumy | xy |, ale zawsze daje prawidłową odpowiedź. Dlaczego tak jest? Czy nie may to minimalizuje |x-y| ale nie (x-y)2)?
Joel

1

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)

1

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 sol oblicza wszystkie permutacje (0,...,n-1), gdzie n jest niejawną długością tablicy wejściowej za[].

Dla każdej permutacji pobliczamy:

k=n-1+ja=0n-1(pja-zaja)2)
Jedyny powód do przewodzenia n-1 jest to, że ponownie wykorzystujemy wewnętrzny licznik sol aby zaoszczędzić kilka bajtów, ale nie ma to wpływu na końcowy wynik.

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



1

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).


Możesz przełączyć się na Python 2, abyś functoolsjuż więcej nie potrzebował .
Pan Xcoder,

reducejest zwykle przesada, szczególnie tutaj, gdzie dodajesz rzeczy. Myślę, że możesz po prostu zrobić sum(abs(p-q)for p,q in zip(x,a)).
xnor

0

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!



0

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.