Rozważ permutację liczb całkowitych 1
... n
, takich jak ta dla n = 6
:
[5,2,4,3,6,1]
Jeśli zobaczysz permutację jako odwzorowanie od [1,2,3,4,5,6]
do [5,2,4,3,6,1]
, permutację można rozłożyć na rozłączne cykle . Cykl jest podzbiorem elementów odwzorowujących się względem siebie. Na przykład 1
zostanie zamapowany na 5
, który zostanie zmapowany 6
, na który zostanie odwzorowany z powrotem 1
. Tak więc jest jeden cykl [1,5,6]
. Pozostałe cykle to [2]
i [3,4]
. Zatem liczba cykli dla tej permutacji wynosi 3
.
Zasadniczo cykle permutacji są unikalne (do kolejności), a liczba cykli permutacji wielkości n
jest różna od 1
do n
.
Wyzwanie
Biorąc pod uwagę niepustą permutację, wypisz jej liczbę cykli.
Wejście jest tablica utworzona przez n
liczby całkowite 1
, 2
, ..., n
, gdzie n > 0
. Każda liczba całkowita występuje dokładnie raz. Kolejność, w jakiej się pojawiają, określa permutację, jak w powyższym przykładzie.
Zamiast tablicy możesz użyć listy, łańcucha z separatorem między liczbami, osobnego wejścia dla każdej liczby lub wszystkiego, co jest rozsądne.
Aby uzyskać permutację rozmiaru n
, zamiast 1-liczbowego zestawu liczb całkowitych 1
... n
możesz konsekwentnie używać zestawu 0-liczbowego 0
, ..., n-1
. Jeśli tak, proszę wskazać to w odpowiedzi.
Kod powinien działać n
nawet 20
w rozsądnym czasie, powiedzmy krócej niż minutę.
Kod golfa. Wszystkie wbudowane dozwolone.
Przypadki testowe
Zakłada się, że dane wejściowe z tablicy 1.
[1] -> 1
[3,2,1] -> 2
[2,3,4,5,1] -> 1
[5,2,4,3,6,1] -> 3
[8,6,4,5,2,1,7,3] -> 2
[4,5,11,12,7,1,3,9,10,6,8,2] -> 1
[4,2,5,11,12,7,1,3,9,10,6,8] -> 5
[5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
[14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7
Związane z
To powiązane wyzwanie wymaga rzeczywistych cykli permutacji, a nie ich liczby. Wymaganie tylko liczby cykli może prowadzić do krótszych algorytmów, które omijają generowanie faktycznych cykli.
źródło
1
, ...,n
w tej kolejności. Czy możesz wyjaśnić, w jaki sposób mapowanie może być wkładem? Czy to struktura danych?dict
. Chcę mieć{1: 2, 2: 1}
jako dane wejściowe zamiast[2, 1]
.Odpowiedzi:
J, 4 bajty
Zakłada się, że permutacja jest oparta na 0. Używa wbudowanego,
C.
który podając listę reprezentującą bezpośrednią permutację, wyświetla listę cykli. Następnie#
składa@
na które zwraca liczbę cykli w tym wykazie.Wypróbuj tutaj.
źródło
JavaScript,
9998 bajtówTo rozwiązanie zakłada, że tablica i jej wartości są indeksowane od zera (np
[2, 1, 0]
.).Wyjaśnienie
źródło
Mathematica, 45 bajtów
Generuje wykres i zlicza połączone elementy.
źródło
Mathematica,
372827 bajtówDzięki @alephalpha za zapisanie 9 bajtów i @miles za 1 dodatkowy bajt.
źródło
PermutationCycles[#,Length]&
PermutationCycles
wziąć drugi argument, aby zmienić kierunek jego działania. Możesz także użyć notacji infix, aby zapisać kolejny bajt#~PermutationCycles~Length&
.#&
jest nieco krótszy niżIdentity
. ;)Python,
776967 bajtówźródło
(not p[i-1])
można to zrobić jako0**p[i-1]
Galaretka,
12109 bajtówZapisano 1 bajt dzięki @ Dennis .
Używa to permutacji opartych na 1. Działa poprzez wielokrotne stosowanie permutacji, aż osiągnie poprzednią permutację, zachowując jednocześnie poprzednie wartości. Śledząc zmiany, utworzy orbitę dla każdej wartości wzdłuż kolumn tej tabeli. Następnie, znajdując minimum lub maksimum każdej kolumny, można utworzyć etykietę dla tego cyklu. Następnie deduplikuj tę listę etykiet i uzyskaj jej długość, która będzie liczbą rozłącznych cykli.
Wypróbuj tutaj.
Wyjaśnienie
źródło
ị³$ÐĿ«/QL
powinno działać.Python, 64 bajty
Ten golfowy kod bywa idiomatyczny i czytelny. Wykorzystuje indeksowanie 0.
Każda wartość patrzy na to, na co wskazuje i na co wskazuje wskazana wartość, i wskazuje na mniejszą z nich. Po wystarczającej liczbie powtórzeń każdy element wskazuje na najmniejszy element swojego cyklu. Wskazana liczba odrębnych elementów to liczba cykli.
Wystarczy wykonać
n
iteracje. Ewentualnie możemy iterować, dopóki lista się nie zmieni. Ta strategia dała mi funkcję rekurencyjną o tej samej długości, 64 bajty:Zmniejszenie wynosiło 65 bajtów
Do
set(_)
konwersji można skrócić do{*_}
w Pythonie 3.5, oszczędność 2 bajty.źródło
Haskell, 111 bajtów
Wykorzystuje indeksowanie 0
źródło
1l!i|iIi!!1ll1|
Pyth, 9 bajtów
Wykorzystuje indeksy oparte na 0. Wypróbuj online .
Jak to działa
źródło
JavaScript (ES6), 49 bajtów
Używa indeksowania zerowego. Objaśnienie:
reduce
służy do wywołania funkcji wewnętrznejg
na każdym elemencie tablicy.c
jest liczbą cykli,e
jest elementem tablicy,i
jest indeksem tablicy. Jeśli element jest mniejszy niż indeks, to jest to potencjalny cykl - element służy do indeksowania tablicy, aby rekurencyjnie znaleźć następny element w cyklu. Jeśli zaczynamy lub kończymy na oryginalnym indeksie, to jest to nowy cykl i zwiększamy liczbę cykli. Jeśli w którymkolwiek momencie znajdziemy wartość większą niż indeks, policzymy ten cykl później.źródło
[2,1,0,3,4,5]
, zawiesił się z komunikatem „Przekroczono maksymalny rozmiar stosu wywołań”.C, 90 bajtów
Wywołanie
f()
ze zmiennąint
tablicą, indeksowanie 1. Drugi parametr to rozmiar tablicy. Funkcja zwraca liczbę cykli.Wypróbuj na ideone .
Algorytm:
źródło
GAP , 30 bajtów
Bezpośrednio drugi argument, który
Cycles
podaje zestaw, na którym permutacja powinna działać:źródło