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);
}