Jak utworzyć losową permutację tablicy?

Question

Napisałem tę funkcję w C i chcę, aby stworzyła losową permutację lub listę liczb od 1 do n. Mam problem z tym, żeby nie mieć powtarzających się numerów. Więc jeśli masz n = 4, chciałbym go do powrotu losową tablicę zawierającą 1-4 każdą tylko raz, na przykład: {1,3,4,2}

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    // initial range of numbers 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    // shuffle 
    for (int i = 1; i <= n; ++i){ 
     int j = rand() % i; 
     r[i] = r[j]; 
     r[j] = i; 
    } 
    return r; 
} 

Answer 1

Zmień swoją drugą pętlę for :

for (int i = n-1; i >= 0; --i){ 
    //generate a random number [0, n-1] 
    int j = rand() % (i+1); 

    //swap the last element with element at random index 
    int temp = r[i]; 
    r[i] = r[j]; 
    r[j] = temp; 
} 

To jest algorytm tasowania Fisher-Yates. Słyszałem, że używanie rand() % n nie rozpowszechnia się równomiernie, zostałeś ostrzeżony.

A jeśli chcesz generować unikatowe permutacje za każdym razem, możesz przechowywać wygenerowane permutacje, być może w Dictionary lub Hashmap, a następnie wyszukiwać za każdym razem, gdy wrócisz. Nie sądzę, że C ma wbudowany, ale powinny być dostępne biblioteki.

Answer 2

To może nie być najbardziej efektywny sposób, ale ponieważ już zapełniłeś tablicę na początku, możesz po prostu przeglądać elementy i dla każdego z nich wybrać losowy indeks z zakresu od 1 do n i zamień z tym elementem:

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    for(int i=0; i<n; ++i){ 
     int randIdx = rand() % n; 
     // swap r[i] with r[randIdx] 
     int t = r[i]; 
     r[i] = r[randIdx]; 
     r[randIdx] = t; 
    } 
    return r; 
} 

Nie wiem, czy jest to najbardziej efektywny, a nawet najlepszy rozkład. Ale to całkiem proste :-)