Today, a user by the name of Nanashiiiima asked in the SuShCodingYT Discord channel:

Does anybody know how to assign every value in a randomized array to a unique integer? In my case, I’m trying to assign the 3 variables in my array with one of three values (I don’t want any of them to be the same).

This is a pretty common problem, especially in video games. One example where this might be useful, both in and out of video games, is to play all of the songs in a playlist in a random order while ensuring the listener hears every song exactly once. This is known as “shuffle” and the algorithm described below is indeed how many old school MP3 players implemented the “shuffle” button.

Fisher-Yates Shuffle algorithm

Please note, this shuffle algorithm has a number of variations; some of which are generically labeled under the same name. See the “Additional Reading” section at the end of this post. I will be demonstrating the range bias-free, O(n) “modern algorithm”. This implementation is also an in-place shuffle. That is, it modifies the original array rather than making a copy. You could easily modify this code to make a copy if you prefer to keep the original array immutable.

First, let’s shuffle a simple array of contiguous integer values. This is a good test case because it’s easy to visually verify that it’s working correctly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEMENT_COUNT 8

int main(int argc, char *argv[])
{
    srand((unsigned int)time(0));  // TODO: Better seed if it matters
    int arr[ELEMENT_COUNT] = { 0, 1, 2, 3, 4, 5, 6, 7 };

    // Print array
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Shuffle array
    int tmp, j;
    for (int i = ELEMENT_COUNT - 1; i > 0; --i) {
        j = rand() % (i + 1);
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // Print shuffled array
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

This program prints both the original array and the shuffled array:

1
2

0 1 2 3 4 5 6 7
5 3 1 4 2 7 0 6

Shuffling anything (indexed lookup)

So we can shuffle lists of integers, that’s cool, but what if we wanted to shuffle something else? One idea is we may want to randomly name eight NPCs from a list of preprogrammed names. We obviously don’t want two NPCs to end up with the same name, that would be confusing! Another idea is a tasty treat chooser. Choosing which treat to grab from the fridge is always tough, so for this example we’ll be shuffling an array of tasty treats.

One way to do this would be to use the shuffled array of numbers we generated above as lookup indices into the treats array. This would us to shuffle many times without modifying the original array.

Here is an example of this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEMENT_COUNT 8

int main(int argc, char *argv[])
{
    srand((unsigned int)time(0));  // TODO: Better seed if it matters

    int index[ELEMENT_COUNT] = { 0, 1, 2, 3, 4, 5, 6, 7 };

    // Print index
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%d ", index[i]);
    }
    printf("\n");

    // Shuffle index
    int tmp, j;
    for (int i = ELEMENT_COUNT - 1; i > 0; --i) {
        j = rand() % (i + 1);
        tmp = index[i];
        index[i] = index[j];
        index[j] = tmp;
    }

    // Print shuffled index
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%d ", index[i]);
    }
    printf("\n");

    // Print shuffled treats
    const char *treats[ELEMENT_COUNT] = {
        "apricot", "banana", "coconut", "durian",
        "elderberry", "fructose", "grape", "honeydew"
    };
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%s ", treats[index[i]]);
    }

    return 0;
}

The output if this program is very similiar, except that we now have a shuffle array of tasty treats!

1
2
3

0 1 2 3 4 5 6 7
7 0 1 4 5 6 3 2
honeydew apricot banana elderberry fructose grape durian coconut

Shuffling anything (in-place)

While there are times when the solution given above for shuffling tasty treat names is useful, there are other times when you may be asking “Why do I need this intermediate array of indices? Why can’t I just shuffle the strings themselves?” and of course the answer is: You can! In this last example, I will show you how you can use this method to shuffle arbitrary data in-place.

This is the same algorithm as above, which runs in O(n), but you should consider the cost of the copies for the numerous swaps that have to occur in order to shuffle an array in-place. For an integer (above) or a string pointer (below), the cost is trivial, but for a more complex data types and larger arrays, the cost of performing O(n) copies to and from the “tmp” variable to perform the swaps may become more noticeable or even prohibitive. This is unlikely for most reasonable use-cases, but good to keep in mind.

Alright, so now let’s do an in-place swap of tasty treats!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEMENT_COUNT 8

int main(int argc, char *argv[])
{
    srand((unsigned int)time(0));  // TODO: Better seed if it matters

    const char *treats[ELEMENT_COUNT] = {
        "apricot", "banana", "coconut", "durian",
        "elderberry", "fructose", "grape", "honeydew"
    };

    // Print treats
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%s ", treats[i]);
    }
    printf("\n");

    // Shuffle treats
    const char *tmp;
    int j;
    for (int i = ELEMENT_COUNT - 1; i > 0; --i) {
        j = rand() % (i + 1);
        tmp = treats[i];
        treats[i] = treats[j];
        treats[j] = tmp;
    }

    // Print shuffled treats
    for (int i = 0; i < ELEMENT_COUNT; ++i) {
        printf("%s ", treats[i]);
    }
    printf("\n");

    return 0;
}

This program outputs a shuffled array of tasty treats:

1
2

apricot banana coconut durian elderberry fructose grape honeydew
coconut grape durian banana elderberry honeydew fructose apricot

Additional reading

The Fisher-Yates Shuffle Wikipedia article has a great overview of the history of this algorithm. It also dives deeper into common mistakes and possible sources of bias. The algorithm I’ve described above is the one described as the “modern algorithm” in the Wiki article. Assuming I’ve implemented it correctly, this variation elimnates shuffle bias due to range errors, but does not attempt to eliminate modulo bias or PRNG (pseudo-random number generator, i.e. rand()) bias. Read the Wiki article for more information on these topics.

Closing remarks

The Fisher-Yates Shuffle is a fast and efficient way to randomly shuffle a collection while ensuring no additional duplication or repetition, aside from any that is already in the original list. Hopefully this post has you thinking of new and creative ways to add variation to your game, or any other software project!

Happy coding!

If you’d like to check out the SuShCodingYT Discord server, you can join it via this link:
https://discordapp.com/invite/xtthkcF

This Discord server is the community hub for Suraj Sharma’s YouTube channel, which you can find here:
https://www.youtube.com/channel/UC2i39AOpDSlO1Mrn1jQ8Xkg