Neste protocolo, apresento um truque para classificar uma lista e, simultaneamente, calcular a permutação mapeando a posição de um elemento na lista classificada para sua posição na lista original.
Este é o truque em Python, embora a ideia possa ser implementada na linguagem de sua escolha:
>>> l = [ random.randint(1,1000) for _ in xrange(5) ]; l
[591, 760, 940, 764, 391]
>>> L = [ (l[i],i) for i in xrange(len(l)) ]
>>> L.sort()
>>> sorted_l,permutation = zip(*L)
>>> sorted_l
(391, 591, 760, 764, 940)
>>> permutation
(4, 0, 1, 3, 2)Normalmente, isso é útil quando informações adicionais relacionadas à chave são acessadas por meio do índice da chave na lista original.
Aproveitar!