Localizando todos os ciclos

Eu tenho um conjunto finito , uma função f : S → S , e uma ordem total < em S . Eu quero encontrar o número de ciclos distintos em S .$S$$f:S\to S$$<$$S$$S$

Para um dado elemento , posso usar o algoritmo de Floyd (ou de Brent, etc.) para encontrar a duração do ciclo para o qual as aplicações repetidas de f enviam s para; com um pouco mais de esforço, consigo identificar esse ciclo (por exemplo, por seu elemento < -minimal). Um método ruim para resolver o problema seria repetir cada elemento, classificar os elementos mínimos resultantes descartando duplicatas e retornar a contagem. Mas isso envolve muitas passagens sobre os mesmos elementos e grandes requisitos de espaço.$s\in S$$f$$s$$<$

Quais métodos têm melhor desempenho de tempo e espaço? Eu nem tenho certeza de qual é a melhor maneira de medir o espaço necessário, se é a função identidade, então qualquer método que armazena todos os ciclos usará Ω ( n ) espaço.$f$$\Omega(n)$

Se tudo o que você deseja fazer é contar o número de ciclos, faça isso com 2 | S | bits (mais mudança) no valor de espaço. Parece improvável que você seja capaz de fazer muito melhor, a menos que S ou f possuam algumas propriedades particularmente convenientes.

Comece com uma matriz A armazenando números inteiros {0,1,2} - um por elemento de S - inicializado em zero; vamos indicar estes como (unexplored), (partially explored), e (fully explored). Inicialize um contador de ciclo para zero. Para cada elemento s  ∈  S em ordem, faça o seguinte:

1. Se A [ s ] =  (fully explored), pule para a etapa 6.
2. Defina A [ s ] ←  (partially explored)e defina um iterador j  ←  f (s) .
3. Enquanto A [ j ] =  (unexplored), defina A [ j ] ←  (partially explored)e defina j  ←  f (j) .
4. Se A [ j ] =  (partially explored), fechamos um novo ciclo; incremente c por 1. (Se você deseja manter um registro de algum representante desse ciclo, o valor atual de j será uma escolha arbitrária; é claro, esse não será necessariamente o elemento mínimo no ciclo sob sua preferência. order <.) Caso contrário, temos A [ j ] =  (fully explored), o que significa que descobrimos uma órbita pré-explorada que termina em um ciclo já contado; não incremente c .
5. Para indicar que a órbita iniciada em s foi totalmente explorada, defina j  ←  s .
   Enquanto A [ j ] =  (partially explored), defina A [ j ] ←  (fully explored)e defina j  ←  f (j) .
6. Avance para o próximo elemento s  ∈  S .

Assim, cada ciclo entre as órbitas induzidas por f será contado uma vez; e quaisquer elementos que você registrar como representantes serão elementos de ciclos distintos. Os requisitos de memória são 2 | S | para a matriz A, O (log | S |) para a contagem de ciclos e outras probabilidades e fins.

Cada elemento s  ∈  S será visitado pelo menos duas vezes: uma vez quando o valor de A [ s ] for alterado de (unexplored)para (partially explored)e uma vez para a alteração de (fully explored). O número total de vezes que qualquer nó é revisitado depois de ter sido (fully explored)delimitado acima pelo número de tentativas de encontrar novos ciclos que não conseguem fazê-lo, o que é no máximo | S | - decorrente da principal iteração loop por todos os elementos de S . Assim, podemos esperar que esse processo envolva no máximo 3 | S | travessias de nó, contando todas as vezes que os nós são visitados ou revisitados.

Se você deseja acompanhar os elementos representativos dos ciclos e realmente deseja que eles sejam os elementos mínimos, vincule o número de visitas ao nó a 4 | S |, se você adicionar uma "volta ao redor do ciclo" na etapa 4 para encontrar um representante menor do que aquele em que você fecha o loop. (Se as órbitas sob f consistissem apenas em ciclos, esse trabalho extra poderia ser evitado, mas isso não se aplica a f arbitrário ).

Se você tiver muito poucos ciclos, aqui está um algoritmo que usará menos espaço, mas levará muito mais tempo para terminar.

[Editar.] Minha análise anterior em tempo de execução perdeu o custo crucial de determinar se os nós que visitamos estão entre os amostrados anteriormente; essa resposta foi revisada para corrigir isso.

Voltamos a percorrer todos os elementos de S . À medida que exploramos as órbitas dos elementos s  ∈  S , coletamos amostras dos nós que visitamos, para poder verificar se os encontramos novamente. Também mantemos uma lista de amostras de 'componentes' - uniões de órbitas que terminam em um ciclo comum (e que são, portanto, equivalentes a ciclos) - que foram visitadas anteriormente.

Inicialize uma lista vazia de componentes complist,. Cada componente é representado por uma coleção de amostras desse componente; também mantemos uma árvore de pesquisa samplesque armazena todos os elementos que foram selecionados como amostras para um componente ou outro. Seja G uma sequência de números inteiros até n , para os quais a associação é eficientemente determinável calculando algum predicado booleano; por exemplo, poderes de 2 ou perfeitas p ^th poderes para algum inteiro p . Para cada s  ∈  S , faça o seguinte:

1. Se s estiver dentro samples, pule para a etapa 5.
2. Inicialize uma lista vazia cursample, um iterador j  ← f ( s ) e um contador t  ← 1.
3. Enquanto j não estiver em samples:
   - Se t  ∈  G , insira j em ambos cursamplee samples.
   - Incremente te ajuste j  ←  f (j) .
4. Verifique se j está em cursample. Caso contrário, encontramos um componente explorado anteriormente: verificamos a qual componente j pertence e inserimos todos os elementos de cursampleno elemento apropriado complistpara aumentá-lo. Caso contrário, reencontramos um elemento da órbita atual, o que significa que percorremos um ciclo pelo menos uma vez sem encontrar representantes de ciclos descobertos anteriormente: inserimos cursamplecomo uma coleção de amostras de um componente recém-encontrado complist.
5. Avance para o próximo elemento s  ∈  S .

Para n  = | S |, seja X (n) uma função crescente monótona que descreve o número esperado de ciclos ( por exemplo,  X (n) =  n ^1/3 ) e deixe Y (n) = y (n)  log ( n ) ∈ ∈ ( X (n)  log ( n )) é uma função crescente monótona que determina um alvo para o uso da memória ( por exemplo,  y (n) =  n ^1/2 ). Exigimos y (n)  ∈ Ω ( X (n) ) porque será necessário pelo menos X (n)  log ( n ) para armazenar uma amostra de cada componente.

• Quanto mais elementos de uma órbita amostramos, maior a probabilidade de selecionarmos rapidamente uma amostra no ciclo no final de uma órbita e, assim, detectar rapidamente esse ciclo. Do ponto de vista assintótico, faz sentido obter tantas amostras quanto nossos limites de memória permitirem: é melhor definirmos G para ter um esperado y (n) elementos que são menores que n .
  - Se se espera que o comprimento máximo de uma órbita em S seja L , podemos permitir que G sejam os múltiplos inteiros de L  /  y (n) .
  - Se não houver comprimento esperado, podemos simplesmente amostrar uma vez a cada n  / a  (n)elementos; em qualquer caso, esse é um limite superior nos intervalos entre as amostras.

• Se, ao procurar um novo componente, começarmos a atravessar elementos de S que já visitamos anteriormente (seja de um novo componente descoberto ou de um antigo cujo ciclo terminal já foi encontrado), será necessário no máximo n  / a  ( n) iterações para encontrar um elemento previamente amostrado; esse é um limite superior do número de vezes que, para cada tentativa de encontrar um novo componente, atravessamos nós redundantes. Como fazemos n tais tentativas, visitaremos redundantemente elementos de S no máximo n ²  /  y (n) vezes no total.

• O trabalho necessário para testar a associação samplesé O ( y (n)  log  y (n) ), que repetimos a cada visita: o custo cumulativo dessa verificação é O ( n ²  log  y (n) ). Há também o custo de adicionar as amostras às suas respectivas coleções, que cumulativamente é O ( y (n)  log  y (n) ). Finalmente, cada vez que encontramos um componente descoberto anteriormente, precisamos gastar até X (n)  log *  y (n) tempo para determinar qual componente redescobrimos; como isso pode acontecer até n vezes, o trabalho cumulativo envolvido é limitado por n X (n)  log  y (n) .

Assim, o trabalho cumulativo realizado para verificar se os nós que visitamos estão entre as amostras domina o tempo de execução: isso custa O ( n ²  log  y (n) ). Então devemos tornar y (n) o menor possível, ou seja, O ( X (n) ).

Assim, pode-se enumerar o número de ciclos (que é o mesmo que o número de componentes que terminam nesses ciclos) no espaço O ( X (n)  log ( n )), ocupando O ( n ²  log  X (n) ) tempo para fazê-lo, onde X (n) é o número esperado de ciclos.

$s$$s$$f(s)$