54 lines
3.1 KiB
Text
54 lines
3.1 KiB
Text
A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items.
|
|
For our purposes the ranking will assign integers <math>0 .. (n! - 1)</math> to an ordering of all the permutations of the integers <math>0 .. (n - 1)</math>.
|
|
|
|
For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:
|
|
|
|
<pre> PERMUTATION RANK
|
|
(0, 1, 2, 3) -> 0
|
|
(0, 1, 3, 2) -> 1
|
|
(0, 2, 1, 3) -> 2
|
|
(0, 2, 3, 1) -> 3
|
|
(0, 3, 1, 2) -> 4
|
|
(0, 3, 2, 1) -> 5
|
|
(1, 0, 2, 3) -> 6
|
|
(1, 0, 3, 2) -> 7
|
|
(1, 2, 0, 3) -> 8
|
|
(1, 2, 3, 0) -> 9
|
|
(1, 3, 0, 2) -> 10
|
|
(1, 3, 2, 0) -> 11
|
|
(2, 0, 1, 3) -> 12
|
|
(2, 0, 3, 1) -> 13
|
|
(2, 1, 0, 3) -> 14
|
|
(2, 1, 3, 0) -> 15
|
|
(2, 3, 0, 1) -> 16
|
|
(2, 3, 1, 0) -> 17
|
|
(3, 0, 1, 2) -> 18
|
|
(3, 0, 2, 1) -> 19
|
|
(3, 1, 0, 2) -> 20
|
|
(3, 1, 2, 0) -> 21
|
|
(3, 2, 0, 1) -> 22
|
|
(3, 2, 1, 0) -> 23</pre>
|
|
|
|
Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).
|
|
|
|
One use of such algorithms could be in generating a small, random, sample of permutations of <math>n</math> items without duplicates when the total number of permutations is large. Remember that the total number of permutations of <math>n</math> items is given by <math>n!</math> which grows large very quickly: A 32 bit integer can only hold <math>12!</math>, a 64 bit integer only <math>20!</math>. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.
|
|
|
|
A [http://stackoverflow.com/questions/12884428/generate-sample-of-1-000-000-random-permutations question on the Stack Overflow site] asked how to generate one million random and indivudual permutations of 144 items.
|
|
|
|
|
|
;Task:
|
|
# Create a function to generate a permutation from a rank.
|
|
# Create the inverse function that given the permutation generates its rank.
|
|
# Show that for <math>n=3</math> the two functions are indeed inverses of each other.
|
|
# Compute and show here 4 random, individual, samples of permutations of 12 objects.
|
|
|
|
|
|
;Stretch goal:
|
|
* State how reasonable it would be to use your program to address the limits of the Stack Overflow question.
|
|
|
|
|
|
;References:
|
|
# [http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/RankPerm.html Ranking and Unranking Permutations in Linear Time] by Myrvold & Ruskey. (Also available via Google [https://docs.google.com/viewer?a=v&q=cache:t8G2xQ3-wlkJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.43.4521%26rep%3Drep1%26type%3Dpdf+&hl=en&gl=uk&pid=bl&srcid=ADGEESgDcCc4JVd_57ziRRFlhDFxpPxoy88eABf9UG_TLXMzfxiC8D__qx4xfY3JAhw_nuPDrZ9gSInX0MbpYjgh807ZfoNtLrl40wdNElw2JMdi94Znv1diM-XYo53D8uelCXnK053L&sig=AHIEtbQtx-sxcVzaZgy9uhniOmETuW4xKg here]).
|
|
# [http://www.davdata.nl/math/ranks.html Ranks] on the DevData site.
|
|
# [http://stackoverflow.com/a/1506337/10562 Another answer] on Stack Overflow to a different question that explains its algorithm in detail.
|
|
<br><br>
|