Número de ciclos de uma permutação

23

Considere uma permutação de números inteiros 1, ... n,, como esta para n = 6:

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

Se você visualizar a permutação como um mapeamento de [1,2,3,4,5,6]para [5,2,4,3,6,1], a permutação poderá ser descompactada em ciclos separados . Um ciclo é um subconjunto de elementos que são mapeados entre si. Por exemplo, 1é mapeado para 5, que é mapeado para 6, para o qual é mapeado novamente 1. Então, um ciclo é [1,5,6]. Os outros ciclos são [2]e [3,4]. Assim, o número de ciclos para esta permutação é 3.

Em geral, os ciclos de uma permutação são únicos (por ordem), e o número de ciclos para uma permutação de tamanho nvaria de 1a n.

O desafio

Dada uma permutação não vazia, produza seu número de ciclos.

A entrada é um conjunto formado pelos nnúmeros inteiros 1, 2, ..., n, onde n > 0. Cada número inteiro ocorre exatamente uma vez. A ordem em que eles aparecem define a permutação, como no exemplo acima.

Em vez de uma matriz, você pode usar uma lista, uma sequência com um separador entre os números, uma entrada separada para cada número ou qualquer coisa que seja razoável.

Para uma permutação de tamanho n, em vez do conjunto de números inteiros baseado em 1 1, ..., nvocê pode usar consistentemente o conjunto baseado em 0 0, ..., n-1. Nesse caso, indique-o na sua resposta.

O código deve funcionar por naté 20um tempo razoável, digamos menos de um minuto.

Código de golfe. Todos os builtins permitidos.

Casos de teste

Isso pressupõe entrada de matriz baseada em 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

Esse desafio relacionado pede os ciclos reais da permutação, não o número deles. Exigir apenas o número de ciclos pode levar a algoritmos mais curtos que evitam a geração dos ciclos reais.

Luis Mendo
fonte
Deixa pra lá a minha pergunta, é declarado que a entrada baseada na pergunta 0 é permitida.
orlp
@ orlp Isso foi rápido! Eu nem cheguei a ver sua pergunta
Luis Mendo
Podemos levar um mapeamento de índices para valores como entrada?
Cobre
1
@ Cobre Acho que sim, se o domínio do mapeamento é o conjunto 1, ..., nnessa ordem. Você pode esclarecer como um mapeamento pode ser uma entrada? É uma estrutura de dados?
Luis Mendo
@LuisMendo Sim, é uma estrutura de dados, como um Python dict. Eu quero ter {1: 2, 2: 1}como uma entrada em vez de [2, 1].
Cobre

Respostas:

12

J, 4 bytes

#@C.

Isso pressupõe que a permutação seja baseada em 0. Ele usa o built-in C.que, dada uma lista que representa uma permutação direta, gera uma lista de ciclos. Em seguida, #composto @em que retorna o número de ciclos nessa lista.

Experimente aqui.

milhas
fonte
1
Isso é batota! :)
orlp 1/08/16
1
Eu deveria ter banido builtins :-D
Luis Mendo
2
Builtins são amor. Construções são vida. Concordo que seria mais divertido com os builtins sendo banidos. Sinta-se à vontade para alterar a regra agora mesmo antes de responder demais.
milhas
@miles Nah, vou deixar como está. Bom trabalho!
Luis Mendo
7

JavaScript, 99 98 bytes

Esta solução assume que a matriz e seus valores são indexados a zero (por exemplo [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}

Explicação

// 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
fonte
3
Bem-vindo ao PPCG! Ótima primeira resposta! Essa também é uma das melhores, se não a melhor, primeira resposta que já vi em minha experiência! Mantenha o bom trabalho!
GamrCorps 02/08
Uau, muito obrigado! Na verdade, eu tive que procurar como fazer as lambdas em JavaScript. Ainda não estou familiarizado com o material do ES6.
precisa saber é o seguinte
6

Mathematica, 45 bytes

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

Ele gera um gráfico e conta seus componentes conectados.

alefalpha
fonte
6

Mathematica, 37 28 27 bytes

#~PermutationCycles~Length&

Obrigado @alephalpha por salvar 9 bytes e @miles por mais 1 byte.

Martin
fonte
3
PermutationCycles[#,Length]&
Alephalpha #
3
Oh, isso é legal. Eu não sabia que PermutationCyclespoderia usar um segundo argumento para alterar a cabeça de sua saída. Você também pode usar a notação infix para salvar outro byte #~PermutationCycles~Length&.
milhas
1
Também em relação à sua solução original, #&é um pouco menor que Identity. ;)
Martin Ender
6

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))
orlp
fonte
(not p[i-1])pode ser feito como0**p[i-1]
xnor
5

Geléia, 12 10 9 bytes

ị³$ÐĿ«/QL

Guardou 1 byte graças a @ Dennis .

Isso usa permutações baseadas em 1. Ele funciona aplicando a permutação repetidamente até atingir uma permutação anterior, mantendo também seus valores anteriores. Ao acompanhar as alterações, ele criará a órbita para cada valor ao longo das colunas dessa tabela. Em seguida, localizando o mínimo ou o máximo de cada coluna, um rótulo para esse ciclo pode ser criado. Em seguida, desduplique essa lista de rótulos e obtenha o comprimento, que será o número de ciclos disjuntos.

Experimente aqui.

Explicação

ị³$ÐĿ«/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
milhas
fonte
Abordagem muito agradável!
Luis Mendo
ị³$ÐĿ«/QLDeveria trabalhar.
Dennis
@ Dennis Wow, isso é um truque legal! Como cada ciclo é separado, pegar o máximo / min e usá-lo como um rótulo será suficiente para deduplicar + comprimento para o resultado.
milhas
5

Python, 64 bytes

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

Esse código golfado é idiomático e legível. Usa indexação 0.

Cada valor examina o que aponta e o que o valor apontado aponta e aponta para o menor dos dois. Após repetições suficientes, cada elemento aponta para o menor elemento do seu ciclo. O número de elementos distintos apontados é o número de ciclos.

Basta fazer niterações. Como alternativa, poderíamos iterar até que a lista não seja mais alterada. Essa estratégia me deu uma função recursiva do mesmo comprimento, 64 bytes:

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

A redução foi de 65 bytes

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

As set(_)conversões podem ser reduzidas para {*_}Python 3.5, economizando 2 bytes.

xnor
fonte
4

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)

Usa indexação baseada em 0

Homem do programa
fonte
4
Droga, é melhor ter uma fonte boa programação :)1l!i|iIi!!1ll1|
orlp
@orlp e são 111 bytes! : O
grooveplex 2/16
4

Pitão, 9 bytes

l{mS.u@QN

Usa índices baseados em 0. Experimente online .

Como 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
Anders Kaseorg
fonte
3

JavaScript (ES6), 49 bytes

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

Usa indexação baseada em zero. Explicação:reduce é usado para chamar a função interna gem cada elemento da matriz. cé a contagem de ciclos, eé o elemento da matriz, ié o índice da matriz. Se o elemento for menor que o índice, é um ciclo em potencial - o elemento é usado para indexar na matriz para encontrar recursivamente o próximo elemento no ciclo. Se começamos ou terminamos com o índice original, esse é um novo ciclo e incrementamos a contagem de ciclos. Se a qualquer momento encontrarmos um valor maior que o índice, contaremos esse ciclo posteriormente.

Neil
fonte
Quando executei seu código na matriz [2,1,0,3,4,5], ele falhou com esta mensagem "Tamanho máximo da pilha de chamadas excedido".
Kamoroso94
1
@ kamoroso94 Desculpe por isso, um erro de digitação apareceu. Deve ser corrigido agora.
Neil
2

C, 90 bytes

Chame f()com uma intmatriz mutável , indexação baseada em 1. O segundo parâmetro é o tamanho da matriz. A função retorna o 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;}

Experimente em ideone .

O algoritmo:

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

GAP , 30 bytes

Simplesmente, o segundo argumento para Cyclesfornece o conjunto no qual a permutação deve atuar:

l->Size(Cycles(PermList(l),l))
Peneiradores cristãos
fonte