permutation_rank

Determining rank of a permutation and generating permutation given rank.

This implementation is due to: https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation#Python

Implementation of algorithms described in [1].

References

[1]	(1, 2, 3) Myrvold, Wendy, and Frank Ruskey. “Ranking and unranking permutations in linear time.” Information Processing Letters 79.6 (2001): 281-284.

mr_utils.utils.permutation_rank.identity_perm(n)

Generate sequence 0:n-1.

mr_utils.utils.permutation_rank.init_pi1(n, pi)

Get the inverse permutation of pi.

mr_utils.utils.permutation_rank.pi2rank(pi, method='rank2', iterative=True)

Return rank of permutation pi.

Parameters:

• pi (list) – Permutation.
• method ({'rank1', 'rank2'}, optional) – Which ranking method to use.
• iterative (bool, optional) – Whether or not to use iterative or recursive version.

Returns:

rank – The rank of the provided permutation.

Return type:

int

Notes

The permutation pi should be a permutation of the list range(n) and contain n elements.

‘method’ should be one of {‘rank1’, ‘rank2’} corresponding to the two schemes presented in the Myrvold and Ruskey paper. There is an iterative version available for both algorithms.

Implements algorithms from [1].

mr_utils.utils.permutation_rank.rank2pi(r, n, method='rank2')

Given rank and permutation length produce the corresponding permutation.

Parameters:

• r (int) – Rank.
• n (int) – Lenth of the permutation.
• method ({'rank1', 'rank2'}) – Which ranking method to use.

Returns:

pi – Associated permutation.

Return type:

list

Notes

Implements algorithms from [1].

mr_utils.utils.permutation_rank.ranker1(n, pi, pi1)

Rank1 algorithm from M&R paper.

mr_utils.utils.permutation_rank.ranker1_iter(n, pi, pi1)

Iterative version of ranker1.

mr_utils.utils.permutation_rank.ranker2(n, pi, pi1)

Ranker2 algorithm from M&R paper.

mr_utils.utils.permutation_rank.ranker2_iter(n, pi, pi1)

Iterative version of ranker2.

mr_utils.utils.permutation_rank.unranker1(n, r, pi)

Given rank produce the corresponding permutation.

Rank is given by rank1 algorithm of M&R paper.

mr_utils.utils.permutation_rank.unranker2(n, r, pi)

Given rank produce the corresponding permutation.

Rank is given by rank2 algorithm of M&R paper.