Existe-t-il un algorithme pour générer toutes les permutations circulaires uniques d'un multiset?

Question

J'ai rencontré ce problème en faisant une programmation enthousiaste. Le problème peut être exprimé comme suit:

Pour multiset A, soit P (A) représentent le ensemble de toutes les permutations possibles de A. P (A) est naturellement divisé en sous-ensembles disjoints qui sont l'équivalence classes, avec la relation d'équivalence étant "peut être reliée par des déplacements circulaires." Enumérez toutes ces classes d'équivalence en générant exactement un membre de chacune d'elles. Par exemple, considérons le multiset {0, 1, 1, 2}.

Les permutations "0112" et "1201" sont des permutations uniques, mais la dernière peut être trouvée en décalant circulairement la première et vice versa. L'algorithme désiré ne devrait pas générer les deux.

Bien sûr, une approche de force brute est possible: il suffit de générer des permutations - indépendamment de la duplication circulaire - en utilisant l'un des algorithmes de permutation multiset, et de rejeter les doublons trouvés par comparaison avec les résultats précédents. Cependant, ceci tend à être inefficace dans la pratique. L'algorithme souhaité devrait nécessiter une comptabilité minimale, voire nulle.

Toute idée de ce problème est très appréciée.

Answer 1

Sawada's algorithm

Answer 2

il est un peu plus facile d'aller à ce bas vers le haut:

si A ne contient que 1 élément, P (A) contient également une permutation. il est facile de voir la même chose si A ne contient que 2 éléments. Maintenant, supposons que vous ayez déjà tout P (A) pour A avec n éléments, et vous ajoutez un élément. il peut aller dans l'un des n emplacements dans l'une des permutations de P (A).

Je pense que cette idée se traduit assez directement par un algorithme récursif dans la langue de votre choix, et j'espère que mon explication était assez claire.

EDIT: Je sais que je sorte de fait abstraction du fait que A peut contenir des éléments en double, mais toujours penser à cette partie :)

comme un bien - si vous triait a avant de commencer l'algorithme de permutation, je pense cela pourrait éliminer les doublons. (Toujours penser à ça aussi)

Answer 3

Pour une compréhension intuitive du problème, je pense que nous pouvons employer cette métaphore. Visualisez une horloge sur le mur, mais au lieu d'avoir 12 positions sur le visage, il a n où n est le nombre d'éléments dans votre ensemble.

Alors la classe d'équivalence de chaque est juste une affectation d'un élément de A à une position sur la face de l'horloge.

Une fois attribué une autre permutation de la même classe d'équivalence peut être générée en tournant simplement l'horloge sur le mur.

Pour générer une autre permutation non liée de A, vous devez faire passer un élément au-dessus d'au moins un autre élément.Maintenant l'algorithme comme je le vois serait de commencer par une affectation par exemple dire que nous avions quatre éléments dans A = {a, b, c, d} et nous les avons assignés aux 12, 3, 6 et 9 positions respectivement pour la clarté visuelle. Alors notre première opération serait d'échanger a et b. alors a et c, puis a et d, alors nous irions à b et nous l'échangerions avec l'élément dans la position 3 qui est maintenant c. Faire cela jusqu'à ce que nous atteignions d générerait un représentant de toutes les classes d'équivalence.

Cela ne prend pas en charge les doublons, mais il devrait être beaucoup plus efficace que de générer toutes les permutations de A.

Answer 4

La pensée qui me vient à l'esprit est que pour un ensemble qui a au moins un élément qui ne apparaît une fois alors vous pouvez mettre cet élément dans la première position de votre liste pour toutes les réponses et ensuite générer toutes les permutations du reste des nombres. C'est une solution assez triviale puisque le fait que votre premier élément soit unique assure qu'il n'y a pas d'équivalents en déplaçant les éléments. Il est clair que toutes les solutions que vous générez doivent être uniques.

Le problème évident est que si vous n'avez pas d'éléments qui sont simples, cela se décompose complètement. La raison principale pour laquelle je mets ceci est parce qu'il y a plusieurs autres solutions traitant des doublons et je pense que celui-ci est plus efficace qu'eux (résout plus de cas) donc mérite d'être mentionné. C'est aussi très simple en termes de compréhension de son fonctionnement et de sa mise en œuvre. J'espère juste que mon raisonnement est solide. ;-)

Modifier pour d'autres réflexions:

Il me semble que ce principe peut être étendu à la situation où vous avez des doublons dans une certaine mesure. Si vous prenez un élément (que nous supposons maintenant répété), vous pouvez regarder seulement ses permutations et celles qui permettent la répétition du cycle, comme avant d'assumer que vous pouvez "verrouiller" un en place sans perte de généralité . par exemple, si vous avez un total de 6 éléments et A apparaît deux fois dans cet ensemble alors vous pouvez:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

Le dernier d'entre eux est le même que le premier (dans les décalage cyclique) peut donc être ignoré, idem le deuxième et le quatrième. Le troisième (AXXAXX) peut être recyclé par trois pour revenir à lui-même, ce qui a le potentiel de cycles. Les deux premiers ne peuvent jamais donner lieu à des cycles, peu importe le nombre de cycles que vous les utilisez. Ainsi, vous distribuez les éléments restants dont vous avez besoin. Assurez-vous qu'ils sont uniques et que vous obtenez des résultats uniques.

Pour le troisième modèle qui peut cycle (AXXAXX) vous devez regarder l'élément B et répéter le processus pour ceux-ci. Cette fois malheureusement, vous seriez incapable d'utiliser l'astuce de verrouillage de la première valeur pour gagner du temps.

Je ne suis pas 100% sûr de savoir comment vous y prendre pour faire cela dans un programme entièrement travail, mais ses quelques thougths sur la façon d'éviter d'avoir à la force brutale.

Answer 5

Je propose ici une solution mise en œuvre en python

import itertools as it 

L = ['a','b','c','d'] 
B = it.combinations(L,2) 
swaplist = [e for e in B] 
print 'List of elements to permute:' 
print swaplist 
print 
unique_necklaces = [] 
unique_necklaces.append(L) 
for pair in swaplist: 
    necklace = list(L) 
    e1 = pair[0] 
    e2 = pair[1] 
    indexe1 = L.index(e1) 
    indexe2 = L.index(e2) 
    #swap 
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1] 
    unique_necklaces.append(necklace) 

for n in unique_necklaces: 
    # Commented code display the rotation of the elements in each necklace 
    print 'Necklaces' 
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)] 

L'idée est de construire différents colliers par permutations de deux éléments.Pour une liste de quatre éléments a, b, c, d, l'algo donne:

['a', 'b', 'c', 'd'] 
['b', 'a', 'c', 'd'] 
['c', 'b', 'a', 'd'] 
['d', 'b', 'c', 'a'] 
['a', 'c', 'b', 'd'] 
['a', 'd', 'c', 'b'] 
['a', 'b', 'd', 'c']