C Perform of Fisher-Yates Implementation (Random Shuffling Algorithm)

Advertisements

[ad_1]

The next is a random shuffling operate in C. This makes use of the Fisher-Yates algorithm, which ensures an unbiased shuffle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#embody <stdlib.h>
#embody <time.h>
 
void shuffle(int *array, size_t n) {
    if (n > 1) {
        // Seed the random quantity generator to get totally different outcomes every time
        srand(time(NULL));
 
        size_t i;
        for (i = 0; i < n - 1; i++) {
            // Generate a random index
            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
 
            // Swap array[i] and array[j]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}
 
#embody <stdlib.h>
#embody <time.h>

void shuffle(int *array, size_t n) {
    if (n > 1) {
        // Seed the random quantity generator to get totally different outcomes every time
        srand(time(NULL));

        size_t i;
        for (i = 0; i < n - 1; i++) {
            // Generate a random index
            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

            // Swap array[i] and array[j]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

This operate operates in-place (it adjustments the enter array as an alternative of returning a brand new one). The srand(time(NULL)) line is used to seed the random quantity generator primarily based on the present time, to be sure to get totally different shuffles every time you run this system. It’s usually a good suggestion to name this simply as soon as, quite than each time you shuffle.

The rand() / (RAND_MAX / (n – i) + 1) line is a strategy to get a random integer between 0 and n – i inclusive. The + 1 is there to ensure that RAND_MAX is a legitimate output from rand(), which wouldn’t be the case if we simply did rand() / (RAND_MAX / (n – i)).

Lastly, we use a easy swap operation to trade the i-th and j-th parts of the array.

Fisher-Yates Algorithms

–EOF (The Final Computing & Expertise Weblog) —

GD Star Ranking
loading…


415 phrases
Final Publish: Is Azure Cli Command Synchronous or Asynchronous?
Subsequent Publish: C Implementation of the iota Perform (Growing Sequence)



[ad_2]