How to resolve the algorithm Permutations/Rank of a permutation step by step in the REXX programming language
How to resolve the algorithm Permutations/Rank of a permutation step by step in the REXX programming language
Table of Contents
Problem Statement
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
0.. ( n ! − 1 )
{\displaystyle 0..(n!-1)}
to an ordering of all the permutations of the integers
0.. ( n − 1 )
{\displaystyle 0..(n-1)}
. For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank: 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
n
{\displaystyle n}
items without duplicates when the total number of permutations is large. Remember that the total number of permutations of
n
{\displaystyle n}
items is given by
n !
{\displaystyle n!}
which grows large very quickly: A 32 bit integer can only hold
12 !
{\displaystyle 12!}
, a 64 bit integer only
20 !
{\displaystyle 20!}
. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them. A question on the Stack Overflow site asked how to generate one million random and indivudual permutations of 144 items.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Permutations/Rank of a permutation step by step in the REXX programming language
Source code in the rexx programming language
/*REXX program displays permutations of N number of objects (1, 2, 3, ···). */
parse arg N y seed . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 4 /*Not specified? Then use the default.*/
if y=='' | y=="," then y= 17 /* " " " " " " */
if datatype(seed,'W') then call random ,,seed /*can make RANDOM numbers repeatable. */
permutes= permSets(N) /*returns N! (number of permutations).*/
w= length(permutes) /*used for aligning the SAY output. */
@.=
do p=0 for permutes /*traipse through each of the permutes.*/
z= permSets(N, p) /*get which of the permutation it is.*/
say 'for' N "items, permute rank" right(p,w) 'is: ' z
@.p= z /*define a rank permutation in @ array.*/
end /*p*/
say /* [↓] displays a particular perm rank*/
say ' the permutation rank of' y "is: " @.y /*display a particular permutation rank*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
permSets: procedure expose @. #; #= 0; parse arg x,r,c; c= space(c); xm= x -1
do j=1 for x; @.j= j-1; end /*j*/
_=0; do u=2 for xm; _= _ @.u; end /*u*/
if r==# then return _; if c==_ then return #
do while .permSets(x,0); #= #+1; _= @.1
do v=2 for xm; _= _ @.v; end /*v*/
if r==# then return _; if c==_ then return #
end /*while···*/
return #+1
/*──────────────────────────────────────────────────────────────────────────────────────*/
.permSets: procedure expose @.; parse arg p,q; pm= p-1
do k=pm by -1 for pm; kp= k+1; if @.k<@.kp then do; q=k; leave; end
end /*k*/
do j=q+1 while j
end /*j*/
if q==0 then return 0
do p=q+1 while @.p<@.q
end /*p*/
parse value @.p @.q with @.q @.p
return 1
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Lingo programming language
You may also check:How to resolve the algorithm Sorting algorithms/Patience sort step by step in the ARM Assembly programming language
You may also check:How to resolve the algorithm Evaluate binomial coefficients step by step in the Quackery programming language
You may also check:How to resolve the algorithm Verify distribution uniformity/Chi-squared test step by step in the J programming language
You may also check:How to resolve the algorithm Narcissist step by step in the Déjà Vu programming language