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

Question

j'ai rencontré ce problème lorsque vous faites une programmation enthousiaste. Le problème peut être exprimé comme suit:

  

Pour un multi-A, soit P (A) représentent la   ensemble de toutes les permutations possibles de A.   P (A) est naturellement divisée en   sous-ensembles disjoints qui sont équivalence   classes, avec la relation d'équivalence   être « peuvent être liés par des changements circulaires. » énumérer tous   ces classes d'équivalence en générant   exactement un membre de chacun d'entre eux.

Par exemple, considérez la multiset {0, 1, 1, 2}. Les permutations « 0112 » et « 1201 » sont des permutations uniques, mais celui-ci se trouvent par circulaire déplaçant l'ancien et vice versa. L'algorithme souhaité ne doit pas générer à la fois.

Bien sûr une approche force brute est possible: il suffit de générer des permutations - quelle que soit la duplication circulaire - en utilisant l'un des algorithmes de permutation multiset et duplications défausse trouvés par rapport aux résultats précédents. Cependant, cela tend à être inefficace dans la pratique. L'algorithme souhaité devrait exiger un minimum, sinon nulle comptabilité.

Les aperçus sur ce problème est très apprécié.

Answer 1

Sawada algorithme est

Answer 2

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

si A ne contient que 1 'élément, P (A) contient en outre une permutation. il est facile de voir les mêmes œuvres si A ne contient que 2 éléments.

Maintenant, supposons que vous avez déjà tout P (A) A avec n éléments, et que vous ajoutez un élément. il peut aller dans l'un des n points dans l'une des permutations en P (A).

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

EDIT: Je sais que je sorte d'ignorer le 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 que cela pourrait éliminer les doublons. (Toujours penser 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 jeu.

Ensuite, la chaque classe d'équivalence est juste une cession d'un élément de A à une position sur le cadran de l'horloge.

Une fois attribué une autre permutation à partir de la même classe d'équivalence peut être générée par une simple rotation de l'horloge sur le mur.

Pour générer une permutation sans rapport A vous devez avoir un élément sauter sur au moins un autre élément.

Maintenant l'algorithme que je vois serait de commencer par une mission par exemple dire que nous avons eu 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. Ensuite, notre première opération serait d'échange a et b. puis a et c, puis a et d, alors nous irions à b et échanger avec l'élément dans la position 3, qui est maintenant c.

Faire jusqu'à ce que nous ayons atteint d génèrerait un représentant de toutes les classes d'équivalence.

Cela ne prend pas soin de 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 n'apparaît une fois, alors vous pouvez mettre cet élément dans la première position de votre liste pour toutes les réponses, puis générer toutes les permutations du reste les nombres. Ceci est une solution assez trivial car le fait que votre premier élément est unique qui assure qu'il n'y a pas d'équivalents par cycle de décalage des éléments. Il est donc clair toutes les solutions que vous produisez doit être unique.

Le problème évident est que si vous avez pas d'éléments qui sont célibataires alors ce ventile entièrement. La principale raison pour laquelle je mets cela en est becasue il existe plusieurs autres solutions traitant pas doublons et je pense que celui-ci est plus efficace que de les (Résout plus de cas) est donc digne de mention. Son simple aussi assez en termes de comprendre comment il fonctionne et 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 est répété) vous pouvez regarder seulement ses permutations et celles qui permettraient de répétition de changement de cycle, comme avant assumign que vous pouvez un « lock » 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 avoir:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

Le dernier de ces derniers est le même que le premier (à moins de décalage cyclique) peut donc être ignorée, idem deuxième et quatrième. Le troisième (AXXAXX) peut être pédalé par trois pour revenir à lui-même a donc le potentiel pour les cycles. Les deux premiers ne peut jamais donner lieu à des cycles, peu importe la façon dont vous le cycle de fois eux afin mais vous distribuer les autres éléments que vous assurerez qu'ils sont des distributions uniques et vous sont garantis pour obtenir des résultats uniques par cycle.

Pour le troisième motif que le cycle de boîte (AXXAXX) vous auriez besoin de regarder l'élément B et répéter le processus pour ceux-ci. Cette fois, vous ne unfortuantely pourrez pas utiliser l'astuce de verrouiller 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 de travail, mais pleinement ses quelques thougths sur la façon d'éviter d'avoir à la force brute.

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 rendement:

['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']