wypełnianie tablicy losową liczbą

Question

Próbuję wypełnić tablicę z 20 ints liczbami od 1-20 w losowej kolejności. oto mój kod:

int lookup[20]={0}; 
int array[20]={0}; 
srand(time(NULL)); 
for(int i=0;i<20;++i){ 
    bool done=false; 
    while(!done){ 
     int n=rand()%20; 
     if(lookup[n]==0){ 
      array[i]=n; 
      lookup[n]=1; 
      done=true; 
     } 
    } 
} 

Utworzyłem tablicę przeglądową, aby sprawdzić, czy liczba losowa nie jest jeszcze wybrany i przechowywać je w tablicy. Jak widzisz, stworzyłem 2 pętle, jedną do przechodzenia przez tablicę i chwilę do wyboru losowej liczby. W każdej iteracji pętli liczba może się ponownie pojawić i spowodować kolejną pętlę while. Czy jest szybszy sposób to zrobić?

Answer 1

Możesz wypełnić tablicę w sekwencji, a następnie potasować ją. To uniemożliwiłoby kiedykolwiek zrobienie więcej niż 20 generowanych liczb losowych.

Fisher-Yates shuffle: można zrobić w czasie O (n).

z Wikipedii:

Prawidłowo wdrożone, Fisher-Yates shuffle jest bezstronna, tak że każda permutacja jest równie prawdopodobne. Nowoczesna wersja algorytmu jest również dość wydajna, wymagająca tylko czasu proporcjonalnego do liczby przetasowanych elementów i braku dodatkowej przestrzeni dyskowej.

Answer 2

Położyłbym 20 liczb losowych w tablicy, a następnie skopiuj do innej tablicy 20 elementów, posortuj jedną tablicę, a dla każdej liczby w posortowanej tablicy znajdź odpowiednią liczbę w nieposortowanej tablicy i umieść indeks tego rodzaju.

Answer 3

można wypełnić tablicę z numerami od 1 do 20 i używać std::random_shuffle

notatka nie trzeba wektor dla tej materii to prosta tablica zrobi.
przykład:

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main(void) 
{ 
     int array[] = { 0, 1, 2, 3, 4 }; 

     srand(unsigned(time(NULL))); 

     random_shuffle(array, array+5); 

     for(int i=0; i<5; i++) 
       cout << array[i] << endl; 

     return 0; 
} 

Answer 4

Istnieje możliwość w kodzie bardzo długiej pętli biegu. Jeśli jesteś w pętli while (! Done), nie ma gwarancji, że kiedykolwiek dokończysz. Oczywiście w zestawie 20 elementów nie będzie to w praktyce problem, ale może spowodować problemy, jeśli skaluje się to do wielu tysięcy elementów.

Bardziej niezawodnym rozwiązaniem byłoby sekwencyjne wypełnianie tablicy, a następnie potasowanie jej później.

Answer 5

Spójrz na std::random_shuffle i std::vector.

Answer 6

Jeśli można użyć pojemników, to bym po prostu wypełnić std :: set z numerami od 1 do 20.

Wtedy można wyciągnąć liczbę losową z odbiornika i włóż go do tablicy.

Answer 7

coś takiego?

int n = 20; //total element of array 
int random = 0, temp=0, start=1; 

for(int i=0; i < n; ++i,++start) 
{ 
    array[i] = start; 
} 

for(int i=0; i<n ; ++i) 
{ 
    random=rand()%(n-i)+i; 
    //swapping, you can make it as a function 
    temp = array[i]; 
    array[i] = array [random]; 
    array[random] = temp; 

} 

Answer 8

Inny możliwy sposób

int array[20]={0}; 
int values[20]; 
for(int i = 0; i < 20; i++) 
    values[i] = i; 
int left = 20; 
for(int i = 0; i < 20; i++) 
{ 
    int n = rand() % left; 
    array[i] = values[n]; 
    left--; 
    values[n] = values[left]; 
} 

PS wypełnione nombers od 0 do 19, a nie od 1 do 20.Taka sama jak oryginalna

Answer 9

przykład Kodeks Fisher-Yates:

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

void shuffle(int array[], size_t size) 
{ 
    if(size) while(--size) 
    { 
     size_t current = (size_t)(rand()/(1.0 + RAND_MAX) * (size + 1)); 
     int tmp = array[current]; 
     array[current] = array[size]; 
     array[size] = tmp; 
    } 
} 

int main(void) 
{ 
    srand((int)time(NULL)); 
    rand(); // throw away first value: necessary for some implementations 

    int array[] = { 1, 2, 3, 4, 5 }; 
    shuffle(array, sizeof array/sizeof *array); 

    size_t i = 0; 
    for(; i < sizeof array/sizeof *array; ++i) 
     printf("%i\n", array[i]); 

    return 0; 
} 

Answer 10

Mam nadzieję, że to pomoże:

std::generate(array, array + sizeof(array)/sizeof(int), ::rand); 

Poniżej masz pełny kod:

#include<algorithm> 
#include<cstdlib> 
#include<iostream> 
#include<iterator> 

int main() 
{ 
    int array[] = {1, 2, 3, 4}; 
    const unsigned SIZE = sizeof(array)/sizeof(int); 

    cout << "Array before: "; 
    std::copy(array, array+SIZE, std::ostream_iterator<int>(cout, ", ")); 

    std::generate(array, array+SIZE, ::rand); // answer for your question 

    cout << "\nArray arter: "; 
    std::copy(array, array+SIZE, std::ostream_iterator<int>(cout, ", ")); 
} 

jeśli chcesz mieć mniejszą liczbę niż można to zrobić po wygenerowaniu:

std::transform(array, array+SIZE, array, std::bind2nd(std::modulus<int>(), 255));