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

Permutações lexográficas de subconjuntos

0 votos
105 visitas
perguntada Dez 11, 2020 em Ciência da Computação por leonardocarvalho (21 pontos)  

As variações de um conjunto são as permutações de seus subconjuntos. Por exemplo, as variações de [1, 2, 2, 3] são

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

Mostre que pequenas mudanças no algoritmo L irá gerar todas as variações de um subconjunto [a1, a2, ... a_n].

(The Art of Computer Programming, Vol. 4A, Donald Knuth. Pg 345, exercício 8).

Compartilhe

1 Resposta

0 votos
respondida Dez 12, 2020 por leonardocarvalho (21 pontos)  
editado Dez 17, 2020 por leonardocarvalho

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:

  1. (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.

  2. (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.

  3. (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.

  4. (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}]
comentou Dez 17, 2020 por danielcajueiro (5,541 pontos)  
Talvez valha a pena colocar um exemplo explicito do codigo.
comentou Dez 17, 2020 por leonardocarvalho (21 pontos)  
Coloquei no final da resposta um exemplo igual a pergunta do autor.
comentou Dez 19, 2020 por Philippe Azevedo (16 pontos)  
Foi excelente seu trabalho, muito bem explicado e conforme exposto no livro.
Algumas observações:

1) Melhor prática: incluir o if __name__ == "__main__": no código principal.

2) "É utilizado a biblioteca copy, que permite que o python copie os valores de uma estrutura

O termo estrutura é meio inadequado, sugiro utilizar objeto.

3) Vc acertadamente mencionou acerca dos valores únicos dentro do array) utilizando a estrutura de dado set(), eles estão entre chaves {}, ultimo elemento da lista, quem não soubesse isso ficaria com dúvida.

4) Dica renomeie a nova função, pois ela tem uma finalidade diferente :)
...