Considere una permutación de los enteros 1, ..., ncomo este para n = 6:

[5,2,4,3,6,1]

Si ve la permutación como un mapeo de [1,2,3,4,5,6]a [5,2,4,3,6,1], la permutación puede descomponerse en ciclos disjuntos . Un ciclo es un subconjunto de elementos que se asignan entre sí. Por ejemplo, 1se asigna a 5, que se asigna a 6, que se vuelve a asignar 1. Entonces un ciclo es [1,5,6]. Los otros ciclos son [2]y [3,4]. Por lo tanto, el número de ciclos para esta permutación es 3.

En general, los ciclos de una permutación son únicos (hasta el orden), y el número de ciclos para una permutación de tamaño nvaría de 1a n.

El reto

Dada una permutación no vacía, genera su número de ciclos.

De entrada es una matriz formada por los nnúmeros enteros 1, 2, ..., n, donde n > 0. Cada número entero ocurre exactamente una vez. El orden en que aparecen define la permutación, como en el ejemplo anterior.

En lugar de una matriz, puede usar una lista, una cadena con un separador entre los números, una entrada separada para cada número o cualquier cosa que sea razonable.

Para una permutación de tamaño n, en lugar del conjunto de enteros basado en 1 1, ..., npuede usar consistentemente el conjunto basado en 0 0, ..., n-1. Si es así, indíquelo en su respuesta.

El código debería funcionar nhasta 20en un tiempo razonable, digamos menos de un minuto.

Código de golf. Todas las construcciones permitidas.

Casos de prueba

Esto supone una entrada de matriz basada en 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

Relacionado

Este desafío relacionado pide los ciclos reales de la permutación, no el número de ellos. Requerir solo el número de ciclos puede conducir a algoritmos más cortos que eluden la generación de los ciclos reales.

J, 4 bytes

#@C.

Esto supone que la permutación está basada en 0. Utiliza el incorporado C.que proporciona una lista que representa una permutación directa y genera una lista de ciclos. Luego #compuesto @sobre eso devuelve el número de ciclos en esa lista.

Pruébalo aquí

JavaScript, 99 98 bytes

Esta solución asume que la matriz y sus valores están indexados a cero (p [2, 1, 0]. Ej .).

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}

Explicación

// 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 bytes

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

Genera un gráfico y cuenta sus componentes conectados.

Mathematica, 37 28 27 bytes

#~PermutationCycles~Length&

Gracias @alephalpha por guardar 9 bytes y @miles por 1 byte más.

Python, 77 69 67 bytes

f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))

Jalea, 12 10 9 bytes

ị³$ÐĿ«/QL

Guardado 1 byte gracias a @ Dennis .

Esto usa permutaciones basadas en 1. Funciona aplicando la permutación repetidamente hasta que alcanza una permutación previa mientras mantiene sus valores anteriores. Al realizar un seguimiento de los cambios, creará la órbita para cada valor a lo largo de las columnas de esa tabla. Luego, al encontrar el mínimo o el máximo de cada columna, se puede crear una etiqueta para ese ciclo. Luego deduplica esa lista de etiquetas y obtén su longitud, que será el número de ciclos disjuntos.

Pruébalo aquí

Explicación

ị³$ÐĿ«/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 bytes

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

Este código de golf resulta ser idiomático y legible. Utiliza indexación 0.

Cada valor mira a qué apunta y a qué apunta el valor señalado, y apunta al menor de los dos. Después de suficientes repeticiones, cada elemento apunta al elemento más pequeño de su ciclo. El número de elementos distintos señalados es entonces el número de ciclos.

Es suficiente hacer niteraciones. Alternativamente, podríamos iterar hasta que la lista ya no cambie. Esta estrategia me dio una función recursiva de la misma longitud, 64 bytes:

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

La reducción fue de 65 bytes

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

Las set(_)conversiones pueden acortarse {*_}en Python 3.5, ahorrando 2 bytes.

Haskell, 111 bytes

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)

Utiliza indexación basada en 0

Pyth, 9 bytes

l{mS.u@QN

Utiliza índices basados ​​en 0. Pruébalo en línea .

Cómo funciona

  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 bytes

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

Utiliza indexación basada en cero. Explicación: reducese utiliza para invocar la función interna gen cada elemento de la matriz. ces el recuento de ciclos, ees el elemento de la matriz, ies el índice de la matriz. Si el elemento es menor que el índice, entonces es un ciclo potencial: el elemento se usa para indexar en la matriz para encontrar el siguiente elemento en el ciclo de forma recursiva. Si comenzamos o terminamos con el índice original, entonces este es un nuevo ciclo e incrementamos la cuenta del ciclo. Si en algún momento encontramos un valor mayor que el índice, contaremos ese ciclo más adelante.

C, 90 bytes

Llamada f()con una intmatriz mutable , 1 indexación basada. El segundo parámetro es el tamaño de la matriz. La función devuelve el número de ciclos.

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

Pruébalo con ideone .

El algoritmo:

For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.

GAP , 30 bytes

Directamente, el segundo argumento Cyclesda el conjunto sobre el cual debe actuar la permutación:

l->Size(Cycles(PermList(l),l))