Trouver tous les cycles

Je un ensemble fini , une fonction , et un ordre total sur . Je veux trouver le nombre de cycles distincts dans .f : S → S < S $S$$f:S\to S$$<$$S$$S$

Pour un élément donné je peux utiliser l'algorithme de Floyd (ou Brent, etc.) pour trouver la longueur du cycle auquel les applications répétées de envoient ; avec un peu plus d'effort, je peux identifier ce cycle (par exemple par son élément -minimal). Une mauvaise méthode pour résoudre le problème serait de répéter chaque élément, de trier les éléments minimaux résultants en éliminant les doublons et de renvoyer le décompte. Mais cela implique potentiellement de nombreux passages sur les mêmes éléments et de grands besoins d'espace.f s $s\in S$$f$$s$$<$

Quelles méthodes offrent de meilleures performances spatio-temporelles? Je ne sais même pas quelle est la meilleure façon de mesurer l'espace nécessaire - si est la fonction d'identité, alors toute méthode qui stocke tous les cycles utilisera l' espace .Ω ( n $f$$\Omega(n)$

Si tout ce que vous voulez faire est de compter le nombre de cycles, vous pouvez le faire avec 2 | S | bits (plus le changement) d'une valeur d'espace. Il semble peu probable que vous puissiez faire beaucoup mieux à moins que S ou f aient des propriétés particulièrement pratiques.

Commencez avec un tableau A stockant des entiers {0,1,2} - un par élément de S - initialisé à zéro; nous indiquerons ces derniers comme (unexplored), (partially explored)et (fully explored). Initialisez un compteur de cycles à zéro. Pour chaque élément s  ∈  S dans l'ordre, procédez comme suit:

1. Si A [ s ] =  (fully explored), passez à l'étape 6.
2. Définissez A [ s ] ←  (partially explored)et définissez un itérateur j  ←  f (s) .
3. Alors que A [ j ] =  (unexplored), réglez A [ j ] ←  (partially explored)et réglez j  ←  f (j) .
4. Si A [ j ] =  (partially explored), nous avons fermé un nouveau cycle; incrémentez c de 1. (Si vous voulez garder une trace d'un représentant de ce cycle, la valeur actuelle de j fera un choix arbitraire; bien sûr, ce ne sera pas nécessairement l'élément minimal du cycle sous votre préférence order <.) Sinon, nous avons A [ j ] =  (fully explored), ce qui signifie que nous avons découvert une orbite pré-explorée qui se termine par un cycle déjà compté; ne pas incrémenter c .
5. Pour indiquer que l'orbite commençant à s a maintenant été entièrement explorée, définissez j  ←  s .
   Alors que A [ j ] =  (partially explored), réglez A [ j ] ←  (fully explored)et réglez j  ←  f (j) .
6. Passez à l'élément suivant de  ∈  S .

Ainsi, chaque cycle parmi les orbites induites par f sera compté une fois; et tous les éléments que vous enregistrez en tant que représentants seront des éléments de cycles distincts. La mémoire requise est de 2 | S | pour le tableau A, O (log | S |) pour le nombre de cycles, et autres cotes et fins.

Chaque élément s  ∈  S sera visité au moins deux fois: une fois lorsque la valeur de A [ s ] passe de (unexplored)à (partially explored), et une fois pour la changer en (fully explored). Le nombre total de fois où un nœud est revu après avoir été (fully explored)limité est limité par le nombre de tentatives pour trouver de nouveaux cycles qui échouent, ce qui est au plus | S | - résultant de l'itération de la boucle principale à travers tous les éléments de S . On peut donc s'attendre à ce que ce processus implique au maximum 3 | S | traversées de nœuds, en comptant toutes les fois que les nœuds sont visités ou revisités.

Si vous voulez garder une trace des éléments représentatifs des cycles et que vous souhaitez vraiment qu'ils soient les éléments minimaux, vous pouvez limiter le nombre de visites de nœuds à 4 | S |, si vous ajoutez un "tour autour du cycle" supplémentaire à l'étape 4 pour trouver un représentant plus petit que celui où vous fermez la boucle. (Si les orbites sous f ne consistaient qu'en cycles, ce travail supplémentaire pourrait être évité, mais ce n'est pas le cas de f arbitraire .)

Si vous avez très peu de cycles, voici un algorithme qui utilisera moins d'espace, mais prendra beaucoup plus de temps pour se terminer.

[Edit.] Mon analyse précédente de l'exécution a manqué le coût crucial de déterminer si les nœuds que nous visitons sont parmi ceux précédemment échantillonnés; cette réponse a été quelque peu révisée pour corriger cela.

Nous avons de nouveau itérer à travers tous les éléments de S . En explorant les orbites des éléments s  ∈  S , nous échantillonnons à partir des nœuds que nous avons visités, afin de pouvoir vérifier si nous les rencontrons à nouveau. Nous tenons également à jour une liste d'échantillons de «composants» - unions d'orbites qui se terminent par un cycle commun (et qui sont donc équivalents à des cycles) - qui ont déjà été visités.

Initialiser une liste vide de composants, complist. Chaque composant est représenté par une collection d'échantillons de ce composant; nous maintenons également un arbre de recherche samplesqui stocke tous les éléments qui ont été sélectionnés comme échantillons pour certains composants ou autres. Soit G une séquence d'entiers jusqu'à n , pour laquelle l'appartenance peut être déterminée efficacement en calculant un prédicat booléen; par exemple, des puissances de 2 ou parfaits p ^e pouvoirs pour un entier p . Pour chaque s  ∈  S , procédez comme suit:

1. Si s est samplesactivé, passez à l'étape 5.
2. Initialiser une liste vide cursample, un itérateur j  ← f ( s ) et un compteur t  ← 1.
3. Si j n'est pas samples:
   - Si t  ∈  G , insérez j dans les deux cursampleet samples.
   - Incrémenter t et régler j  ←  f (j) .
4. Vérifiez si j est dedanscursample . Sinon, nous avons rencontré un composant précédemment exploré: nous vérifions à quel composant j appartient et insérons tous les éléments de cursampledans l'élément approprié de complistpour l'augmenter. Sinon, nous avons retrouvé un élément de l'orbite actuelle, ce qui signifie que nous avons traversé un cycle au moins une fois sans rencontrer de représentants de cycles précédemment découverts: nous insérons cursample, en tant que collection d'échantillons d'un composant nouvellement trouvé, dans complist.
5. Passez à l'élément suivant de  ∈  S .

Pour n  = | S |, soit X (n) une fonction croissante monotone décrivant le nombre de cycles attendu ( par exemple  X (n) =  n ^1/3 ), et soit Y (n) = y (n)  log ( n ) ∈ Ω ( X (n)  log ( n )) est une fonction croissante monotone détermination d' une cible pour l' utilisation de la mémoire ( par exemple ,  y (n) =  n ^1/2 ). Nous avons besoin de y (n)  ∈ Ω ( X (n) ) car il faudra au moins X  ( n ) espace log ( n ) pour stocker un échantillon de chaque composant.

• Plus nous échantillonnons d'éléments d'une orbite, plus nous sommes susceptibles de sélectionner rapidement un échantillon dans le cycle à la fin d'une orbite, et ainsi de détecter rapidement ce cycle. D'un point de vue asymptotique, il est alors logique d'obtenir autant d'échantillons que nos limites de mémoire le permettent: nous pouvons aussi bien définir G pour avoir un y (n) éléments attendus qui sont inférieurs à n .
  - Si la longueur maximale d'une orbite dans S est supposée être L , nous pouvons laisser G être les multiples entiers de L  /  y (n) .
  - S'il n'y a pas de longueur attendue, nous pouvons simplement échantillonner une fois tous les n  /  y (n)éléments; il s'agit en tout cas d'une borne supérieure sur les intervalles entre les échantillons.

• Si, en cherchant un nouveau composant, nous commençons à parcourir des éléments de S que nous avons visités précédemment (soit à partir d'un nouveau composant en cours de découverte, soit d'un ancien dont le cycle terminal a déjà été trouvé), cela prendra au plus n  /  y ( n) itérations pour rencontrer un élément précédemment échantillonné; il s'agit alors d'une limite supérieure du nombre de fois, pour chaque tentative de trouver un nouveau composant, nous traversons des nœuds redondants. Parce que nous faisons n de telles tentatives, nous visiterons alors de manière redondante des éléments de S au plus n ²  /  y (n) fois au total.

• Le travail requis pour tester l'appartenance à samplesest O ( y (n)  log  y (n) ), que nous répétons à chaque visite: le coût cumulé de cette vérification est O ( n ²  log  y (n) ). Il y a aussi le coût de l'ajout des échantillons à leurs collections respectives, qui est cumulativement O ( y (n)  log  y (n) ). Enfin, chaque fois que nous rencontrons à nouveau un composant découvert précédemment, nous devons consacrer jusqu'à X (n)  log *  y (n) de temps pour déterminer le composant que nous avons redécouvert; comme cela peut se produire jusqu'à n fois, le travail cumulé impliqué est limité par n X (n)  log  y (n) .

Ainsi, le travail cumulé effectué pour vérifier si les nœuds que nous visitons figurent parmi les échantillons dominent le temps d'exécution: cela coûte O ( n ²  log  y (n) ). Il faut alors rendre y (n) le plus petit possible, c'est-à-dire O ( X (n) ).

Ainsi, on peut énumérer le nombre de cycles (qui est le même que le nombre de composants qui se terminent par ces cycles) dans l' espace O ( X (n)  log ( n )), en prenant O ( n ²  log  X (n) ) le temps de le faire, où X (n) est le nombre attendu de cycles.

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