W matematyce permutacja σ rzędu n jest funkcją podwójną od liczb całkowitych 1 ... n do siebie. Ta lista:
2 1 4 3
reprezentuje permutację σ tak, że σ (1) = 2, σ (2) = 1, σ (3) = 4, i σ (4) = 3.
Pierwiastek kwadratowy permutacji σ jest permutacją, która zastosowana do siebie daje σ . Na przykład 2 1 4 3
ma pierwiastek kwadratowy τ = 3 4 2 1
.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
ponieważ τ ( τ (k)) = σ (k) dla wszystkich 1≤k≤n.
Wkład
Lista liczb całkowitych n > 0, wszystkie od 1 do n włącznie, reprezentujące permutację. Permutacja zawsze będzie miała pierwiastek kwadratowy.
Zamiast tego możesz użyć listy 0 ... n-1, o ile dane wejściowe i wyjściowe są spójne.
Wydajność
Pierwiastek kwadratowy permutacji, również jako tablica.
Ograniczenia
Twój algorytm musi działać w czasie wielomianowym w n . Oznacza to, że nie możesz po prostu przejść przez wszystkie n ! permutacje rzędu n .
Wszelkie wbudowane są dozwolone.
Przypadki testowe:
Zauważ, że wiele wejść ma wiele możliwych wyników.
2 1 4 3
3 4 2 1
1
1
3 1 2
2 3 1
8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6
13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
źródło
Odpowiedzi:
Perl,
124122 bajtówObejmuje +3 za
-alp
Uruchom z permutacją opartą na 1 na STDIN:
rootperm.pl
:Złożoność wynosi O (n ^ 3)
źródło
Mathematica, 165
167bajtówFunkcja bez nazwy.
Częściowo nie golfowy:
źródło
Prolog - 69 znaków
Wyjaśnienie:
źródło