Liczba cykli permutacji

23

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 1zostanie 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 njest różna od 1do n.

Wyzwanie

Biorąc pod uwagę niepustą permutację, wypisz jej liczbę cykli.

Wejście jest tablica utworzona przez nliczby 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... nmożesz konsekwentnie używać zestawu 0-liczbowego 0, ..., n-1. Jeśli tak, proszę wskazać to w odpowiedzi.

Kod powinien działać nnawet 20w 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.

Luis Mendo
źródło
Nieważne, czy moje pytanie jest określone w pytaniu, dozwolone są dane wejściowe oparte na 0.
orlp
@orlp To było szybkie! Nawet nie zobaczyłem twojego pytania
Luis Mendo
Czy możemy wprowadzić mapowanie indeksów do wartości jako danych wejściowych?
Copper
1
@Copper Myślę, że tak, jeśli domeną mapowania jest zbiór 1, ..., nw tej kolejności. Czy możesz wyjaśnić, w jaki sposób mapowanie może być wkładem? Czy to struktura danych?
Luis Mendo,
@LuisMendo Tak, to struktura danych, taka jak Python dict. Chcę mieć {1: 2, 2: 1}jako dane wejściowe zamiast [2, 1].
Copper

Odpowiedzi:

12

J, 4 bajty

#@C.

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.

mile
źródło
1
To jest oszukiwanie! :)
orlp
1
Powinienem był zbanować wbudowane :-D
Luis Mendo
2
Wbudowane są miłością. Wbudowane są życie. Zgadzam się, że byłoby fajniej, gdyby wbudowane zostały zakazane. Możesz zmienić regułę teraz, zanim pojawi się zbyt wiele odpowiedzi.
mile
@miles Nie, zostawię to tak, jak jest. Dobra robota!
Luis Mendo,
7

JavaScript, 99 98 bajtów

To rozwiązanie zakłada, że ​​tablica i jej wartości są indeksowane od zera (np [2, 1, 0].).

f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

Wyjaśnienie

// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};
kamoroso94
źródło
3
Witamy w PPCG! Ładna pierwsza odpowiedź! To także jedna z najlepszych, jeśli nie najlepsza, pierwsza odpowiedź, jaką widziałem w swoim doświadczeniu! Tak trzymaj!
GamrCorps
Wow, bardzo dziękuję! Właściwie musiałem sprawdzić, jak zrobić lambda w JavaScript. Nie znam się jeszcze na ES6.
kamoroso94
6

Mathematica, 45 bajtów

Length@ConnectedComponents@Thread[Sort@#->#]&

Generuje wykres i zlicza połączone elementy.

alephalpha
źródło
6

Mathematica, 37 28 27 bajtów

#~PermutationCycles~Length&

Dzięki @alephalpha za zapisanie 9 bajtów i @miles za 1 dodatkowy bajt.

jaskółka oknówka
źródło
3
PermutationCycles[#,Length]&
alephalpha
3
Och, to miłe. Nie wiedziałem, że mogę PermutationCycleswziąć drugi argument, aby zmienić kierunek jego działania. Możesz także użyć notacji infix, aby zapisać kolejny bajt #~PermutationCycles~Length&.
mile
1
Także jeśli chodzi o twoje oryginalne rozwiązanie, #&jest nieco krótszy niż Identity. ;)
Martin Ender
6

Python, 77 69 67 bajtów

f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))
orlp
źródło
(not p[i-1])można to zrobić jako0**p[i-1]
xnor
5

Galaretka, 12 10 9 bajtów

ị³$ÐĿ«/QL

Zapisano 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

ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return
mile
źródło
Bardzo fajne podejście!
Luis Mendo,
ị³$ÐĿ«/QLpowinno działać.
Dennis
@Dennis Wow, to fajna sztuczka! Ponieważ każdy cykl jest rozłączny, przyjęcie albo maks / min i użycie go jako etykiety wystarczy, aby deduplikować + długość wyniku.
mile
5

Python, 64 bajty

l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

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ć niteracje. 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:

f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

Zmniejszenie wynosiło 65 bajtów

lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

Do set(_)konwersji można skrócić do {*_}w Pythonie 3.5, oszczędność 2 bajty.

xnor
źródło
4

Haskell, 111 bajtów

l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

Wykorzystuje indeksowanie 0

Program człowiek
źródło
4
Cholera, lepiej mieć dobrą czcionkę programistyczną :)1l!i|iIi!!1ll1|
orlp
@orlp i ma 111 bajtów! : O
grooveplex
4

Pyth, 9 bajtów

l{mS.u@QN

Wykorzystuje indeksy oparte na 0. Wypróbuj online .

Jak to działa

  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length
Anders Kaseorg
źródło
3

JavaScript (ES6), 49 bajtów

a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

Używa indeksowania zerowego. Objaśnienie: reducesłuży do wywołania funkcji wewnętrznej gna każdym elemencie tablicy. cjest liczbą cykli, ejest elementem tablicy, ijest 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.

Neil
źródło
Kiedy uruchomiłem twój kod na tablicy [2,1,0,3,4,5], zawiesił się z komunikatem „Przekroczono maksymalny rozmiar stosu wywołań”.
kamoroso94,
1
@ kamoroso94 Przepraszamy za to, że wkradła się literówka. Teraz należy to naprawić.
Neil
2

C, 90 bajtów

Wywołanie f()ze zmienną inttablicą, indeksowanie 1. Drugi parametr to rozmiar tablicy. Funkcja zwraca liczbę cykli.

i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

Wypróbuj na ideone .

Algorytm:

For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.
owacoder
źródło
2

GAP , 30 bajtów

Bezpośrednio drugi argument, który Cyclespodaje zestaw, na którym permutacja powinna działać:

l->Size(Cycles(PermList(l),l))
Christian Sievers
źródło