Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Sub grupos de permutações lexográficas

0 votos
8 visitas
perguntada Nov 18 em Ciência da Computação por JOAO PAULO (1 ponto)  

Modificar o algoritmo de permutação lexográfica a fim de podermos gerar também subgrupos dessas permutações. Por exemplo, a permutação lexográfica do grupo {1,2,2,3} será:

e, 1, 12, 122, 1223, 123, 1232, 13, 132, 1322
2, 21, 212, 2123, 2132, 22, 221, 2213, 223, 2231, 23, 231, 2312, 232, 2321
3, 31, 312, 3122, 32, 321, 3212, 322, 3221

Compartilhe

1 Resposta

0 votos
respondida Nov 18 por JOAO PAULO (1 ponto)  
editado Nov 19 por JOAO PAULO

A questão pede para mostrar como mudanças no algoritmo de permutação lexográfica (Algoritmo L) permite realizar permutações sobre todos os seus subgrupos.
O algoritmo L possui 4 passos e é definido da seguinte maneira:

A imagem será apresentada aqui.

O que temos que fazer é inserir uma variável de nível para que possamos determinar o tamanho do subgrupo gerado e em cima dele fazer as permutações necessárias. Essa variável nível será o tamanho da lista que passaremos. De modo que o maior nível irá representar o conjunto vazio, o segundo maior nível o conjunto com 1 elemento apenas e assim por adiante. Logo insiro antes do passo 1 original a seguinte instrução:

L.0[First Visit] set: depth ← length \((a_1 a_2….a_n)\) and the empty subset [] ← depth n. (So we’ll have \(a_i\)←depth \(n-1; a_i a_{(i+1)}\)←depth \(n-2\) and so on). Set \(a_t a_{(t+1)}…a_{(t+n)}\) elements of the sequence that are not in submultiset.

O passo 1 se mantem inalterado.

L.1 [Visit.] Visit the permutation \(a_1 a_2….a_n \)

No passo seguinte (passo 2 original), alteramos as instruções ligeiramente e tomamos o cuidado de sempre manter o nível “setado” anteriormente. Logo, teremos as seguintes alterações:

L.2 [Find \(j\).]. Set \(j←n-1\). If \(a_j≥a_{(j+1)}\), decrease j by 1 repeatedly
until \(a_j\) < \(a_{(j+1)}\). Terminate the algorithm if j=0. If the permutation
\(a_1 a_2…. \) has not covered all of its elements of own depth return to
L.1 and interchange \(a_{(i+1)}↔a_t\). Otherwise return to L.1 with depth-1
if depth>0.

Quando eu solicito para retornar para o L.1 com o nível “-1” significa que eu peço para fazer um subgrupo de 1 nível menor; i.e. com um elemento a mais. Com esse subgrupo com um elemento a mais, refaço a permutação, no entanto, mantendo o primeiro elemento como fixo. Note que eu solicito para que em determinado nível, o algoritmo procure dentro da permutação, todas as combinações possíveis de 2, 3, n termos, mas sempre mantendo o primeiro termo fixo. E peço para refazer esses passos recursivamente até permutarmos o subgrupo cheio (com o primeiro elemento fixo). Em termos gerais o que eu estou fazendo inicialmente é garantir que o primeiro ramo de uma árvore recursiva de uma sequência {1,2,3}, por exemplo, seja construído da seguinte forma:

A imagem será apresentada aqui.

No terceiro passo precisamos fazer uma pequena alteração no início do algoritmo a fim de se evitar que caso a sequência tenha elementos iguais, a permutação se repita:

L.3 [Increase \(a_j\).] Set l←n. If \(a_j>a_l\)...

Após essa parte passamos para o passo 4 e realizamos a seguinte alteração:

L.4 [Reverse \(a_{(j+1)}…a_n\).] Set \( k←j+1\) and \(l←n\). Then, while \( k< l \),
interchange \(a_k↔a_l\) and set \(k←k+1,l←l-1\). Return to L1, but with depth+\((n-1)\)

Assim, voltamos para o início do algoritmo e realizamos as permutações com os respectivos subgrupos mantendo o segundo item da sequência original como fixo. Se tomarmos a sequência do exemplo acima, nessa etapa (a primeira volta ao L.1) iremos construir o ramo da árvore com início 2.
O algoritmo a seguir é capaz de replicar em Python a ordenação com os múltiplos subgrupos sugerido pelo exercício:

 import collections

def permut_mult_lex(B):

        def permut_int_mult(depth, counter, permut):
            print("--",permut)

            if depth == 0:
                yield permut
                return

            # escolhas
            for key, value in counter.items():

                if value > 0:

                    # aqui faço as escolha
                    counter[key] -= 1
                    permut.append(key)

                    # procuro
                    yield from [
                        list(i) for i in permut_int_mult(depth - 1, counter, permut)
                    ]

                    # volto e refaço 
                    permut.pop()
                    counter[key] += 1


        counter = collections.Counter(B)

        return list(permut_int_mult(len(B), counter, []))


if __name__ == '__main__':
        A=[1,2,2,3]
        B = sorted(A)
        permut_mult_lex(B)
comentou 10 horas atrás por Arthur Quintão (1 ponto)  
editado 10 horas atrás por Arthur Quintão

Excelente explicação, João Paulo!

Infelizmente, não consegui entender muito bem seu código.

Seguindo sua explicação, segue uma segunda proposta de solução.

from itertools import product

def combinations(string):
    order=sorted(string)

    #created a list to fill with permutations
    permutation=[]

    #each loop == one more element
    for i in range(1,len(string)+1):
       permutation.append([''.join(i) for i in product(order, repeat = i)])

    #merged each list appended to permutation
    permutation =list(itertools.chain(*permutation))

    return permutation

if __name__=="__ main __":
   print(combinations("321"))
...