Shuffle generic array in C

Question

I have an array of pointer to a struct.

I tried to use the first answer of this question to try to solve this problem, but I got a seg fault:

Shuffle array in C

After try this code, I tryed to use this function to do the shuffling:

static void shuffle(void *array, size_t n, size_t size) {
    void * aux;
    aux = malloc (size);

    if (n > 1) {
        size_t i;
        for (i = 0; i < n - 1; ++i) {

            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

            memcpy(aux, array[j], size);
            memcpy(array[j], array[i], size);
            memcpy(array[i], aux, size);
        }
    }
}

But i got the following error:

warning: dereferencing 'void *' pointer [enable by default]
error: invalid use of void expression

I got this warning and error 3 times: one for each memcpy().

EDIT

I changed the code because I was trying to use this new one instead the old one.

Answer 1

In addition to @Deduplicator good advice, need to scale the j offset by size.

This code also changes the j calculation. I do not think what you have will work well.

#include <stdlib.h>
static void shuffle(void *array, size_t n, size_t size) {
  // This if() is not needed functionally, but left per OP's style
  if (n > 1) {
    char *carray = array;
    void * aux;
    aux = malloc(size);
    size_t i;
    for (i = 1; i < n; ++i) {
      size_t j = rand() % (i + 1); 
      j *= size;
      memcpy(aux, &carray[j], size);
      memcpy(&carray[j], &carray[i*size], size);
      memcpy(&carray[i*size], aux, size);
    }
    free(aux);
  }
}

---

Clarify the weakness of size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

Substituting rand() with the values 0 to RAND_MAX in the formula will generate a sample distribution. Example (i=0, n=30265, RAND_MAX=2147483647) generates the values j = 0 to 30263, 70957 times each and j = 30264= 41000. This is a bad case and likely not the worst case.

Using size_t j = i + r%(n-i); generates a nearly uniform result.

Example (i=0, n=30265, RAND_MAX=2147483647) generates the values j = 0 to 307, 70957 times each and j = 308 to 30264= 70956 times. Methods exist to compensate for this small bias. Many SO postings.

Note: Inherit weaknesses in a poor rand() are not fixed by either of these methods, but method selection can make things noticeably worse when trying to use a sub-range of 0 to RAND_MAX

[Edit]

Holes appear with size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

Somewhere about n > sqrt(RAND_MAX) and i=0, values near n will not be generated. Example: (i=0, n=104643, RAND_MAX=2147483647) does not generate values 104638 to 104642.

Answer 2

Vou cannot dereference a void* nor do arithmetic on it in C, because it is literally "pointer to object of unknown type", so the compiler has no idea what to do (Some compilers allow arithmetic as an extension as if it was char*, but don't rely on it).

Thus:

Cast your void* to char* and do it with them instead. Don't forget to do your own scaling for the pointer arithmetic.
Also, memcpy should get a pointer, not the object pointed to, so use +, not [].
Aside: Please avoid memory leaks, free any memory you allocated.
Finally, be aware that random() might have both a tiny range and bad statistic properties.
Finally+1: chux answer dissects the range-mapping used in this case, showing how badly it was done.

How to Debug Small Programs
C99 with Technical corrigenda TC1, TC2, and TC3 included

Answer 3

1. Make sure, that you're actually compiling this as C code (C and C++ differ in type conversion)
2. Pass pointers to elements in an array instead of dereferencing them: array[i] -> &array[i]
3. sizeof(void) is not guaranteed to be defined, use char
4. Add some assertions to check parameters for memcpy(). One may use modulo to clamp i and j, although this mostly won't result in good random number distribution either.

static void shuffle(char *array, size_t n, size_t size)
{
    char* aux;
    aux = malloc(size);

    if (n > 1)
    {
        size_t i;
        for (i = 0; i < n - 1; ++i)
        {

            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

            assert(j + size <= ???);
            assert(i + size <= ???);

            memcpy(aux, &array[j], size);
            memcpy(&array[j], &array[i], size);
            memcpy(&array[i], aux, size);
        }
    }
}

Answer 4

Here's another option:

void shuffle(void *arr, size_t n, size_t size) {
  char *tmp;
  char *array;
  int i, r;
  array = (char *)arr;
  tmp = (char *)malloc(size);
  for (i = n-1; i >= 0; --i) {
    r = rand() % (i+1);
    // swap 
    memcpy(tmp, &array[size*r], size);
    memcpy(&array[size*r], &array[size*i], size);
    memcpy(&array[size*i], tmp, size);
  }
  free(tmp);
}

The simplest so far. Note there is no need to check for n=1.

If you really want to use size_t then modify the code a bit:

void shuffle(void *arr, size_t n, size_t size) {
  char *tmp;
  char *array;
  size_t i, r;
  array = (char *)arr;
  tmp = (char *)malloc(size);
  for (i = n-1; i+1 > 0; --i) {
    r = rand() % (i+1);
    // swap 
    memcpy(tmp, &array[size*r], size);
    memcpy(&array[size*r], &array[size*i], size);
    memcpy(&array[size*i], tmp, size);
  }
  free(tmp);
}

Thanks to commenters for pointing out issues with using int. (It is probably obvious the above code works --- that is returns permutation of the array uniformly at random, i.e., returns each permutation of the array with probability 1/n!. It is nontheless a fun exercise to prove this.)