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.

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.

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
};

Mathematica, 45 bajtów

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

Generuje wykres i zlicza połączone elementy.

Mathematica, 37 28 27 bajtów

#~PermutationCycles~Length&

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

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))

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

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.

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

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

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.

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.

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))