Existe um algoritmo para gerar todas as permutações circulares exclusivas de um multiconjunto?

StackOverflow https://stackoverflow.com/questions/3467914

Pergunta

Encontrei esse problema ao fazer alguma programação entusiasmada.O problema pode ser expresso da seguinte forma:

Para um multiset A, deixe p (a) denotar o conjunto de todas as permutações possíveis de A.P (a) é naturalmente dividido em subconjuntos disjuntos que são classes de equivalência, com a relação de equivalência "pode ​​ser relacionada por mudanças circulares". Enumere todas essas classes de equivalência gerando exatamente um membro de cada uma delas.

Por exemplo, considere o multiconjunto {0, 1, 1, 2}.As permutações "0112" e "1201" são permutações únicas, mas a última pode ser encontrada deslocando circularmente a primeira e vice-versa.O algoritmo desejado não deve gerar ambos.

É claro que uma abordagem de força bruta é possível:apenas gere permutações - independentemente da duplicação circular - usando qualquer um dos algoritmos de permutação multiconjunto e descarte as duplicações encontradas por comparação com resultados anteriores.No entanto, isso tende a ser ineficiente na prática.O algoritmo desejado deve exigir uma contabilidade mínima, se não zero.

Qualquer visão sobre este problema é profundamente apreciada.

Foi útil?

Solução

Algoritmo de Sawada

Outras dicas

é um pouco mais fácil fazer isso de baixo para cima:

se A contém apenas 1 elemento, P(A) também contém uma permutação.é fácil ver que o mesmo funciona se A contém apenas 2 elementos.

Agora, vamos supor que você já tenha todos os P(A) para A com n elementos e adicione um elemento.ele pode estar em qualquer um dos n pontos em qualquer uma das permutações em P(A).

Acho que essa ideia se traduz diretamente em um algoritmo recursivo na linguagem de sua escolha e espero que minha explicação tenha sido clara o suficiente.

EDITAR:Eu sei que ignorei o fato de que A pode conter elementos duplicados, mas ainda estou pensando nessa parte :)

apenas como um pensamento - se você classificou A antes de iniciar o algoritmo de permutação, acho que isso pode eliminar duplicatas.(ainda pensando nisso também)

Para uma compreensão intuitiva do problema, penso que podemos empregar esta metáfora.Visualize um relógio na parede, mas em vez de ter 12 posições no mostrador ele tem n onde n é o número de elementos do seu conjunto.

Então cada classe de equivalência é apenas uma atribuição de um elemento de A a uma posição no mostrador do relógio.

Uma vez atribuída, outra permutação da mesma classe de equivalência pode ser gerada simplesmente girando o relógio na parede.

Para gerar outra permutação não relacionada de A, você precisa fazer com que um elemento pule pelo menos um outro elemento.

Agora, o algoritmo, como vejo, seria começar com uma atribuição, por exemplo, digamos que tínhamos quatro elementos em A = {a, b, c, d} e os atribuímos às posições 12, 3, 6 e 9, respectivamente, para visual clareza.Então nossa primeira operação seria trocar a e b.então a e c, depois a e d, então iríamos para b e trocaríamos com o elemento na posição 3 que agora é c.

Fazer isso até chegarmos a d geraria um representante de todas as classes de equivalência.

Isso não resolve duplicatas, mas deve ser muito mais eficiente do que gerar todas as permutações de A.

O pensamento que me vem à mente é que para qualquer conjunto que tenha pelo menos um elemento que aparece apenas uma vez, você pode colocar esse elemento na primeira posição da sua lista para todas as respostas e então gerar todas as permutações do restante dos números.Esta é uma solução bastante trivial, pois o fato de seu primeiro elemento ser único garante que não haja equivalentes por deslocamento cíclico dos elementos.É claro que todas as soluções que você gera devem ser únicas.

O problema óbvio é que, se você não tiver elementos únicos, isso será totalmente destruído.A principal razão pela qual coloquei isso é porque existem várias outras soluções que lidam com não duplicatas e acho que este é mais eficaz que eles (resolve mais casos), por isso vale a pena mencionar.Também é bastante simples em termos de compreensão de como funciona e implementação.Só espero que meu raciocínio seja sólido.;-)

Edite para mais reflexões:

Ocorre-me que este princípio pode ser estendido à situação em que você tem duplicatas até certo ponto.

Se você pegar um elemento (que presumimos agora ser repetido), poderá observar apenas suas permutações e quais permitiriam a repetição da mudança de ciclo, como antes, suponha que você possa "travar" um no lugar sem perda de generalidade.por exemplo, se você tiver um total de 6 elementos e A aparecer duas vezes neste conjunto, você poderá ter:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

O último deles é igual ao primeiro (dentro da mudança cíclica), portanto pode ser ignorado, assim como o segundo e o quarto.O terceiro (AXXAXX) pode ser alternado por três para voltar a si mesmo, portanto tem potencial para ciclos.Os dois primeiros nunca podem dar origem a ciclos, não importa quantas vezes você os alterne, portanto, independentemente de como você distribui os elementos restantes, você só precisa garantir que eles sejam distribuições únicas e que você terá a garantia de obter resultados exclusivos por ciclo.

Para o terceiro padrão que pode circular (AXXAXX), você precisaria olhar para o elemento B e repetir o processo para eles.Desta vez, infelizmente, você não conseguirá usar o truque de bloquear o primeiro valor para economizar tempo.

Não tenho 100% de certeza de como você faria para transformar isso em um programa totalmente funcional, mas são algumas reflexões sobre como evitar a força bruta.

Proponho aqui uma solução implementada em 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)]

A ideia é construir colares diferentes através da permutação de dois elementos.Para uma lista de quatro elementos a, b, c, d o algoritmo produz:

['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']
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top