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