Permutations/Rank of a permutation: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 60:
{{trans|Nim}}
<
F nonrandom()
:seed = 1664525 * :seed + 1013904223
Line 106:
V r = Int(nonrandom() * factorial(12))
getPermutation(&tv12, r)
print(‘#9 -> #. -> #.’.format(r, tv12, getRank(tv12)))</
{{out}}
Line 151:
=== C: Myrvold and Ruskey ===
This is algorithm #1 from the M&R paper.
<
#include <stdlib.h>
Line 219:
}
}
</syntaxhighlight>
{{out}}
Line 251:
{{trans|C}}
Currently this doesn't use BigInts.
<
alias TRank = ulong;
Line 313:
writefln("%20d: %s = %d", rank, items2, items2.computeRank);
}
}</
{{out}}
<pre> 0: [1, 2, 3, 0] = 0
Line 348:
=={{header|FreeBASIC}}==
===Up to 20 objects===
<
' compile with: fbc -s console
Line 497:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Rank: unrank1 rank1
Line 532:
===Using GMP for the big numbers===
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 648:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>862993243747395020367391904490190117106585269146708404403331561502140758428008657463653366643611155380240799622282374456087743515643868809722278635878978733132591027133490410275442362000562723356064257191755491520940533177124123076535632269113257248
Line 669:
=={{header|Go}}==
<
import (
Line 750:
fmt.Println(r, MRPerm(r, n))
}
}</
{{out}}
<pre>
Line 769:
=={{header|Haskell}}==
Without the random part.
<
fact n = product [1 .. n]
Line 788:
f n = print (n, p, permRank p)
where
p = rankPerm [0 .. 3] n</
{{out}}
from rank to permutation back to rank:
Line 821:
The J primitive <code>A.</code> provides an effective solution to this task. Generating 4 random permutations of 144 items takes about 6 milliseconds so solving the Stack Overflow question ought to take about 100 minutes on that particular test machine.
<
4
4 A. i.3 NB. return permutation of rank 4
Line 845:
111 65 136 58 92 46 4 83 20 54 21 10 72 110 56 28 13 18 73 133 105 117 63 126 114 43 5 80 45 88 86 108 11 29 0 129 71 141 59 53 113 137 2 102 95 15 35 74 107 61 134 36 32 19 106 100 55 69 76 142 64 49 9 30 47 123 12 97 42...
64 76 139 122 37 127 57 143 32 108 46 17 126 9 51 59 1 74 23 89 42 124 132 19 93 137 70 86 14 112 83 91 63 39 73 18 90 120 53 103 140 87 43 55 131 40 142 102 107 111 80 65 61 34 66 75 88 92 13 138 50 117 97 20 44 7 56 94 41...
139 87 98 118 125 65 35 112 10 43 85 66 58 131 36 30 50 11 136 130 71 100 79 142 40 69 101 84 143 33 95 26 18 94 13 68 8 0 47 70 129 48 107 64 93 16 83 39 29 81 6 105 78 92 104 60 15 55 4 14 7 91 86 12 31 46 20 133 53...</
=={{header|Java}}==
Line 855:
'''Code:'''
<
import java.util.*;
Line 926:
}
}</
{{out}}
Line 954:
'''Preliminaries'''
<
# if the input and $j are integers, then the result will be a pair of integers,
# except that if $j is 0, then an error condition is raised.
Line 972:
| reduce range(2; $n) as $i ($n; . * $i);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;</
'''The Tasks'''
<
# The input should be a permutation of 0 ... $n-1 inclusive
def mrUnrank1($rank; $n):
Line 1,026:
task(4),
"",
task3</
{{out}}
<pre>
Line 1,078:
Unfortunately, as of the 0.3 release of Julian, this code can not be used to address the StackOverflow question. Although many of Julia's permutation built-in functions support large permutations, <tt>nthperm(p)</tt> is limited to partitions of no more than 20 objects. <tt>p = randperm(114)</tt> works fine, but <tt>nthperm(p)</tt> throws an <tt>OverflowError</tt>. Arguably, this is a bug, and it may be rectified in future releases.
<
nobjs = 4
Line 1,105:
println(" ", p, " (", prank, ")")
end
</syntaxhighlight>
{{out}}
Line 1,144:
=={{header|Kotlin}}==
{{trans|C}}
<
import java.util.Random
Line 1,208:
System.out.printf("%9d -> %s -> %d\n", r, tv.contentToString(), getRank(12, tv))
}
}</
{{out}}
Line 1,252:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Haskell}}
<
fromrank[list_, n_] :=
Prepend[fromrank[DeleteCases[list, #],
Line 1,265:
Do[Print@fromrank[Range[0, 12 - 1], RandomInteger[12!]], {4}];
Do[Print@fromrank[Range[0, 144 - 1], RandomInteger[144!]], {4}];</
{{Out}}
<pre>{0,{0,1,2,3},0}
Line 1,302:
=={{header|Nim}}==
{{trans|Kotlin}}
<
if n < 1: return
let q = rank div n
Line 1,349:
for r in newSeqWith(4, rand(fac(12))):
tv12.getPermutation(r)
echo &"{r:>9} → {tv12} → {tv12.getRank()}"</
{{out}}
Line 1,391:
=={{header|PARI/GP}}==
The functions are built into GP already: <code>numtoperm</code> and <code>permtonum</code>
<
vector(4,i,numtoperm(12,random(12!)))
for(i=1,1e6,numtoperm(144,random(144!)))</
{{out}}
<pre>%1 = 1
Line 1,401:
The ntheory module gives us <code>numtoperm</code> and <code>permtonum</code> commands similar to Pari/GP, though in the preferred lexicographic order. Values larger than the native int size are handled as well. The <code>randperm</code> function is useful for random permutations, using a Knuth shuffle and a Chacha/20 CSPRNG supplying randomness. A Macbook takes a bit under 4 seconds to generate 1 million random permutations of 144 objects, or 8 seconds if inserting into a set to ensure uniqueness.
{{libheader|ntheory}}
<
my $n = 3;
Line 1,421:
print " Four 4-object random permutations of 100k objects using randperm\n";
print join(" ", randperm(100000,4)),"\n" for 1..4;
</syntaxhighlight>
{{out}}
Line 1,454:
=={{header|Phix}}==
{{trans|C}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_rank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
Line 1,486:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 1,515:
Their algorithm is efficient and pythons transparent use of arbitrary precision integers allows the Stack Overflow questions limits to be used. (Chopped at four rather than a million random samples although function get_random_ranks(144, 1e6) doesn't take long).
<
from random import randrange
from textwrap import wrap
Line 1,600:
test1('First ordering:', unranker1, ranker1)
test1('Second ordering:', unranker2, ranker2)
test2('First ordering, large number of perms:', unranker1)</
{{out}}
Line 1,674:
Permutations with small differences in rank are likely to be "similar" in appearance (if rank difference << perm length).
<
from typing import List
Line 1,777:
rank = tj_rank(p)
parity = tj_parity(p)
print(f" Rank: {r:10} to perm: {p}, parity: {parity} to rank: {rank:10}")</
{{out}}
Line 1,803:
Functions ranker1 and ranker2 above, can be changed from the recursive form as used in the paper to iterative versions if they are replaced with the following code that yields the same results:
<
if n == 1:
return 0
Line 1,819:
pi1[s], pi1[i] = pi1[i], pi1[s]
result += s * fact(i)
return result</
=={{header|Racket}}==
Mimicking the Haskell style.
<
#lang racket (require math)
(define-syntax def (make-rename-transformer #'match-define-values))
Line 1,839:
(* (for/sum ([x xs] #:when (< x x0)) 1)
(factorial (length xs))))]))
</syntaxhighlight>
{{out}}
<pre>
Line 1,878:
It is easy generate random inversion vector without BigInt.
<syntaxhighlight lang="raku"
sub rank2inv ( $rank, $n = * ) {
Line 1,927:
.say
};
</syntaxhighlight>
{{out}}
<pre>
Line 1,960:
Since this REXX program generates permutations without recursive calls,
testing for the limit for a ''stack overflow'' wouldn't be necessary using this REXX program.
<
parse arg N y seed . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 4 /*Not specified? Then use the default.*/
Line 1,997:
end /*p*/
parse value @.p @.q with @.q @.p
return 1</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,029:
=={{header|Ring}}==
<
# Project : Permutations/Rank of a permutation
Line 2,071:
last = last - 1
end
</syntaxhighlight>
Output:
<pre>
Line 2,101:
=={{header|Ruby}}==
<
include Enumerable
attr_reader :num_elements, :size
Line 2,138:
n.zero? ? 1 : n.downto(1).inject(:*)
end
end</
Demo:
<
perm = Permutation.new(3)
(0...perm.size).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}
Line 2,159:
p prm = perm.unrank(r)
p perm.rank(prm) == r
end</
{{out}}
<pre style="overflow:auto">
Line 2,193:
=={{header|Scala}}==
<
def factorial(n: Int): BigInt = {
Line 2,215:
case Nil => BigInt(0)
case x :: rest => factorial(rest.size) * rest.count(ord.lt(_, x)) + permutationToIndex(rest)
}</
<
val perm = indexToPermutation(n, x)
val xOut = permutationToIndex(perm)
Line 2,227:
} else {
println("Failed")
}</
{{out}}
Line 2,241:
=={{header|Tcl}}==
{{trans|D}}
<
proc swap {v idx1 idx2} {
lset v $idx2 [lindex $v $idx1][lset v $idx1 [lindex $v $idx2];subst ""]
Line 2,274:
}}
return [apply $mrRank1 $mrRank1 [llength $vec] $vec $inv]
}</
Demonstrating:
<
for {set result 1; set i 2} {$i <= $n} {incr i} {
set result [expr {$result * $i}]
Line 2,299:
puts [format "%20lld: \[%s\] = %lld" \
$rank [join $items2 ", "] [computeRank $items2]]
}</
{{out}}
<pre style="overflow:auto">
Line 2,333:
</pre>
The above code is not a particularly good use of a random number generator; the Tcl PRNG does not generate enough bits of true randomness per call to <code>rand()</code> for it to be useful in such a simplistic approach. However, it will do for the purposes of demonstration. A more sophisticated RNG is this one:
<
set bits [expr {ceil(log($limit)/log(2))+10}]
for {set b [set r 0]} {$b < $bits} {incr b 16} {
Line 2,339:
}
return [expr {$r % $limit}]
}</
===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.)
Line 2,346:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 2,408:
getPermutation.call(r, 12, tv)
Fmt.print("$9d -> $n -> $d", r, tv, getRank.call(12, tv))
}</
{{out}}
Line 2,452:
=={{header|zkl}}==
{{trans|D}}
<
foreach n in ([items.len()..1,-1]){
r:=rank%n;
Line 2,459:
}
items
}</
<
fcn computeRank(perm){
N,p2,inv := perm.len(), perm.copy(), List.createLong(N,0);
Line 2,471:
s + n*self.fcn(i,p2,inv);
}(N,p2,inv);
}</
<
fcn factorial(n){ (1).reduce(n,'*) }
items,max:=(4).toList(),factorial(items.len()); // (0,1,2,3), read only
Line 2,486:
p:=computePermutation(items.copy(),rank);
println("%12d: %s = %d".fmt(rank,p,computeRank(p)));
}</
{{out}}
<pre>
Line 2,503:
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):
<
one44Bang:=BN(144).factorial(); // 250 digits
// Needed: random number [0,one44Bang)
do(0d1_000_000){
p:=computePermutation((144).toList().copy(),(0).random((0).MAX));
}</
and the TCL idea of shuffles (List.shuffle()) makes more sense.
|