Para começar, primeiro devemos entender do que se trata o algoritmo L citado na pergunta:
import copy as cp
def LPG(array, permutations=[]):
permutations.append(cp.copy(array)) # 1
j = len(array)-2
while True: # 2
if j+1 == 0:
return permutations
elif array[j] < array[j+1]:
break
else:
j -= 1
l = len(array)-1
while True: # 3
if array[j] >= array[l]:
l -= 1
else:
array[j], array[l] = array[l], array[j] # 4
break
subArray = array[j+1:]
subArray.reverse()
array[j+1:] = subArray
return LPG(array, permutations) # roda proxima permutacao
multisets = LPG([1, 2, 2, 3])
De acordo com a página 319, temos que:
(Visite) Visite a permutação a1, a2, ..., a_n
Isso é feito na primeira linha depois de definida a função. É visitado a primeira permutação possível, que é o próprio array dado como argumento na função LPG. É utilizado a biblioteca copy, que permite que o python copie os valores de uma estrutura, ao invés de fazer uma copia por referência e mudar os valores dentro de permutations conforme o algoritmo for avançando.
(Ache j) Dado j = n-1 (penúltimo elemento do array). Se aj >= a(j+1) diminua j em 1 repetidamente até que aj < a(j+1). Termine o algoritmo se j = 0. (Nesse ponto j é o menor subscrito de forma que já visitamos todas as outras permutações possíveis começando com a1, ... aj.
No bloco while com #2 ao lado, temos essa parte do algoritmo. Primeiro colocamos j como o penúltimo elemento do array utilizando len(array)-2, e então é iniciado o bloco while.
O primeiro if desso bloco while é para verificar se já rodamos por todas as permutações possíveis. Como o python começa a contar em 0, temos que verificar se j+1 é igual a 0 (no caso, ao invés de parar quando o algoritmo atinge o index 0, que seria a última verificação a ser feita, ele irá parar em -1, o que quer dizer que 0 já é o maior número do array.)
Caso falso, verificamos se o próximo valor é menor do que o atual. Caso seja, a estrutura while para e j será igual ao index desse número. Caso contrário, iremos reduzir j em 1, e procurar no antepenúltimo item se ele é menor do que o próximo, até que esse valor seja encontrado ou todas as permutações já tenham sido visitadas. Exemplo:
Considerando a lista [1, 2, 3, 4], começamos em lista[2], que é o penúltimo item. Verificamos se ele é menor do que o próximo item, lista[3]. Como é verdade, a estrutura while para e temos nosso j = 2.
(Aumente aj) Dado l = n (último element do array). Se aj >= al, diminua l em 1 repetidamente até que aj < al. Então mude a posição de aj com al. (Como a(j+1) >= ... >= an, o elemento al é o menor elemento maior que aj que legitimadamente segue a1 ... a(j-1) em uma permutação. Antes da mudança temos a(j+1) >= ... >= a(l-1) >= al > aj >= a(l+1) >= ... >= an; depois da mudança, temos a(j+1) >= ... >= a(l-1) >= aj > al >= a(l+1) >= ... > = a_n
Após o fim da primeira estrutura while temos o l sendo iniciado como o último elemento da lista. Verificamos se lista[j] é maior ou igual que o último elemento, caso seja verdade, diminuímos o valor de l até que encontremos um lista[j] < lista[l]. Quando isso acontecer, iremos trocar lista[j] e lista[l] de lugar (bloco else). Exemplo:
Na lista [1, 2, 3, 4], temos j = 2. Considerando l = 3, temos que lista[j] < lista[l], então trocamos eles de lugar, ficando [1, 2, 4, 3] e paramos essa estrutura while.
(Inverta a(j+1) ... an) Dado k = j + 1 e l = n. Então, enquanto k < l, troque ak e al de posição e coloque k = k + 1, l = l - 1. Retorne para a primeira instrução.
Após a troca ser feita, temos que inverter do índice j+1 até o final da lista. Isso é feito utilizando uma variável de suporte chamada subArray, que vai armazenar os valores que devem ser invertidos. Após isso, é utilizado o método reverse(), que irá inverter a lista. Depois, colocamos a lista organizada de j+1 até o final de volta ao array original. Exemplo:
subArray = [4, 3]
(reverter) subArray = [3]
array[4:] = subArray
array = [1, 2, 4, 3]
Nesse ponto, a função LPG é chamada novamente, com permutations = [[1, 2, 3, 4]], que seria a primeira permutação a ser visitada.
Esse algoritmo permite que visitamos todas as permutações de um conjunto de números de forma crescente, desde que esse conjunto esteja ordenado. Com algumas modificações, podemos gerar todas as permutações de seus subconjuntos:
import copy as cp
def LPG(array, permutations=[], start=0, final=2, initialArray=True, arraySliceLength=2, perm=False):
if perm:
arraySlice = cp.copy(array)
else:
arraySlice = cp.copy(array[start:final])
permutations.append(cp.copy(arraySlice))
j = len(arraySlice)-2
while True:
if j+1 == 0:
return permutations
elif arraySlice[j] < arraySlice[j+1]:
break
else:
j -= 1
l = len(arraySlice)-1
while True:
if arraySlice[j] >= arraySlice[l]:
l -= 1
else:
arraySlice[j], arraySlice[l] = arraySlice[l], arraySlice[j]
break
subArray = arraySlice[j+1:]
subArray.reverse()
arraySlice[j+1:] = subArray
permutations = LPG(arraySlice, permutations, start,
final, initialArray=False, perm=True) # roda proxima permutacao
if initialArray:
while True:
if final == len(array):
arraySliceLength += 1
start, final = 0, arraySliceLength
if arraySliceLength == len(array)+1:
permutations.append(set(array))
return permutations
else:
start += 1
final += 1
permutations = LPG(array, permutations, start,
final, False, arraySliceLength, perm=False)
else:
return permutations
multisets = LPG([1, 2, 2, 3])
print(multisets)
A estrutura do algoritmo que gera as permutações é praticamente o mesmo, com a mudança de que agora o array não é iniciado por inteiro na função, mas sim seus dois primeiros índices. Isso é feito por meio dos argumentos start e final, com valores iniciais de 0 e 2, respectivamente, já que o primeiro subconjunto escolhido será os dois primeiros valores do array.
O ínicio do algoritmo verifica se a operação a ser realizada é uma permutação ou não, utilizando o parâmetro perm. Caso, verdadeiro, o arraySlice será somente um cópia do própio array, para evitar que ele seja cortado com [start:final] sendo que só queremos realizar a permutação desse subconjunto. Caso contrário, arraySlice será uma cópia do subconjunto de array (com inicio e fim definidos nos argumentos da função LPG).
LPG irá retornar todas as permutações do primeiro subconjunto dessa forma. Supondo a lista [1, 2, 2, 3], será realizado a permutação de [1, 2], que é apenas [1, 2] e [2, 1]. Como não há mais permutações a serem feitas, o término da recursão na primeira estrutura while irá retornar permutations = [[1, 2], [2, 1]].
Agora, o algoritmo irá verificar se esse é o primeiro subconjunto a ser gerado com a estrutura if initialArray. Essa variável é definida no momento em que a função é chamada. Ela é feita para evitar que se inicie outras recursões dentro de permutações que estão sendo retornadas conforme o algoritmo avance. Como a primeira chamada essa variável é definida como True, temos que o algoritmo irá iniciar uma estrutura while.
Nesse bloco, temos um condicional para verificar se todos os subconjuntos de tamanho 2 já foram achados. Exemplo: Em [1, 2, 2, 3] caso final = 4, temos que o último subconjunto [2, 3] já foi visitado, e, assim, o algoritmo pode aumentar final em 1, e iniciar os subconjuntos de tamanho 3.
Como esse não é o caso, o algoritmo vai para o próximo condicional. Ele aumenta start e final em 1, e depois faz uma chamada à função LPG, com os valores de start e final atualizados para 1 e 2, respectivamente. E então, ele gera as as permutações de [2, 2], aumentando os índices novamente até que final = 4.
Quando isso acontecer, temos que o tamanho do subconjunto irá aumentar em 1, start será iniciado em 0 e final irá ser igual ao tamanho desse subconjunto, agora, 3. Agora, ele irá procurar pelo subconjunto [1, 2, 2]. Caso já tenhamos chegado ao último subconjunto possível (tamanho 4, o próprio array de entrada), o algoritmo adiciona os subconjuntos de tamanho 1 (os valores únicos dentro do array) utilizando a estrutura de dado set().
Exemplo de input e output:
multisets = LPG([1, 2, 2, 3])
print(multisets)
Multisets irá conter todas as permutações dos subconjuntos. O output será:
[[1, 2], [2, 1], [2, 2], [2, 3], [3, 2], [1, 2, 2], [2, 1, 2],
[2, 2, 1], [2, 2, 3], [2, 3, 2], [3, 2, 2], [1, 2, 2, 3],
[1, 2, 3, 2], [1, 3, 2, 2], [2, 1, 2, 3], [2, 1, 3, 2],
[2, 2, 1, 3], [2, 2, 3, 1], [2, 3, 1, 2], [2, 3, 2, 1],
[3, 1, 2, 2], [3, 2, 1, 2], [3, 2, 2, 1], {1, 2, 3}]