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

Rank de uma permutacao seguindo o algoritmo L

+1 voto
27 visitas
perguntada Out 21 em Ciência da Computação por daniel cunha (16 pontos)  

A imagem será apresentada aqui.

Exercício 3 da página 345 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

O rank de um dado arranjo X gerado por um algoritmo computa o numero de outros arranjos gerados previamente a X. Compute o rank de 314592687.

Compartilhe

1 Resposta

0 votos
respondida Out 21 por daniel cunha (16 pontos)  
editado Out 21 por daniel cunha

Seguindo o enunciado, vamos primeiramente computar o rank utilizando o algoritmo L. Para tanto, replicacou-se o algoritmo disponibilizado no link abaixo que elenca todas as permutacoes lexicograficas para um dado \( p = [a1,a2,…,an] \) e foi adicionada uma alteracao no codigo com vistas a computar o rank por meio da funcao index.

Link para codigo gerador do rol de arranjos lexicograficos .

print("Algoritmo-L")
import time
inicio = time.time()

def next_permutation_helper(perm):
    if not perm:
        return perm

n = len(perm)

"""
Find k such that p[k] < p[k + l] and entries after index k appear in
decreasing order.
"""
for i in range(n - 1, -1, -1):
    if not perm[i - 1] >= perm[i]:
        break

# k refers to the inversion point
k = i - 1

# Permutation is already the max it can be
if k == -1:
    return []

"""
Find the smallest p[l] such that p[l] > p[k]
(such an l must exist since p[k] < p[k + 1].
Swap p[l] and p[k]
"""
for i in range(n - 1, k, -1):
    if not perm[k] >= perm[i]:
        perm[i], perm[k] = perm[k], perm[i]
        break

# Reverse the sequence after position k.
perm[k + 1 :] = reversed(perm[k + 1 :])

return perm


def multiset_permutation(B):
"""
We sort array first and `next_permutation()` will ensure we generate
permutations in lexicographic order
"""
A = sorted(B)
result = list()


while True:
    result.append(A.copy())
    A = next_permutation_helper(A)
    if not A:
        break

r = result.index(list(B))

return r

if __name__ == "__main__":

B = [3,1,4,5,9,2,6,8,7]

print(multiset_permutation(B))
fim = time.time()
print("Tempo de execução: ", fim - inicio)

Contudo, nota-se que codigo nao e' rapido. Outra opcao seria usar o codigo abaixo que computa o rank lexicografico sem usar o algoritmo L. que foi construido fazendo uma alteracao marginal no codigo do link abaixo a fim de considerar os digitos \( >0\).

Explicao super interessante sobre o rank lexicografico com codigo para permutacoes que levam em conta o digito 0.

print("Algoritmo alternativo")
import time
inicio = time.time()

def permutation_rank(p):
"""Given a permutation of {0,..,n-1} find its rank according to lexicographical order

   :param p: list of length n containing all integers from 0 to n-1
   :returns: rank between 0 and n! -1
   :beware: computation with big numbers
   :complexity: `O(n^2)`
"""

n = len(p)
factorials = 1                                 # compute (n-1) factorial
for i in range(2, n):
    factorials *= i
r = 0                                    # compute rank of p
digits = list(range(1,n+1))                  # all yet unused digits
for i in range(n-1):                     # for all digits except last one
    q = digits.index(p[i])
    r += factorials * q
    del digits[q]                        # remove this digit p[i]
    factorials //= (n - 1 - i)                 # weight of next digit
return r

if __name__ == "__main__":

    p = [3,1,4,5,9,2,6,8,7]
    print(permutation_rank(p))
    fim = time.time()
    print("Tempo de execução: ", fim - inicio)
comentou Out 21 por Rodrigo Stuckert (46 pontos)  
Olá, Daniel. Tudo bem?

Sua solução foi boa, vi que você replicou certinho o Algoritmo L de geração de permutações lexicográficas do Knuth (p. 319), e também trouxe uma resposta alternativa mais prática desconsiderando tal algoritmo. Minha única sugestão seria evitar o uso de for loops com breaks, fazendo uso de while loops quando possível, para facilitar a legilibilidade do código.

Quanto ao desempenho de execução da primeira versão, uma sugestão seria a adição de uma variável de contagem dos loops na função "multiset_permutation", bem como uma cláusula de retorno quando a permutação "A" fosse igual à lista "B" original. Isso diminuiria o overhead tanto pela remoção da lista "results", quanto pelo retorno antecipado da função. Ficaria mais ou menos assim:

    def multiset_permutation(B):
        """ Returns the rank of combinatorial arrangement "B".
        
        B: numerical list, without repetitions
        """
        A = sorted(B)
        count = 0
        
        # Finds the rank
        while True:
            count += 1
            A = next_permutation_helper(A)
            if A == B:
                return count

Forte abraço!
...