Permutations/Rank of a permutation: Difference between revisions

Content added Content deleted
(Promote from draft to full task status.)
m ({{out}})
Line 1: Line 1:
{{task}}
{{task}}
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>.
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:
For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:
Line 121: Line 122:
</lang>
</lang>


{{out}}
And here's the output:

<pre> 0: [ 1, 2, 3, 0 ] = 0
<pre> 0: [ 1, 2, 3, 0 ] = 0
1: [ 3, 2, 0, 1 ] = 1
1: [ 3, 2, 0, 1 ] = 1
Line 501: Line 501:
}</lang>
}</lang>


{{out}}
'''Output:'''

<pre>0 --> [0, 1, 2] --> 0
<pre>0 --> [0, 1, 2] --> 0
1 --> [0, 2, 1] --> 1
1 --> [0, 2, 1] --> 1
Line 672: Line 671:
test2('First ordering, large number of perms:', unranker1)</lang>
test2('First ordering, large number of perms:', unranker1)</lang>


{{out}}
;Sample output:
<pre>First ordering:
<pre>First ordering:
From rank 0 to [1, 2, 0] back to 0
From rank 0 to [1, 2, 0] back to 0
Line 779: Line 778:
(factorial (length xs))))]))
(factorial (length xs))))]))
</lang>
</lang>
{{out}}
Example and output:
<lang>
<pre>
(for/list ([n 24])
(for/list ([n 24])
(define p (perm '(0 1 2 3) n))
(define p (perm '(0 1 2 3) n))
Line 809: Line 808:
(22 (3 2 0 1) 22)
(22 (3 2 0 1) 22)
(23 (3 2 1 0) 23))
(23 (3 2 1 0) 23))
</lang>
</pre>


=={{header|REXX}}==
=={{header|REXX}}==
Line 815: Line 814:
this modified version starts the permute numbers with 0 (zero) instead of 1.
this modified version starts the permute numbers with 0 (zero) instead of 1.


Since this REXX program generates permutations without recursive calls, testing for the limit for a ''stack overflow'' wouldn't be
Since this REXX program generates permutations without recursive calls,
possible using this REXX program.
testing for the limit for a ''stack overflow'' wouldn't be possible using this REXX program.
<lang rexx>/*REXX program shows permutations of N number of objects (1,2,3, ...).*/
<lang rexx>/*REXX program shows permutations of N number of objects (1,2,3, ...).*/
parse arg N seed .; if N=='' then N=3 /*Not specified? Assume default*/
parse arg N seed .; if N=='' then N=3 /*Not specified? Assume default*/
Line 850: Line 849:
do j=q+1 while @.j<@.q; end; parse value @.j @.q with @.q @.j
do j=q+1 while @.j<@.q; end; parse value @.j @.q with @.q @.j
return 1</lang>
return 1</lang>
'''output''' when using the default input
{{out}} when using the default input
<pre style="overflow:auto;height:250px">
<pre style="overflow:auto;height:250px">
4 items, permute 0 = 0 1 2 3 rank= 0
4 items, permute 0 = 0 1 2 3 rank= 0
Retrieved from "https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation"