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)