[ create a new paste ] login | about

Link: http://codepad.org/El9SQwOE    [ raw code | fork ]

D, pasted on Feb 5:
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);
}


Create a new paste based on this one


Comments: