webentwicklung-frage-antwort-db.com.de

Shuffle Array in C

Ich bin auf der Suche nach einer Funktion in ANSI C, die ein Array wie auch shuffle() von PHP randomisiert. Gibt es eine solche Funktion oder muss ich sie selbst schreiben? Und wenn ich es selbst schreiben muss, was ist der beste/performanteste Weg, dies zu tun? 

Meine bisherigen Ideen:

  • Zum Beispiel 100 mal durch das Array iterieren und einen Zufallsindex mit einem anderen Zufallsindex austauschen
  • Erstellen Sie ein neues Array und füllen Sie es mit zufälligen Indizes aus dem ersten, und prüfen Sie jedes Mal, ob der Index bereits belegt ist (Leistung = 0 Komplexität = ernsthaft).
35
Asmodiel

Eingefügt aus Asmodiel 's link zu Ben Pfaffs Schriften , zur Beharrlichkeit:

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

EDIT: Und hier ist eine generische Version, die für jeden Typ (int, struct, ...) bis memcpy geeignet ist. Bei einem auszuführenden Beispielprogramm sind VLAs erforderlich. Nicht jeder Compiler unterstützt dies. Daher möchten Sie möglicherweise malloc (was schlecht funktioniert) oder einen statischen Puffer ändern, der groß genug ist, um jeden Typ zu berücksichtigen, den Sie darauf werfen.

#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;
}
36
John Leehey

Der folgende Code stellt sicher, dass das Array basierend auf einem zufälligen Startwert aus der Usec-Zeit gemischt wird. Auch hiermit wird der Fisher-Yates-Shuffle korrekt implementiert. Ich habe die Ausgabe dieser Funktion getestet und sie sieht gut aus (sogar die Erwartung, dass ein Arrayelement das erste Element nach dem Mischen ist. Auch die Erwartung, das letzte zu sein).

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

Im C-Standard gibt es keine Funktion, um ein Array zufällig zu sortieren.

  • Schauen Sie sich Knuth an - er hat Algorithmen für den Job.
  • Oder schauen Sie sich Bentley - Programmierperlen oder Weitere Programmierperlen an.
  • Oder schauen Sie in fast jedem Algorithmus-Buch nach.

Die Gewährleistung eines fairen Shuffles (bei dem jede Permutation der ursprünglichen Reihenfolge gleichermaßen wahrscheinlich ist) ist einfach, aber nicht trivial.

6

Hier ist eine Lösung, die memcpy anstelle von Zuweisung verwendet. Sie können also Array für beliebige Daten verwenden. Sie benötigen den doppelten Speicherplatz des ursprünglichen Arrays und die Kosten sind 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++] ) );
}
4
Hyperboreus

Ich werde Neil Butterworth's Antwort nur wiederholen und auf einige Probleme mit Ihrer ersten Idee hinweisen:

Du schlugst vor, 

Zum Beispiel 100 mal durch das Array iterieren und einen Zufallsindex mit einem anderen Zufallsindex austauschen

Mache das rigoros. Ich gehe davon aus, dass es sich um randn(int n) handelt, einen Wrapper um ein RNG, der Zahlen erzeugt, die gleichmäßig in [0, n -1] und swap(int a[], size_t i, size_t j) verteilt sind.

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

welche a[i] und a[j]..__ tauscht. Lassen Sie uns nun Ihren Vorschlag implementieren:

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
}

Beachten Sie, dass dies nicht besser ist als diese einfachere (aber immer noch falsche) Version:

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

Nun, was ist los? Bedenken Sie, wie viele Permutationen Ihnen diese Funktionen geben: Mit n (oder 2 × n für silly_shuffle) zufälligen Auswahlen in [0, n -1] wird der Code "ziemlich" ausgewählt von n ² (oder 2 × n ²) Möglichkeiten, das Deck zu mischen. Das Problem ist, dass es n gibt! = n × (n -1) × ⋯ × 2 × 1 mögliche Anordnungen des Arrays, und weder n ² noch 2 × n ² ist ein Vielfaches von n !, was beweist, dass einige Permutationen wahrscheinlicher sind als andere.

Der Fisher-Yates-Shuffle entspricht eigentlich deinem zweiten Vorschlag, nur mit einigen Optimierungen, die sich ändern (Leistung = 0, Komplexität = ernsthaft) in (Leistung = sehr gut, Komplexität = ziemlich einfach). (Eigentlich bin ich nicht sicher, ob es eine schnellere oder einfachere korrekte Version gibt.)

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: Siehe auch diesen Beitrag zu Coding Horror .

3
J. C. Salomon

Ich habe es unter den Antworten nicht gesehen, also schlage ich diese Lösung vor, wenn es jemandem helfen kann:

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;
    }
}
0
Antonin GAVREL