random permutation with Fisher-Yates shuffle

[Minh Van Nguyen]

A C implementation of the Fisher-Yates shuffle. This algorithm is also known as the Knuth shuffle and is used for producing random permutations of sequences. The algorithm has a theoretical runtime of O(n), where n is the length of the input sequence.

The attached patch is a pre-requisite for further patches on game theory on graphs that I'm working on, in particular the following ticket:

https://bugs.launchpad.net/igraph/+bug/779369

Some game update procedures require that in case multiple candidates can be chosen for update, we need to choose one such candidate at random. The Fisher-Yates shuffle can be used to randomize the order in which candidates are to be updated. See the following blog post for a statistical analysis of the C implementation contained in the patch:

http://mvngu.wordpress.com/2011/05/08/statistical-analysis-of-the-fisher-yates-shuffle/

[Gábor Csárdi (gabor.csardi)]

Added in revision #2441, after slight changes, mostly cosmetics.

RNG_BEGIN/RNG_END is not part of the igraph API, the user is not supposed to call it. The RNG_INTEGER(), etc. macros are also internal, they will be moved to an internal header file, at some point.

[Gábor Csárdi (gabor.csardi)]

Minh, another comment, for future code. Please put variable declarations at the beginning of the function body, some older compilers need this. Thanks.

[Tamás Nepusz (ntamas)]

Not necessarily at the beginning; putting them at the beginning of for blocks is usually also fine.
MSVC is especially picky about this; gcc-based compilers usually do not care and accept variable declarations at all places inside the function body.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/429