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

Milionésima iteração de uma lista com crescimento restrito

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

Qual a milionésima partição de {1,...,12} gerado pelo algoritmo H ?

O algoritmo H (Crescimento restrito de palavras em ordem lexicográfica) é representado por:

H1. |Inicialização|. Atribua A1 ... An <-- 0 ... 0, Bn-1 <-- 1 ... 1, e m <-- 1.
H2. |Visitação.| Visite a lista a1 ... an, que representa uma partição em m + |An = m| blocos. E então vá para H4 se An = m.
H3. |Aumente An.| Incremente An em uma unidade e retorne para H2.
H4. |Encontre j.| Atribua j <-- n - 1; Então, enquanto Aj = Bj, decremente j em uma unidade.
H5. |Aumente Aj.| Encerre se j =1. Caso não, incremente Aj em uma unidade.
H6. |Zerar de Aj+1 a An| Atribua m <-- Bj + |Aj = Bj| e j <-- j + 1. Então, enquanto j < n, atribua Aj <-- 0, Bj <-- m, e incremente j em uma unidade. Finalmente atribua An <-- 0 e vá apra H2.
  • Exercício 3 do livro The Art of Computer Programming, Donald E. Knuth, Capítulo: Combinatorial Serching
Compartilhe

1 Resposta

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

Uma lista de crescimento restrito, restricted growth string, aceita apenas elementos que satifazem as condições:

  1. A1 = 0
  2. Para 1 ≤ j < n , A imagem será apresentada aqui.

Um exemplo de lista de crescimento restrito com 15 partições:

[0000, 0001, 0010, 0011, 0012, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0123]

Estas listas são úteis para descrever partições de um conjunto, desta forma supondo um conjunto {1,2,3,4} e utilizando a 8° posição da lista crescimento restrito, utilizado como exemplo acima, 0102, significa dizer que: o 1° e 3° elemento do conjuto (1 e 3) estão em uma mesma partição, e o 2° elemento (2) e 4° elemento (4) estão em partições individuais cada uma. Desta forma, resultaria nas partições: {1,3}, {2} e {4}.

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

n = 12 # Tamanho do conjunto
# H1 (Inicialização das variáveis)
A = Gen_list(n + 1,0) # Lista de crescimento restrito
B = Gen_list(n + 1,1) # Auxiliar
C = [1,2,3,4,5,6,7,8,9,10,11,12] # Conjunto
m = 1 # Limite inicial

A função gen_list foi utilizada para gerar uma lista no padrão [1,...,1] com valores iguais e tamanho n. A implementação dessa função foi realizada da seguinte forma:

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

Para encontrar o valor de crescimento restrito, utilizando o Algoritmo H do livro de referência do problema, foi desenvolvido da seguinte forma:

for count in range(10**6): # H2 (Visita da lista de crescimento restrito)
    if A[n] == m :  # H4 (Encontra o valor j (algorismo a ser incrementado))
        j = n - 1
        while A[j] == B[j]:
            j -= 1
    else: 
        A[n] += 1 # H3 (Incrementa)
        continue # Retorna ao H2
    if (j == 1): # H5 
        break # Ultima particao, fim do loop
    else: 
        A[j] += 1 # (Incrementa o algarismo encontrado indice j)
    if(B[j] == A[j]):
        m = B[j] + 1 # H6 
    else: m = B[j] # Encontra o limite de incremento de cada posicao
    j += 1
    while j < n: # Recomecar a contagem ao incrementar um algarismo mais significativo
        A[j] = 0
        B[j] = m 
        j += 1
    A[n] = 0

del A[0] # Corrigir adaptação do algoritmo para lista iniciada com indice 0 em python

O algoritmo H está em um loop com 1.000.000 de passagens, como descrito no problema. Obtida a partição do algoritmo anterior, o resultado pode ser visto a partir do seguinte código:

for i in range(12): #Possíveis partições
    aux = []
    for j in range(12):# Percorre a lista de crescimento
        if (A[j] == i):
            aux.append(C[j]) # Forma a partição
    if len(aux) > 0:  # Caso a partição esteja vazia não será apresentada
        out.append(aux)

print("Milionésima iteração do algoritmo H: " + str(A))    
print("Partições para o conjunto "+ str(C) + ": "+str(out)) 

O resultado encontrado para o problema foi:

Milionésima iteração do algoritmo H: [0, 1, 0, 2, 2, 0, 3, 4, 5, 0, 4, 2]
Partições para o conjunto [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]:
[[1, 3, 6, 10], [2], [4, 5, 12], [7], [8, 11], [9]]

...