Permutations/Rank of a permutation: Difference between revisions

{{trans|Nim}}

F nonrandom()

:seed = 1664525 * :seed + 1013904223

V r = Int(nonrandom() * factorial(12))

getPermutation(&tv12, r)

{{out}}

=== C: Myrvold and Ruskey ===

This is algorithm #1 from the M&R paper.

#include <stdlib.h>

}

}

{{out}}

{{trans|C}}

Currently this doesn't use BigInts.

alias TRank = ulong;

writefln("%20d: %s = %d", rank, items2, items2.computeRank);

}

{{out}}

<pre> 0: [1, 2, 3, 0] = 0

=={{header|FreeBASIC}}==

===Up to 20 objects===

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Rank: unrank1 rank1

===Using GMP for the big numbers===

{{libheader|GMP}}

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>862993243747395020367391904490190117106585269146708404403331561502140758428008657463653366643611155380240799622282374456087743515643868809722278635878978733132591027133490410275442362000562723356064257191755491520940533177124123076535632269113257248

=={{header|Go}}==

import (

fmt.Println(r, MRPerm(r, n))

}

{{out}}

<pre>

=={{header|Haskell}}==

Without the random part.

fact n = product [1 .. n]

f n = print (n, p, permRank p)

where

{{out}}

from rank to permutation back to rank:

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

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...

=={{header|Java}}==

'''Code:'''

import java.util.*;

}

{{out}}

'''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.

| reduce range(2; $n) as $i ($n; . * $i);

'''The Tasks'''

# The input should be a permutation of 0 ... $n-1 inclusive

def mrUnrank1($rank; $n):

task(4),

"",

{{out}}

<pre>

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

println(" ", p, " (", prank, ")")

end

{{out}}

=={{header|Kotlin}}==

{{trans|C}}

import java.util.Random

System.out.printf("%9d -> %s -> %d\n", r, tv.contentToString(), getRank(12, tv))

}

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{trans|Haskell}}

fromrank[list_, n_] :=

Prepend[fromrank[DeleteCases[list, #],

Do[Print@fromrank[Range[0, 12 - 1], RandomInteger[12!]], {4}];

{{Out}}

<pre>{0,{0,1,2,3},0}

=={{header|Nim}}==

{{trans|Kotlin}}

if n < 1: return

let q = rank div n

for r in newSeqWith(4, rand(fac(12))):

tv12.getPermutation(r)

{{out}}

=={{header|PARI/GP}}==

The functions are built into GP already: <code>numtoperm</code> and <code>permtonum</code>

vector(4,i,numtoperm(12,random(12!)))

{{out}}

<pre>%1 = 1

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;

print " Four 4-object random permutations of 100k objects using randperm\n";

print join(" ", randperm(100000,4)),"\n" for 1..4;

{{out}}

=={{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>

<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>

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

test1('First ordering:', unranker1, ranker1)

test1('Second ordering:', unranker2, ranker2)

{{out}}

Permutations with small differences in rank are likely to be "similar" in appearance (if rank difference << perm length).

from typing import List

rank = tj_rank(p)

parity = tj_parity(p)

{{out}}

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

pi1[s], pi1[i] = pi1[i], pi1[s]

result += s * fact(i)

=={{header|Racket}}==

Mimicking the Haskell style.

#lang racket (require math)

(define-syntax def (make-rename-transformer #'match-define-values))

(* (for/sum ([x xs] #:when (< x x0)) 1)

(factorial (length xs))))]))

{{out}}

<pre>

It is easy generate random inversion vector without BigInt.

sub rank2inv ( $rank, $n = * ) {

.say

};

{{out}}

<pre>

Since this REXX program generates permutations without recursive calls,

testing for the limit for a &nbsp; ''stack overflow'' &nbsp; 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.*/

end /*p*/

parse value @.p @.q with @.q @.p

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ring}}==

# Project : Permutations/Rank of a permutation

last = last - 1

end

Output:

<pre>

=={{header|Ruby}}==

include Enumerable

attr_reader :num_elements, :size

n.zero? ? 1 : n.downto(1).inject(:*)

end

Demo:

perm = Permutation.new(3)

(0...perm.size).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}

p prm = perm.unrank(r)

p perm.rank(prm) == r

{{out}}

<pre style="overflow:auto">

=={{header|Scala}}==

def factorial(n: Int): BigInt = {

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)

} else {

println("Failed")

{{out}}

=={{header|Tcl}}==

{{trans|D}}

proc swap {v idx1 idx2} {

lset v $idx2 [lindex $v $idx1][lset v $idx1 [lindex $v $idx2];subst ""]

}}

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}]

puts [format "%20lld: \[%s\] = %lld" \

$rank [join $items2 ", "] [computeRank $items2]]

{{out}}

<pre style="overflow:auto">

</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} {

}

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.)

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

getPermutation.call(r, 12, tv)

Fmt.print("$9d -> $n -> $d", r, tv, getRank.call(12, tv))

{{out}}

=={{header|zkl}}==

{{trans|D}}

foreach n in ([items.len()..1,-1]){

r:=rank%n;

}

items

fcn computeRank(perm){

N,p2,inv := perm.len(), perm.copy(), List.createLong(N,0);

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

p:=computePermutation(items.copy(),rank);

println("%12d: %s = %d".fmt(rank,p,computeRank(p)));

{{out}}

<pre>

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.