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

Gerar todas as partições em blocos de tamanho 1 a n

0 votos
10 visitas
perguntada Nov 9 em Ciência da Computação por Renan Abrantes (16 pontos)  
editado Nov 9 por Renan Abrantes

Sugira um algoritmo para gerar todas as partições de {1,...,n} no qual possua exatamente c1 blocos de tamanho 1, c2 blocos de tamanho 2, ... , 1 bloco de tamanho n.

  • Exercício 6 do livro The Art of Computer Programming, Donald E. Knuth, Capítulo: Combinatorial Serching, página 432.
Compartilhe

1 Resposta

0 votos
respondida Nov 9 por Renan Abrantes (16 pontos)  

A solução buscada, utilizando como referência o livro da questão problema, foi permutar a lista [1,..,n] onde seria possível criar todos os possíveis blocos desta forma. Ex: n = 3, buscando os blocos C2, ao permutar resultaria em [1,2,3], [2,1,3], [3,1,2] ... e ao particionar cada permutação resultaria em todas os possíveis blocos [2,1], [1,2], [3,1], [3,2] ...
Como cada permutação poderia gerar um mesmo bloco foi criado uma condição para impedir. Por fim é removido os casos de partições com mesmos elementos como Ex. [1,2] e [2,1].

Para iniciar a implementação na linguagem python, foi inicializada as variáveis:

n = int(input("n = ")) # Tamanho da lista
lista = gen_list(int(n))
listas_perm = permuta(lista) # Lista de listas das permutações
lista_out = [] # Retorno na função "main" como solução

A função gen_list foi utilizada para gerar uma lista no padrão [1,...,n] em ordem crescente, e a função permuta tem o objetivo de gerar uma lista de listas, sendo cada lista interna uma permutação da lista gerada pela função anterior. A implementação dessas funções foi realizada da seguinte forma:

def gen_list(n): # Cria lista no padrão [1,...,n]
    lista = []
    for i in range(n):
        lista.append(i+1)
    return lista # Retorna uma lista no padrão [1,...,n]

def permuta(lista): # Gera n! permutacões de uma lista
    if len(lista) == 1: # Para n = 1
        return [lista]
    lista_out = []
    for i in range(len(lista)):
       ant = lista[i] # Elemento inicial de cada lista permutada
       resto = lista[:i] + lista[i+1:]
       for p in permuta(resto): # Iteracao com ponto final uma lista com n = 1
           lista_out.append([ant] + p)
    return lista_out # Retorna uma lista de listas permutadas

A função permuta é uma função iterativa onde após a seleção de um valor da lista é realizada uma sub-rotina, da mesma função para uma lista de tamanho n - 1, sem o elemento selecionado na interação anterior.

Para efetuar as partições das listas foi executado o seguinte código:

for i in range(n): # Para cada C1, ..., Cn
    for ls in listas_perm:
        for l in particiona(ls,i+1): # Para cada particao
            if (l not in lista_out) and (len(l) == i+1): # Não permite duplicacao nem blocos incompletos
                lista_out.append(l) 
    #saida = lista_out # Caso não remova duplicados
    saida = remove_duplicados(lista_out)
    print("C" + str(i+1) + " = " + str(saida)) # Retorno para console
    lista_out = [] 

É chamado a função particiona para cada lista permutada, esta função recebe o tamanho do bloco e a lista a ser particionada. A implementação da função particiona esta descrita abaixo:

def particiona(lista, size): # Separa uma lista em listas menores de tamanho "size" e seu resto de tamanho < "size"
    lista_out = []
    for i in range(0, len(lista), size): # Terceiro atributo "size" define o passo da variavel i criando o intervalo necessário
        lista_out.append(lista[i:i + size])
    return lista_out # Retorna uma lista de listas particionadas

Após prencher a lista das partições é eliminada os blocos com elementos iguais a partir da função remove_duplicados:

def remove_duplicados(lista): # Remove os casos de listas com elementos iguais, mantendo somente um Ex: [1,2] e [2,1] 
    lista_limpa=[] # Retorno da lista sem listas com elementos iguais
    for l in list(set(tuple(sorted(perm)) for perm in lista)): # Passa lista para estrutura de dados "set" que não permite dados duplicados e transforma novamente para lista
        lista_limpa.append(list(l))
    return lista_limpa

Para exemplificar, este algoritmo obteve como resultado para n = 4:

C1 = [[1], [2], [3], [4]]
C2 = [[2, 4], [1, 2], [3, 4], [1, 4], [2, 3], [1, 3]]
C3 = [[2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4]]
C4 = [[1, 2, 3, 4]]

...