Wprowadzenie
Załóżmy, że masz losową permutację n
obiektó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 n
różnych obiektów, możesz natychmiast wywnioskować jej tożsamość. Możesz jednak zastosować permutację tylko do n
wektorów binarnych o długości , co oznacza, że będziesz musiał ją zastosować kilka razy, aby ją rozpoznać. Oczywiście, zastosowanie go do n
wektorów za pomocą tylko jednego 1
dział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ą n
oraz permutację p
pierwszych n
liczb całkowitych, przy użyciu indeksowania 0 lub 1. Jego wynikiem jest permutacja p
. Nie masz jednak p
bezpośredniego dostępu do permutacji . Jedyne, co możesz z tym zrobić, to zastosować go do dowolnego wektora n
bitów. W tym celu należy użyć funkcji pomocniczej, P
która przyjmuje permutację p
i wektor bitów v
i 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 3
i -4
, i 'a'
i 'b'
, i nie trzeba ich naprawiać, więc możesz dzwonić P
zarówno z tym samym, jak [-4,3,3,-4]
i [2,2,2,1]
tym samym f
. Definicja P
nie 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.txt
któ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 Integer
obiektów P
i porównać ich tożsamości), a funkcja P
zawsze zwraca nowy wektor zamiast zmiany kolejności danych wejściowych. Możesz dowolnie zmieniać nazwy f
i P
oraz 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, P
któ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 P
rejestrować 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.
abaaabababaa
i-4 3 3 3 -4 3
byłby wektorem bitów.Odpowiedzi:
J
44,069322,0693 =3715 + 7,06931Jeśli nie możemy zadzwonić
P
nai. n
, to może przynajmniej rozmowyP
na każdy kawałeki. n
oddzielnie. Liczba wywołańP
wynosi>. 2 ^. n
(⌈log 2 n ⌉). Uważam, że jest to optymalne.Oto implementacja funkcji,
P
która wykorzystuje wektor permutacjip
i zapisuje liczbę wywołań wPinv
.Oto zestaw testowy, który otrzymuje permutację i zwraca liczbę wywołań
p
:A oto jak możesz go użyć w pliku
permutations.txt
:Wyjaśnienie
Krótkie wyjaśnienie znajduje się już powyżej, ale tutaj jest bardziej szczegółowe. Po pierwsze,
f
ze wstawionymi spacjami i jako funkcja jawna:Czytać:
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
P
się nai. n
(tj0 1 2 ... (n - 1)
), możemy powołać sięP
na każdej pozycji bitowej liczby wi. 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 od0
doy - 1
.#: y
-y
reprezentowane w podstawie 2. Jest to naturalnie rozszerzone na wektory liczb. Na przykład#: i. 16
daje:#. y
-y
interpretowane jako liczba podstawowa 2. W szczególności jest to odwrotność#:
;y ~: #. #:
zawsze trzyma.|: y
-y
transponowane.u&.v y
-u
poniżejv
, czylivinv u v y
tam gdzievinv
jest odwrotność dov
. Zauważ, że|:
jest to jego własna odwrotność.P y
- funkcjaP
zastosowana do każdego wektoray
z definicji.źródło
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ą.A następnie kod, który określa permutację.
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
P
liczy, 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żywaint(log2(n-1)) + 1
wywołań (= ceil(log2(n))
). Isum(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łymin
.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/2
aktywny 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])
aP([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ąc1 + 2 = 3
wywołaniaP
. 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. NpP([1, 1, 0, 0])
aP([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ę permutacja4
. 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.
P
Natychmiast 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).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]
.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]
.I kod funkcji permutacji:
źródło
*sltQ]0
sięm0sltQ
, można mieć 6 zagnieżdżone mapy na tej samej długości.f
chociaż dozwolone są inne nazwy. Zadanie wlicza się do twojego wyniku.g
zamiast odczytu ze STDIN.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):I przygotowanie danych wejściowych wraz z pętlą testową:
I na koniec, moje aktualne zgłoszenie, które na razie wykorzystuje naiwny algorytm:
Lub z wcięciem:
źródło