Pseudo-random permutation using 128 bit seed

Question

I'm looking for a couple of functions that permute the index of a vector in an efficient way by seeding with 128-bit key. Optimization is critical for me since i'm doing the same operation multiple times.

Can anyone suggest a C/C++ open-source library in which 128 bit seeding is available and it supports a function like permute(seed, range(min,max),sample_size)?

For example; if permute(1, [0,10], 10) function gives the result as: 3 6 7 2 4 9 8 1 0 5, then permute(1, [0,10], 5) should give 3 6 7 2 4.

min, max and sample_size parameters are dynamic variables. It changes at each iteration.

This sounds unlikely to find it... Your best option might be to write it yourself. — Antzi, Aug 03 '16 at 07:13
What do you do with the result vector? If you need performance you might be able to eliminate it altogether. — sh1, Aug 04 '16 at 07:01
Actually, i'm using an c++ open source library named as PCG Random Number Generator. It allows to use 128 bit PRNG, but does not support a permutation function like shuffle. — metlira, Aug 04 '16 at 07:30

score 2 · Answer 1 · answered Aug 03 '16 at 08:06

2

You may use Fisher–Yates_shuffle:

// Fisher–Yates_shuffle
std::vector<int>
FisherYatesShuffle(std::size_t size, std::size_t max_size, std::mt19937& gen)
{
    assert(size < max_size);
    std::vector<int> res(size);

    for (std::size_t i = 0; i != max_size; ++i) {
        std::uniform_int_distribution<> dis(0, i);
        std::size_t j = dis(gen);
        if (j < res.size()) {
            if (i < res.size()) {
                res[i] = res[j];
            }
            res[j] = i;
        }
    }
    return res;
}

Live example

answered Aug 03 '16 at 08:06

Jarod42

203,559
14
181
302

whats with the scope-operator hell? You **do** know that there is a keyword called `using`, right? – specializt Aug 03 '16 at 08:27
@specializt: Have you look at [why-is-using-namespace-std-in-c-considered-bad-practice](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-in-c-considered-bad-practice) ? – Jarod42 Aug 03 '16 at 08:39
solution : http://stackoverflow.com/a/1455227/351861 and **especially** : http://stackoverflow.com/a/26722134/351861 – specializt Aug 03 '16 at 10:48
that's a new shuffling method. thanks for sharing. but my constraint is to use a 128 bit key for PRNG. – metlira Aug 04 '16 at 07:29

score 1 · Answer 2 · answered Aug 03 '16 at 08:06

1

No need for a library (so it actually is on-topic!)

std::shuffle gives you the permutation; it takes a UniformRandomBitGenerator such as std::mt19937. std::mt19937::seed() takes a sequence, so you can feed it 128 bits of initial state. And taking a subrange is of course trivial.

answered Aug 03 '16 at 08:06

MSalters

173,980
10
155
350

one of the solution is exactly like this. but the problem is seeding PRNG with 128 bit key. as far as i know mt19937 uses 32 bit key and mt19937_64 uses 64 bit key. – metlira Aug 04 '16 at 07:27
@metlira: No, as I said `seed()` takes a sequence. IIRC, there's more than **500** bytes of state. – MSalters Aug 04 '16 at 08:19

Pseudo-random permutation using 128 bit seed

2 Answers2