Matrice casuale in C

Sto cercando una funzione in ANSI C che possa randomizzare un array come fa il PHP shuffle() . Esiste una tale funzione o devo scriverla da sola? E se devo scriverlo da solo, qual è il modo migliore / più performante per farlo?

Le mie idee finora:

  • Scorrere l’array per, per esempio, 100 volte e scambiare un indice casuale con un altro indice casuale
  • Crea un nuovo array e riempilo con indici casuali dal primo che controlla ogni volta se l’indice è già stato preso (performance = 0 complessità = grave)

Incollato dal legame di Asmodiel con gli scritti di Ben Pfaff , per la persistenza:

 #include  /* 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; } } } 

EDIT : Ed ecco una versione generica che funziona per qualsiasi tipo ( int , struct , ...) attraverso memcpy . Con un programma di esempio da eseguire, richiede VLA, non tutti i compilatori supportano questo, quindi potresti voler cambiarlo in malloc (che funzionerà male) o un buffer statico abbastanza grande da adattarsi a qualsiasi tipo tu passi su di esso:

 #include  #include  #include  #include  /* 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; } 

Il codice seguente garantisce che l’array venga mescolato in base a un seme casuale preso dal momento dell’ora legale. Anche questo implementa correttamente la Fisher-Yates . Ho testato l’output di questa funzione e ha un bell’aspetto (anche l’aspettativa che ogni elemento dell’array sia il primo elemento dopo lo shuffle e anche l’aspettativa di essere l’ultimo).

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

Non c’è una funzione nello standard C per randomizzare un array.

  • Guarda Knuth: ha degli algoritmi per il lavoro.
  • Oppure guarda Bentley – Programming Pearls o More Programming Perle.
  • O guarda in quasi tutti i libri di algoritmi.

Garantire un giusto shuffle (dove ogni permutazione dell’ordine originale è altrettanto probabile) è semplice, ma non banale.

Ecco una soluzione che utilizza memcpy al posto del compito, quindi puoi usarlo per array su dati arbitrari. È necessario il doppio della memoria dell’array originale e il costo è lineare 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++] ) ); } 

Risponderò solo alla risposta di Neil Butterworth e indicherò alcuni problemi con la tua prima idea:

Hai suggerito,

Scorrere l’array per, per esempio, 100 volte e scambiare un indice casuale con un altro indice casuale

Rendi questo rigoroso. randn(int n) l’esistenza di randn(int n) , un wrapper attorno ad alcuni RNG, producendo numeri uniformsmente distribuiti in [0, n -1], e 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; } 

che scambia a[i] e a[j] . Ora implementiamo il tuo suggerimento:

 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 } 

Si noti che questo non è migliore di questa versione più semplice (ma ancora sbagliata):

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

Bene, cosa c'è che non va? Considera quante permutazioni queste funzioni ti danno: Con n (o 2 × n per silly_shuffle ) selezioni casuali in [0, n -1], il codice selezionerà "abbastanza" uno dei modi n ² (o 2 × n ²) per mischia il mazzo. Il problema è che ci sono n ! = n × ( n -1) × ⋯ × 2 × 1 possibili disposizioni dell'array, e né n ² né 2 × n ² è un multiplo di n !, a dimostrazione che alcune permutazioni sono più probabili di altre.

Lo shuffle Fisher-Yates è in realtà equivalente al secondo suggerimento, solo con alcune ottimizzazioni che cambiano (prestazioni = 0, complessità = serie) a (prestazioni = molto buone, complessità = piuttosto semplici). (In realtà, non sono sicuro che esista una versione più veloce o più semplice.)

 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: vedi anche questo post su Coding Horror .

Non l’ho visto tra le risposte quindi propongo questa soluzione se può aiutare qualcuno:

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