Wprowadzenie

Załóżmy, że masz losową permutację nobiektów. Permutacja jest zamknięta w pudełku, więc nie masz pojęcia, który z n!nich jest możliwy. Jeśli udało ci się zastosować permutację do nróżnych obiektów, możesz natychmiast wywnioskować jej tożsamość. Możesz jednak zastosować permutację tylko do nwektorów binarnych o długości , co oznacza, że ​​będziesz musiał ją zastosować kilka razy, aby ją rozpoznać. Oczywiście, zastosowanie go do nwektorów za pomocą tylko jednego 1działa, ale jeśli jesteś sprytny, możesz to zrobić za pomocą log(n)aplikacji. Kod dla tej metody będzie dłuższy, jednak ...

Jest to wyzwanie eksperymentalne, w którym wynik jest kombinacją długości kodu i złożoności zapytań , co oznacza liczbę wywołań procedury pomocniczej. Specyfikacja jest trochę długa, więc trzymaj się mnie.

Zadanie

Twoim zadaniem jest napisanie nazwanej funkcji (lub najbliższego odpowiednika), f która przyjmuje jako dane wejściowe dodatnią liczbę całkowitą noraz permutację ppierwszych nliczb całkowitych, przy użyciu indeksowania 0 lub 1. Jego wynikiem jest permutacja p. Nie masz jednak pbezpośredniego dostępu do permutacji . Jedyne, co możesz z tym zrobić, to zastosować go do dowolnego wektora nbitów. W tym celu należy użyć funkcji pomocniczej, Pktóra przyjmuje permutację pi wektor bitów vi zwraca permutowany wektor, którego p[i]współrzędna zawiera bit v[i]. Na przykład:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

Możesz zastąpić „bity” dowolnymi dwiema odrębnymi wartościami, takimi jak 3i -4, i 'a'i 'b', i nie trzeba ich naprawiać, więc możesz dzwonić Pzarówno z tym samym, jak [-4,3,3,-4]i [2,2,2,1]tym samym f. Definicja Pnie jest wliczana do wyniku.

Punktacja

Złożoność zapytań od rozwiązania na danym wejściu jest liczba połączeń sprawia, że do funkcji pomocniczych P. Aby ta miara była jednoznaczna, twoje rozwiązanie musi być deterministyczne. Możesz użyć liczb generowanych pseudolosowo, ale musisz także ustalić początkowe źródło dla generatora.

W tym repozytorium znajdziesz plik o nazwie, permutations.txtktóry zawiera 505 permutacji, 5 o każdej długości od 50 do 150 włącznie, z wykorzystaniem indeksowania opartego na 0 (zwiększaj każdą liczbę w przypadku opartym na 1). Każda permutacja ma swoją własną linię, a jej liczby są oddzielone spacjami. Twój wynik to liczba bajtów f+ średnia złożoność zapytań na tych danych wejściowych . Najniższy wynik wygrywa.

Dodatkowe zasady

Preferowany jest kod z objaśnieniami, a standardowe luki są niedozwolone. W szczególności poszczególne bity są nierozróżnialne (więc nie można podać wektora Integerobiektów Pi porównać ich tożsamości), a funkcja Pzawsze zwraca nowy wektor zamiast zmiany kolejności danych wejściowych. Możesz dowolnie zmieniać nazwy fi Poraz kolejność, w jakiej przyjmują swoje argumenty.

Jeśli jesteś pierwszą osobą, która udzieli odpowiedzi w swoim języku programowania, gorąco zachęca się do włączenia uprzęży testowej, w tym implementacji funkcji, Pktóra również zlicza liczbę wywołań. Jako przykład, oto uprząż dla Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

W niektórych językach nie można napisać takiej uprzęży. Co najważniejsze, Haskell nie pozwala czystej funkcji Prejestrować liczby wywołań. Z tego powodu możesz ponownie wdrożyć swoje rozwiązanie w taki sposób, aby obliczało ono również złożoność zapytania i używało go w uprzęży.

J 44,0693 22,0693 = 37 15 + 7,06931

Jeśli nie możemy zadzwonić Pna i. n, to może przynajmniej rozmowy Pna każdy kawałek i. noddzielnie. Liczba wywołań Pwynosi >. 2 ^. n(⌈log ₂  n ⌉). Uważam, że jest to optymalne.

f=:P&.|:&.#:@i.

Oto implementacja funkcji, Pktóra wykorzystuje wektor permutacji pi zapisuje liczbę wywołań w Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Oto zestaw testowy, który otrzymuje permutację i zwraca liczbę wywołań p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

A oto jak możesz go użyć w pliku permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

Wyjaśnienie

Krótkie wyjaśnienie znajduje się już powyżej, ale tutaj jest bardziej szczegółowe. Po pierwsze, fze wstawionymi spacjami i jako funkcja jawna:

f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Czytać:

Niech f będzie P w transpozycji w reprezentacji zasady 2 pierwszych y liczb całkowitych.

gdzie y jest formalnym parametrem dla f. w J parametry do (funkcja) zwane x i r gdy czasownik dwójkowym (dwa parametry) i Y , jeśli jest monadycznego (posiada jeden parametr).

Zamiast powołując Psię na i. n(tj 0 1 2 ... (n - 1)), możemy powołać się Pna każdej pozycji bitowej liczby w i. n. Ponieważ wszystkie permutacje permutują w ten sam sposób, możemy ponownie złożyć permutowane bity na liczby, aby uzyskać wektor permutacji:

• i. y- liczby całkowite od 0do y - 1.

• #: y- yreprezentowane w podstawie 2. Jest to naturalnie rozszerzone na wektory liczb. Na przykład #: i. 16daje:

  0 0 0 0
  0 0 0 1
  0 0 1 0
  0 0 1 1
  0 1 0 0
  0 1 0 1
  0 1 1 0
  0 1 1 1
  1 0 0 0
  1 0 0 1
  1 0 1 0
  1 0 1 1
  1 1 0 0
  1 1 0 1
  1 1 1 0
  1 1 1 1
  

• #. y- yinterpretowane jako liczba podstawowa 2. W szczególności jest to odwrotność #:; y ~: #. #:zawsze trzyma.

• |: y- ytransponowane.

• u&.v y- uponiżej v, czyli vinv u v ytam gdzie vinvjest odwrotność do v. Zauważ, że |:jest to jego własna odwrotność.

• P y- funkcja Pzastosowana do każdego wektora yz definicji.

Pyth 32 + 7.06931 = 37.06931

Poniższy algorytm był całkowicie niezależny. Ale to mniej więcej to samo, co bardzo krótkie rozwiązanie FUZxxl J (o ile rozumiem).

Najpierw definicja funkcji P, która permutuje tablicę bitów zgodnie z nieznaną permutacją.

D%GHJHVJ XJ@HN@GN)RJ

A następnie kod, który określa permutację.

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

Definiuje funkcję g, która przyjmuje dwa argumenty. Możesz to nazwać g5[4 2 1 3 0. Oto demonstracja online . Nigdy nie korzystałem z tak wielu (5) zagnieżdżonych map.

A właściwie nie stworzyłem uprzęży testowej. Ta funkcja również nie Pliczy, ile razy ją nazywam. Sporo czasu poświęciłem na opracowywanie algorytmu. Ale jeśli przeczytasz moje wyjaśnienie, to całkiem oczywiste, że używa int(log2(n-1)) + 1wywołań ( = ceil(log2(n))). I sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069…

Wyjaśnienie:

Trudno mi było znaleźć ten algorytm. W ogóle nie było dla mnie jasne, jak osiągnąć log(n). Zacząłem więc eksperymentować z małymi n.

Pierwsza uwaga: Tablica bitów gromadzi te same informacje, co uzupełniająca tablica bitów. Dlatego wszystkie tablice bitów w moim rozwiązaniu mają co najwyżej n/2aktywny bit.

n = 3:

Ponieważ możemy używać macierzy bitów tylko z 1 aktywnym bitem, optymalne rozwiązanie zależy od dwóch wywołań. Np P([1, 0, 0])a P([0, 1, 0]). Wyniki mówią nam o pierwszej i drugiej liczbie permutacji, pośrednio otrzymujemy trzecią.

n = 4:

Tutaj jest trochę interesująco. Teraz możemy używać dwóch rodzajów macierzy bitów. Te z 1 aktywnym bitem i te z 2 aktywnymi bitami. Jeśli użyjemy tablicy bitów z jednym aktywnym bitem, zbieramy informacje tylko o jednej liczbie permutacji i cofamy się n = 3, powodując 1 + 2 = 3wywołania P. Interesujące jest to, że możemy zrobić to samo za pomocą tylko 2 wywołań, jeśli użyjemy tablic bitów z 2 aktywnymi bitami. Np P([1, 1, 0, 0])a P([1, 0, 1, 0]).

Powiedzmy, że otrzymujemy dane wyjściowe [1, 0, 0, 1]i [0, 0, 1, 1]. Widzimy, że bit nr 4 jest aktywny w obu tablicach wyjściowych. Jedynym bitem, który był aktywny w obu tablicach wejściowych, był bit nr 1, więc wyraźnie zaczyna się permutacja 4. Teraz łatwo zauważyć, że bit 2 został przeniesiony na bit 1 (pierwsze wyjście), a bit 3 został przeniesiony na bit 3 (drugie wyjście). Dlatego permutacja musi być [4, 1, 3, 2].

n = 7:

Teraz coś większego. PNatychmiast pokażę połączenia . Są to te, które wymyśliłem po krótkim zastanowieniu i eksperymentowaniu. (Zauważ, że to nie są te, których używam w kodzie).

P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

Jeśli w pierwszych dwóch tablicach wyjściowych (a nie w trzecim) bit 2 jest aktywny, wiemy, że permutacja przenosi bit 1 na bit 2, ponieważ bit pierwszy jest jedynym bitem, który jest aktywny w pierwszych dwóch tablicach wejściowych.

Ważne jest to, że (interpretując dane wejściowe jako macierz) każda kolumna jest unikalna. Przypomniało mi się to o kodach Hamminga , w których dokonano tego samego. Po prostu przyjmują liczby od 1 do 7 i wykorzystują swoją reprezentację bitową jako kolumny. Użyję liczb od 0 do 6. Teraz ładną część możemy ponownie interpretować dane wyjściowe (ponownie kolumny) jako liczby. Mówią nam o wyniku zastosowanej permutacji [0, 1, 2, 3, 4, 5, 6].

   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

Musimy tylko prześledzić liczby. Bit 0 skończył się na bicie 5, bit 1 skończył się na bicie 0, bit 2 skończył się na bicie 6, ... Więc permutacja była [5, 0, 6, 1, 3, 4, 2].

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation. 
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with 
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer 
                                                   # than others are shortened
           m%dH                    map each row (former column) d of 
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:                         
    i    2                           the decimal number of the 
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.  
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

I kod funkcji permutacji:

D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]: 
         XJ@HN@GN            J[H[N]] = G[N]           
                  RJ      return J

Mathematica, 63 + 100 = 163

Używam permutacji opartych na jednym, ponieważ tak działa indeksowanie w Mathematica.

Najpierw uprząż testowa. To jest funkcja zapytania p(nazwy zdefiniowane przez użytkownika nie powinny być dużymi literami w Mathematica):

p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

I przygotowanie danych wejściowych wraz z pętlą testową:

permutations = 
  ToExpression@StringSplit@# + 1 & /@ 
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result, 
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

I na koniec, moje aktualne zgłoszenie, które na razie wykorzystuje naiwny algorytm:

f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

Lub z wcięciem:

f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &