codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
import std.stdio, std.random, std.algorithm, std.bigint, std.typecons, std.range; T fact(T=uint)(in uint n) { T result = 1; foreach (x; 1 .. n + 1) result *= x; return result; } int[] identityPerm(in int n) { return iota(n).array(); } int[] unranker1(T)(int n, T r, int[] pi) { while (n > 0) { auto rdivn = r / n; int rmodn = r % n; n--; swap(pi[n], pi[rmodn]); r = rdivn; } return pi; } int[] initPi1(int n, int[] pi) { auto pi1 = new int[n]; pi1[] = -1; foreach (i; 0 .. n) pi1[pi[i]] = i; return pi1; } int ranker1(int n, int[] pi, int[] pi1) { if (n == 1) return 0; auto n1 = n - 1; auto s = pi[n1]; swap(pi[pi1[n1]], pi[n1]); swap(pi1[s], pi1[n1]); return s + n * ranker1(n1, pi, pi1); } int[] unranker2(int n, int r, int[] pi) { while (n > 0) { auto n1 = n - 1; int fn1 = fact(n1); auto s = r / fn1; auto rmodf = r % fn1; swap(pi[n1], pi[s]); n = n1; r = rmodf; } return pi; } int ranker2(int n, int[] pi, int[] pi1) { if (n == 1) return 0; auto n1 = n - 1; auto s = pi[n1]; swap(pi[pi1[n1]], pi[n1]); swap(pi1[s], pi1[n1]); auto fn1 = fact(n1); return s * fn1 + ranker2(n1, pi, pi1); } // Bad code. This has modulus bias and probably more. BigInt uniformBigInt(BigInt sup) in { assert(sup > 0); } body { alias TI = uint; BigInt result; while (result < sup) { result <<= (8 * TI.sizeof); result += uniform!"[]"(cast(TI)0, TI.max); } return result % sup; } T[] getRandomRanks(T=int)(int permSize, int sampleSize) { T perms = fact!T(permSize); bool[T] ranks; while (ranks.length < sampleSize) foreach (r; 0 .. sampleSize - ranks.length) static if (is(T == BigInt)) ranks[uniformBigInt(perms)] = true; else ranks[uniform(T.init, perms)] = true; return ranks.keys; } void test1(F1, F2)(string comment, F1 unranker, F2 ranker) { int n = 3; int sampleSize = 4; int n2 = 12; writeln(comment); Tuple!(int, int[])[] perms; foreach (int r; 0 .. fact(n)) { int[] pi = identityPerm(n); int[] perm = unranker(n, r, pi); perms ~= tuple(r, perm); } foreach (rpi; perms) { auto r = rpi[0]; auto pi = rpi[1]; int[] pi1 = initPi1(n, pi); writefln(" From rank %2d to %s back to %2d", r, pi, ranker(n, pi.dup, pi1)); } writefln("\n %d random individual samples of %d items:", sampleSize, n2); foreach (int r; getRandomRanks(n2, sampleSize)) { int[] pi = identityPerm(n2); writefln(" %(%2d %)", unranker(n2, r, pi)); } writeln(); } void test2(F)(string comment, F unranker) { int sampleSize = 4; int n2 = 144; writeln(comment); writefln(" %d random individual samples of %d items:", sampleSize, n2); foreach (BigInt r; getRandomRanks!BigInt(n2, sampleSize)) { int[] pi = identityPerm(n2); //writeln " " + "\n ".join(wrap(str(unranker(n2, r, pi)))) writeln(unranker(n2, r, pi)); } writeln(); } void main() { rndGen.seed(1); test1("First ordering:", &unranker1!int, &ranker1); test1("Second ordering:", &unranker2, &ranker2); test2("First ordering, large number of perms:", &unranker1!BigInt); }
Private
[
?
]
Run code
Submit