Shuffle array in C

Question

I'm looking for a function in ANSI C that would randomize an array just like PHP's shuffle() does. Is there such a function or do I have to write it on my own? And if I have to write it on my own, what's the best/most performant way to do it?

My ideas so far:

• Iterate through the array for, say, 100 times and exchange a random index with another random index
• Create a new array and fill it with random indices from the first one checking each time if the index is already taken (performance = 0 complexity = serious)

Answer 1

The following code ensures that the array will be shuffled based on a random seed taken from the usec time. Also this implements the Fisher–Yates shuffle properly. I've tested the output of this function and it looks good (even expectation of any array element being the first element after shuffle. Also even expectation for being the last).

void shuffle(int *array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);


    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}

Answer 2

There isn't a function in the C standard to randomize an array.

• Look at Knuth - he has algorithms for the job.
• Or look at Bentley - Programming Pearls or More Programming Pearls.
• Or look in almost any algorithms book.

Ensuring a fair shuffle (where every permutation of the original order is equally likely) is simple, but not trivial.

Answer 3

The function you are looking for is already present in the standard C library. Its name is qsort. Random sorting can be implemented as:

int rand_comparison(const void *a, const void *b)
{
    (void)a; (void)b;

    return rand() % 2 ? +1 : -1;
}

void shuffle(void *base, size_t nmemb, size_t size)
{
    qsort(base, nmemb, size, rand_comparison);
}

The example:

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

srand(0); /* each permutation has its number here */

shuffle(arr, 10, sizeof(int));

...and the output is:

3, 4, 1, 0, 2, 7, 6, 9, 8, 5

Answer 4

I’ll just echo Neil Butterworth’s answer, and point out some trouble with your first idea:

You suggested,

Iterate through the array for, say, 100 times and exchange a random index with another random index

Make this rigorous. I'll assume the existence of randn(int n), a wrapper around some RNG, producing numbers evenly distributed in [0, n-1], and swap(int a[], size_t i, size_t j),

void swap(int a[], size_t i, size_t j) {
  int temp = a[i]; a[i] = a[j]; a[j] = temp;
}

which swaps a[i] and a[j]. Now let’s implement your suggestion:

void silly_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, randn(n), randn(n)); // swap two random elements
}

Notice that this is not any better than this simpler (but still wrong) version:

void bad_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, randn(n));
}

Well, what’s wrong? Consider how many permutations these functions give you: With n (or 2×_n_ for silly_shuffle) random selections in [0, n-1], the code will “fairly” select one of _n_² (or 2×_n_²) ways to shuffle the deck. The trouble is that there are n! = _n_×(n-1)×?×2×1 possible arrangements of the array, and neither _n_² nor 2×_n_² is a multiple of n!, proving that some permutations are more likely than others.

The Fisher-Yates shuffle is actually equivalent to your second suggestion, only with some optimizations that change (performance = 0, complexity = serious) to (performance = very good, complexity = pretty simple). (Actually, I’m not sure that a faster or simpler correct version exists.)

void fisher_yates_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, i+randn(n-1-i)); // swap element with random later element
}

ETA: See also this post on Coding Horror.

Answer 5

Here a solution that uses memcpy instead of assignment, so you can use it for array over arbitrary data. You need twice the memory of original array and the cost is linear O(n):

void main ()
{
    int elesize = sizeof (int);
    int i;
    int r;
    int src [20];
    int tgt [20];

    for (i = 0; i < 20; src [i] = i++);

    srand ( (unsigned int) time (0) );

    for (i = 20; i > 0; i --)
    {
        r = rand () % i;
        memcpy (&tgt [20 - i], &src [r], elesize);
        memcpy (&src [r], &src [i - 1], elesize);
    }
    for (i = 0; i < 20; printf ("%d ", tgt [i++] ) );
}

Answer 6

Assuming you may want to just access an array randomly instead of actually shuffling it, you can use the degenerative case of a linear congruential pseudo-random number generator

X_n+1 = (a Xn+c) mod N
where a is coprime to N
generates a random cycle over all values 0:N

Naturally you could store this sequence in an empty array.

uint32_t gcd ( uint32_t a, uint32_t b )
{
  if ( a==0 ) return b;
  return gcd ( b%a, a );
}

 uint32_t get_coprime(uint32_t N){  
     uint32_t min_val = 2;  
     for(int i =0;i<N*40;i++){  
         uint64_t sel = min_val + ( rand()%(r-min_val ));  
         if(gcd(sel,r)==1)  
             return sel;  
     }  
     return 0;  
}

uint32_t next_val(uint32_t coprime, uint32_t cur)
{     
   return cur+coprime;   
}

Answer 7

The same answer like Nomadiq but the Random is kept simple. The Random will be the same if you call the function one after another:

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

void shuffle(int aArray[], int cnt){
    int temp, randomNumber;
    time_t t;
    srand((unsigned)time(&t));
    for (int i=cnt-1; i>0; i--) {
        temp = aArray[i];
        randomNumber = (rand() % (i+1));
        aArray[i] = aArray[randomNumber];
        aArray[randomNumber] = temp;
    }
}

Answer 8

I saw the answers and I've discovered an easy way to do it

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

int main(void){

    int base[8] = {1,2,3,4,5,6,7,8}, shuffled[8] = {0,0,0,0,0,0,0,0};
    int index, sorted, discart=0;

    srand(time(NULL));
    for(index = 0; index<8; index++){
        discart = 0;
        while(discart==0){
            sorted = rand() % 8;
            
            if (shuffled[sorted] == 0){
                //This here is just for control of what is happening
                printf("-------------\n");
                printf("index: %i\n sorted: %i \n", index,sorted);
                printf("-------------\n");

                shuffled[sorted] = base[index];
                discart= 1;
            }
        }
    }

    //This "for" is just to exibe the sequence of items inside your array
    for(index=0;index<8; index++){
        printf("\n----\n");
        printf("%i", shuffled[index]);
    }

    return 0;
}

Notice that this method doesn't allow duplicated items. And at the end you can use either numbers and letters, just replacing them into the string.

Answer 9

This function will shuffle array based on random seed:

void shuffle(int *arr, int size)
{
    srand(time(NULL));

    for (int i = size - 1; i > 0; i--)
    {
        int j = rand() % (i + 1);

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

Answer 10

I didn't see it among answers so I propose this solution if it can help anybody:

static inline void shuffle(size_t n, int arr[])
{
    size_t      rng;
    size_t      i;
    int         tmp[n];
    int         tmp2[n];

   memcpy(tmp, arr, sizeof(int) * n);
    bzero(tmp2, sizeof(int) * n);
    srand(time(NULL));
    i = 0;
    while (i < n)
    {
        rng = rand() % (n - i);
        while (tmp2[rng] == 1)
            ++rng;
        tmp2[rng] = 1;
        arr[i] = tmp[rng];
        ++i;
    }
}