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

Gerar todas as partições {1,..,n} que atendam a condição de left-to-right mínima.

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

Sugira uma forma de gerar todas as permutações de {1,...,n} que tenham exatamente m left-to-right mínima.

  • Exercício 8 do livro The Art of Computer Programming, Donald E. Knuth, Capítulo: Combinatorial Serching
Compartilhe

1 Resposta

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

A solução buscada, utilizando como referência o livro da questão problema, foi permutar a lista [1,..,n] de forma a testar cada permutação e encontrar seu valor de mínimo left-to-right, onde um elemento é o menor que todos a sua esquerda, assim, por exemplo: [1,2,3] somente o elemento 1 teria a condição de minimo left-to-right (LRM) e em [3,2,1] todos os elemento teriam essa condição, a função retorna somente as permutações em que o número de elementos que satisfaz a condição de mínimo left-to-right é igual a m.

A imagem será apresentada aqui.

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

n = int(input("n = "))
m = int(input("m = ")) # Minimo left-right
lista = gen_list(int(n))
listas_perm = permuta(lista)
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 obejtivo 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.

Por fim, para selecionar apenas as permutações onde possuem m elemento(s) left-to-right mínima, foi executado o seguinte código:

for ls in listas_perm: # Para cada permutacao de [1,..,n]
    lrm = 0 # numero de elementos que satifazem a condicacao de minimo left-right
    for i in range(n):# Cria blocos de C1 a Cn e analisa cada elemento em loop aninhado
        lrm_t = True 
        for l in ls[:i]:
            if not (ls[i] <= l ): # Caso um elemento nao condicacao de minimo left-right (LRM)
                lrm_t = False
        if(lrm_t):
            lrm +=1
    if (lrm == m) and (ls not in lista_out): # Verifica se a permutacacao atende o criterio LRM = m
        lista_out.append(ls)
    print(str(lista_out)) # Lista de listas de permutacoes que atendem ao criterio de LRM = m

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

Para m =1:

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]

Para m =2:

[[2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2], [4, 1, 2, 3], [4, 1, 3, 2]]

Para m =3:

[[3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 2, 1], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2]]

Para m =4:

[[4, 3, 2, 1]]

...