suelto - Mezcla aleatoria en C

remojar arroz toda la noche

Question

Estoy buscando una función en ANSI C que aleatorice una matriz al igual que lo hace PHP shuffle() . ¿Existe tal función o tengo que escribirla por mi cuenta? Y si tengo que escribirlo solo, ¿cuál es la mejor forma de hacerlo?

Mis ideas hasta ahora

• Itere a través de la matriz por, digamos, 100 veces e intercambie un índice aleatorio con otro índice aleatorio
• Cree una nueva matriz y llénela con índices aleatorios a partir del primero que verifique cada vez si el índice ya está tomado (rendimiento = 0 complejidad = serio)

Answer 1

Aquí hay una solución que utiliza memcpy en lugar de asignación, por lo que puede usarla para una matriz en lugar de datos arbitrarios. Necesita el doble de memoria de la matriz original y el costo es O (n) lineal:

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 2

El siguiente código garantiza que la matriz se baraje basándose en una semilla aleatoria tomada del tiempo de usec. También esto implementa la en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle correctamente. Probé la salida de esta función y se ve bien (incluso la expectativa de que cualquier elemento de la matriz sea el primer elemento después de la reproducción aleatoria, e incluso la expectativa de ser el último).

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 3

Me limitaré a hacerme eco de la respuesta de Neil Butterworth y señalar algunos problemas con tu primera idea:

Sugeriste,

Itere a través de la matriz por, digamos, 100 veces e intercambie un índice aleatorio con otro índice aleatorio

Haz esto riguroso randn(int n) la existencia de randn(int n) , un envoltorio alrededor de algunos RNG, produciendo números distribuidos uniformemente en [0, n -1], y swap(int a[], size_t i, size_t j) ,

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

que intercambia a[i] y a[j] . Ahora implementemos su sugerencia:

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
}

Tenga en cuenta que esto no es mejor que esta versión más simple (pero aún incorrecta):

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

Bueno, ¿qué pasa? Considere cuántas permutaciones le dan estas funciones: con n (o 2 × n para silly_shuffle ) selecciones aleatorias en [0, n -1], el código "bastante" seleccionará una de las n ² (o 2 × n ²) formas de baraja la baraja. ¡El problema es que hay n ! = n × ( n -1) × ⋯ × 2 × 1 arreglos posibles de la matriz, y ni n ² ni 2 × n ² es un múltiplo de n !, lo que demuestra que algunas permutaciones son más probables que otras.

El barajado de Fisher-Yates es en realidad equivalente a su segunda sugerencia, solo con algunas optimizaciones que cambian (rendimiento = 0, complejidad = serio) a (rendimiento = muy bueno, complejidad = bastante simple). (En realidad, no estoy seguro de que exista una versión correcta más rápida o más simple).

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: Ver también codinghorror.com/blog/2007/12/the-danger-of-naivete.html .

Answer 4

No hay una función en el estándar C para aleatorizar una matriz.

• Mira a Knuth, tiene algoritmos para el trabajo.
• O mira Bentley - Perlas de programación o más perlas de programación.
• O busca en casi cualquier libro de algoritmos.

Garantizar un cambio justo (donde cada permutación del orden original es igualmente probable) es simple, pero no trivial.

Answer 5

No lo vi entre las respuestas, por lo que propongo esta solución si puede ayudar a cualquiera:

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;
    }
}

Answer 6

Pegado del enlace de a benpfaff.org/writings/clc/shuffle.html , por su persistencia:

#include <stdlib.h>

/* Arrange the N elements of ARRAY in random order.
   Only effective if N is much smaller than RAND_MAX;
   if this may not be the case, use a better random
   number generator. */
void shuffle(int *array, size_t n)
{
    if (n > 1) 
    {
        size_t i;
        for (i = 0; i < n - 1; i++) 
        {
          size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
        }
    }
}

EDITAR : Y aquí hay una versión genérica que funciona para cualquier tipo ( int , struct , ...) a través de memcpy . Con un programa de ejemplo para ejecutar, requiere VLA, no todos los compiladores lo admiten por lo que es posible que desee cambiarlo a malloc (que funcionará mal) o un búfer estático lo suficientemente grande como para acomodar cualquier tipo que le arroje:

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

/* compile and run with
 * cc shuffle.c -o shuffle && ./shuffle */

#define NELEMS(x)  (sizeof(x) / sizeof(x[0]))

/* arrange the N elements of ARRAY in random order.
 * Only effective if N is much smaller than RAND_MAX;
 * if this may not be the case, use a better random
 * number generator. */
static void shuffle(void *array, size_t n, size_t size) {
    char tmp[size];
    char *arr = array;
    size_t stride = size * sizeof(char);

    if (n > 1) {
        size_t i;
        for (i = 0; i < n - 1; ++i) {
            size_t rnd = (size_t) rand();
            size_t j = i + rnd / (RAND_MAX / (n - i) + 1);

            memcpy(tmp, arr + j * stride, size);
            memcpy(arr + j * stride, arr + i * stride, size);
            memcpy(arr + i * stride, tmp, size);
        }
    }
}

#define print_type(count, stmt) /
    do { /
    printf("["); /
    for (size_t i = 0; i < (count); ++i) { /
        stmt; /
    } /
    printf("]/n"); /
    } while (0)

struct cmplex {
    int foo;
    double bar;
};

int main() {
    srand(time(NULL));

    int intarr[] = { 1, -5, 7, 3, 20, 2 };

    print_type(NELEMS(intarr), printf("%d,", intarr[i]));
    shuffle(intarr, NELEMS(intarr), sizeof(intarr[0]));
    print_type(NELEMS(intarr), printf("%d,", intarr[i]));

    struct cmplex cmparr[] = {
        { 1, 3.14 },
        { 5, 7.12 },
        { 9, 8.94 },
        { 20, 1.84 }
    };

    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));
    shuffle(cmparr, NELEMS(cmparr), sizeof(cmparr[0]));
    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));

    return 0;
}