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

Sub grupos de permutações lexográficas

0 votos
7 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 6 dias atrás 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)
...