Arreglos aleatorios en C

13 minutos de lectura

avatar de usuario
Asmodiel

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

Mis ideas hasta ahora:

  • Iterar a través de la matriz, digamos, 100 veces e intercambiar un índice aleatorio con otro índice aleatorio
  • Cree una nueva matriz y llénela con índices aleatorios desde el primero, verificando cada vez si el índice ya está en uso (rendimiento = 0 complejidad = serio)

  • Tienes que escribir el tuyo, es bastante sencillo. Ver en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle. Como siempre que se trata de números aleatorios, encontrar sus propias soluciones suele ser una mala idea,

    usuario2100815

    25 mayo 2011 a las 16:11


  • OK, no importa, lo encontré >.> benpfaff.org/writings/clc/shuffle.html

    – Asmodiel

    25 de mayo de 2011 a las 16:12

  • Tenga cuidado con el ‘sesgo de módulo’ identificado en la página de Wikipedia: el algoritmo de Ben Pfaff presenta el problema.

    –Jonathan Leffler

    25 mayo 2011 a las 16:41

  • Consulte también stackoverflow.com/questions/859253

    – JC Salomón

    25 de mayo de 2011 a las 19:02

  • Esto muestra cómo barajar una baraja de cartas y cómo no hacerlo: codinghorror.com/blog/2007/12/the-danger-of-naivete.html el código debería ser fácilmente transferible a C

    – nos

    25 mayo 2011 a las 21:02

avatar de usuario
JC Salomón

Me haré eco de la respuesta de Neil Butterworth y señalaré algunos problemas con su primera idea:

Sugeriste,

Iterar a través de la matriz, digamos, 100 veces e intercambiar un índice aleatorio con otro índice aleatorio

Haz esto riguroso. Asumiré la existencia de randn(int n)un envoltorio alrededor de algún RNG, produciendo números distribuidos uniformemente en [0, n-1]y 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;
}

que permuta a[i] y a[j]. Ahora implementemos tu 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? Considera cuántas permutaciones te dan estas funciones: Con norte (o 2×_n_ para silly_shuffle) selecciones aleatorias en [0, n-1], el código seleccionará “justamente” una de _n_² (o 2×_n_²) formas de barajar el mazo. El problema es que hay norte! = _n_×(norte-1)×⋯×2×1 arreglos posibles del arreglo, y ni _n_² ni 2×_n_² son múltiplos de norte!, demostrando que algunas permutaciones son más probables que otras.

La reproducción aleatoria de Fisher-Yates es en realidad equivalente a su segunda sugerencia, solo que 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: Véase también esta publicación en Coding Horror.

avatar de usuario
Juan Leehey

Pegado del enlace de Asmodiel a Los escritos de Ben Pfaffpor 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 admiten esto, por lo que es posible que desee cambiar eso a malloc (que funcionará mal) o un búfer estático lo suficientemente grande como para acomodar cualquier tipo que le arrojes:

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

  • Para evitar la asignación de t con cada iteración, debe intercambiar los dos enteros sin variable temporal: matriz[i] ^= matriz[j]; formación[j] ^= matriz [i]; formación [i] ^= matriz [j];

    – Hiperbóreo

    25 mayo 2011 a las 16:37

  • también podrías hacer array[i] += array[j]; array[j] = array[i] - array[j]; array[i] -= array[j]; si no te preocupas por los desbordamientos de int. Sin embargo, no quiero confundir nada nuevo en el idioma sobre por qué XOR’ing funciona …

    – John Lee Hey

    25 mayo 2011 a las 16:44

  • @Hyperboreus – ¿Estás bromeando? “Asignar” enteros en la pila es tan simple como realizar sumas/restas en un registro. Eso en sí mismo será lo suficientemente rápido, pero además, un optimizador decente solo hará esa suma/resta una vez para este código, no para cada iteración. (Compile esto con la optimización activada y mire el desmontaje usted mismo. Lo hice con gcc -S y había exactamente dos modificaciones del puntero de la pila, una vez al comienzo de la función y una vez al final.) Hay ninguna cosa ahorras teniendo t y j anteriormente en el ámbito de la función.

    – asveikau

    25 de mayo de 2011 a las 16:53


  • Nota: la fórmula i + r / (RAND_MAX / (n - i) + 1) introduce un sesgo adicional. ej. j(i=32,n=61,RM=2147483647) –> { con 2147483648 diferente r, j= 32 a 60 ocurre 74051161 cada uno, 61 ocurre solo 74051140 }. Por determinar el peor de los casos i,n,RAND_MAX. Con i+ rnd%(n-i) { j= 32 a 39 ocurren 74051161 cada uno, j = 40 a 61 ocurre 74051160, la distribución del peor de los casos para varios i,n,RAND_MAX siendo como máximo 1 diferente. Como otras publicaciones se refieren a esta respuesta popular, sentí que era importante tener en cuenta este sesgo.

    – chux – Reincorporar a Monica

    26/04/2014 a las 16:36

  • @PaulStelian: Si RAND_MAX es solo 32767, necesita obtener un mejor PRNG. Un simple paso adelante es el drand48() familia de funciones; ese es un conjunto de funciones estándar POSIX. Es posible que descubras que tienes random() y srandom()o arc4random()o tal vez puedas usar /dev/random o /dev/urandom como fuente de valores aleatorios. Hay muchas posibilidades, pero lo que está preguntando es realmente una pregunta nueva (o debería formularse en una pregunta nueva).

    –Jonathan Leffler

    9 junio 2018 a las 18:15

avatar de usuario
nómada

El siguiente código asegura que la matriz se barajará en función de una semilla aleatoria tomada del tiempo de uso. También esto implementa el Mezcla Fisher-Yates adecuadamente. He probado el resultado 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. También 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;
        }
    }
}

  • usaría un intno size_ten este caso porque n representa el número de enteros, no el tamaño del bloque de memoria. prefiero usar size_t solo para tamaños en bytes.

    – mk12

    6 de noviembre de 2012 a las 18:13

  • @Mk12 El número de elementos y el sizeof una matriz puede ser mucho más que INT_MAX. Utilizando size_t aquí hay un enfoque más robusto y portátil.

    – chux – Reincorporar a Monica

    26 de abril de 2014 a las 16:48

  • Bonito, tan poco código. ¿Es rápido y simple hacer que esto funcione con la biblioteca C de Microsoft?

    – T. Webster

    13 de mayo de 2015 a las 1:00

  • Nota srand() — Por qué solo deberías llamarlo una vez.

    –Jonathan Leffler

    11 de diciembre de 2016 a las 1:05

La función que está buscando ya está presente en la biblioteca C estándar. Su nombre es qsort. La clasificación aleatoria se puede implementar como:

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

El ejemplo:

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

… y la salida es:

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

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

  • Mire a Knuth: tiene algoritmos para el trabajo.
  • O mire Bentley – Perlas de programación o Más perlas de programación.
  • O busque en casi cualquier libro de algoritmos.

Asegurar una mezcla justa (donde cada permutación del orden original sea igualmente probable) es simple, pero no trivial.

  • Realmente igualmente probable es muy difícil. Por ejemplo, su generador de números aleatorios debe tener un múltiplo de N. estados

    usuario97370

    25 mayo 2011 a las 19:14

  • @Paul: Siempre que su envoltorio PRNG “número aleatorio entre 1 y N” sea correcto (distribución uniforme), es fácil. Sin embargo, la gente suele arruinar esto y crear prejuicios.

    – R.. GitHub DEJA DE AYUDAR A ICE

    25 mayo 2011 a las 20:35

  • @Paul Hankin: ¿Es porque necesitas generar números aleatorios a partir de 0 para i donde i viene de n para 1?

    – ninjalj

    25 mayo 2011 a las 20:38

  • @ninjalj: No, absolutamente no. Ese es el ingenuo algoritmo roto que todos usan. Cualquier cosa con punto flotante será un infierno para hacerlo bien, por lo que el primer paso para arreglarlo sería cambiar a números enteros. Luego descarte cualquier resultado mayor que el mayor múltiplo de 10, menos 1 (llame rand de nuevo si obtiene un valor que tiene que descartar). Hay formas de guardar y reutilizar esta entropía en lugar de descartarla por completo, pero eso es más trabajo y probablemente no tenga valor cuando es solo pseudoaleatorio de todos modos.

    – R.. GitHub DEJA DE AYUDAR A ICE

    25 mayo 2011 a las 20:51

  • @R. glibc rand() tiene solo 2 ^ 32 estados diferentes, por lo que puede generar como máximo 2 ^ 32 mezclas diferentes de un paquete de cartas, haga lo que haga. 52! es más como 2^225, por lo que en realidad generas una pequeña fracción de todas las posibilidades.

    usuario97370

    27 de mayo de 2011 a las 19:18

avatar de usuario
Hiperbóreo

Aquí hay una solución que usa memcpy en lugar de asignación, por lo que puede usarla para una matriz sobre datos arbitrarios. Necesita el doble de memoria de la matriz original y el costo es lineal 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++] ) );
}

  • Realmente igualmente probable es muy difícil. Por ejemplo, su generador de números aleatorios debe tener un múltiplo de N. estados

    usuario97370

    25 mayo 2011 a las 19:14

  • @Paul: Siempre que su envoltorio PRNG “número aleatorio entre 1 y N” sea correcto (distribución uniforme), es fácil. Sin embargo, la gente suele arruinar esto y crear prejuicios.

    – R.. GitHub DEJA DE AYUDAR A ICE

    25 mayo 2011 a las 20:35

  • @Paul Hankin: ¿Es porque necesitas generar números aleatorios a partir de 0 para i donde i viene de n para 1?

    – ninjalj

    25 mayo 2011 a las 20:38

  • @ninjalj: No, absolutamente no. Ese es el ingenuo algoritmo roto que todos usan. Cualquier cosa con punto flotante será un infierno para hacerlo bien, por lo que el primer paso para arreglarlo sería cambiar a números enteros. Luego descarte cualquier resultado mayor que el mayor múltiplo de 10, menos 1 (llame rand de nuevo si obtiene un valor que tiene que descartar). Hay formas de guardar y reutilizar esta entropía en lugar de descartarla por completo, pero eso es más trabajo y probablemente no tenga valor cuando es solo pseudoaleatorio de todos modos.

    – R.. GitHub DEJA DE AYUDAR A ICE

    25 mayo 2011 a las 20:51

  • @R. glibc rand() tiene solo 2 ^ 32 estados diferentes, por lo que puede generar como máximo 2 ^ 32 mezclas diferentes de un paquete de cartas, haga lo que haga. 52! es más como 2^225, por lo que en realidad generas una pequeña fracción de todas las posibilidades.

    usuario97370

    27 de mayo de 2011 a las 19:18

avatar de usuario
Antonin GAVREL

No lo vi entre las respuestas, así que propongo esta solución si puede ayudar a alguien:

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

  • Cuando probé este código en una matriz de 20 elementos, el último elemento nunca se intercambió y el penúltimo rara vez se intercambió. Cuando lo probé en una matriz de 10 elementos, el 60 % de las veces el último elemento permaneció sin cambios y el 60 % de las veces el penúltimo elemento permaneció sin cambios. Esto no parece una buena mezcla. (También utiliza una gran cantidad de espacio de almacenamiento adicional, con dos matrices adicionales del mismo tamaño que la matriz que se está mezclando. Eso tampoco es bueno). No debe llamar srand() en la función de reproducción aleatoria: srand() — ¿Por qué llamarlo solo una vez?

    –Jonathan Leffler

    30 de agosto de 2018 a las 6:02

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad