Anonymous user
Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 23:25, 23 September 2016
, 7 years ago→{{header|Tcl}}: added zkl
m (→{{header|REXX}}: changed/added comments and whitespace, implemented some semantic changes.) |
(→{{header|Tcl}}: added zkl) |
||
Line 1,239:
===Addressing the extra credit===
The technique above can generate any random permutation of a list, but an equally viable approach (and one especially suitable to the SO question where the number of required permutations is small with respect to the number of possible permutations) would be to use a [[Knuth shuffle]] on a list and just use that with a quick check for repetitions, which could be implemented using a simple hashing check. (On the other hand, building a hash table of a million strings of 144 characters would not be too awkward on modern hardware.)
=={{header|zkl}}==
{{trans|D}}
<lang zkl>fcn computePermutation(items,rank){ // in place permutation of items
foreach n in ([items.len()..1,-1]){
r:=rank%n;
rank/=n;
items.swap(r,n-1);
}
items
}</lang>
<lang zkl> /// Return the rank of a permutation.
fcn computeRank(perm){
N,p2,inv := perm.len(), perm.copy(), List.createLong(N,0);
foreach n in (N){ inv[perm[n]] = n; }
fcn(n,p2,inv){
if(n<2) return(0);
i,s:= n-1, p2[i];
p2.swap(i,inv[i]);
inv.swap(s,i);
s + n*self.fcn(i,p2,inv);
}(N,p2,inv);
}</lang>
<lang zkl> // do some random permutations of 4
fcn factorial(n){ (1).reduce(n,'*) }
items,max:=(4).toList(),factorial(items.len()); // (0,1,2,3), read only
foreach rank in ((5).pump(List,(0).random.fp(max)).sort()){
p:=computePermutation(items.copy(),rank);
println("%3d: %s = %d".fmt(rank, p, computeRank(p)));
}
println();
// Permutations of 12 to compare to other solutions
items:=(12).toList(); // (0,1,2,3,..11)
foreach rank in (T(340494881,469128647,460982459,432900481)){
p:=computePermutation(items.copy(),rank);
println("%12d: %s = %d".fmt(rank,p,computeRank(p)));
}</lang>
{{out}}
<pre>
16: L(3,2,1,0) = 16
16: L(3,2,1,0) = 16
16: L(3,2,1,0) = 16
17: L(0,2,3,1) = 17
23: L(0,1,2,3) = 23
340494881: L(4,2,3,9,0,8,10,11,1,6,7,5) = 340494881
469128647: L(7,6,10,5,2,3,1,0,8,4,9,11) = 469128647
460982459: L(4,9,5,7,0,8,6,10,2,1,3,11) = 460982459
432900481: L(0,6,5,10,8,2,4,7,3,9,11,1) = 432900481
</pre>
===Addressing the extra credit===
computePermutation works fine with BigInts but there is no current way to generate a random number in range to 250!
If a 63 bit range was OK, then (but don't hold your breath, this takes a while):
<lang zkl>var [const] BN=Import("zklBigNum"); // libGMP
one44Bang:=BN(144).factorial(); // 250 digits
// Needed: random number [0,one44Bang)
do(0d1_000_000){
p:=computePermutation((144).toList().copy(),(0).random((0).MAX));
}</lang>
and the TCL idea of shuffles (List.shuffle()) makes more sense.
| |||