generating random unique numbers

[Giorgos Keramidas]

On Mon, 26 Oct 2009 02:17:29 +0200, Christos Bacharakis <cmpahar at gmail.com> wrote:
> Καλησπέρα!
>
> Θα ήθελα την προγραμματιστική βοήθεια σας.
>
> Θέλω να δημιουργήσω 7 τυχαίους αριθμούς οι οποίοι θα έχουν τιμές από 1
> έως 7. Ο λόγος που θέλω να το κάνω αυτό είναι για να αλλάζει σε κάθε
> εκτέλεση η σειρά των αριθμών. Η γλώσσα που υλοποιώ το πρόγραμμα είναι
> C++.
>
> Μια δικιά μου προσέγγιση η οποία όμως σε κάθε εκτέλεση μου βγάζει τα
> ίδια αποτελέσματα!!!
>
> for(i=0; i<8; i++){
> pin[i]=i;
> }
>
> for(i=0; i<8; i++){
> j=rand() % 7;
> k=rand() % 7;
> swap(pin[j],pin[k]);
>
> }

Γειά σου Χρήστο,

Αυτό δεν είναι πλήρες πρόγραμμα, οπότε δε μπορώ να ξέρω αν καλείς την
srand() κάπου αλλού.  Αν δεν το κάνεις όμως, πρόσεξε τι λέει το
manpage του FreeBSD για την rand() -- ιδιαίτερα τα σημεία που έχω
σημειώσει στο αριστερό μέρος:

     The rand() function computes a sequence of pseudo-random integers
     in the range of 0 to RAND_MAX (as defined by the header file
     <stdlib.h>).

     The srand() function sets its argument seed as the seed for a new
     sequence of pseudo-random numbers to be returned by rand().
   | These sequences are repeatable by calling srand() with the same
   | seed value.
   |
   | If no seed value is provided, the functions are automatically
   | seeded with a value of 1.

Αν εσύ δεν καλείς την srand() η pseudo-random γεννήτρια αρχικοποιείται
πάντα με το νούμερο 1.

Επειδή η rand() δεν είναι γεννήτρια «πραγματικά τυχαίων» αριθμών (αυτό
σημαίνει το «pseudo-random» στην περιγραφή της), όταν η γεννήτρια
αρχικοποιείται με το ίδιο seed number παράγει πάντα την ίδια ακριβώς
ακολουθία «τυχαίων» αριθμών.

Η ιδιότητα της γεννήτριας πίσω από το rand() να παράγει την ίδια σειρά
αριθμών είναι χρήσιμη ορισμένες φορές (π.χ. όταν θέλεις να αναπαράγεις
ένα test case με «τυχαίο» input αλλά όχι τόσο τυχαίο που να μη μπορεί
να τρέξει δύο φορές με τον ίδιο ακριβώς τρόπο).

Αλλά αν θέλεις να παράγεις διαφορετικούς αριθμούς σε κάθε τρέξιμο,
ίσως χρειαστεί να δώσεις στην srand() ένα πιο «τυχαίο» seed value,
π.χ. κάτι που παράγεται από άλλη πηγή:

    * Το pid από το πρόγραμμα, την ώρα που έτρεξε, το πόσο γρήγορα
      μπορείς να τρέξεις ένα software loop 1000 φορές, πόσα context
      switches έκανε το kernel τα τελευταία 2 seconds, κλπ.

    * Μπορείς να χρησιμοποιήσεις το /dev/urandom ή το /dev/random για
      να εξάγεις ένα «πιο τυχαίο» seed value και να αρχίσεις μ' αυτό.

Τέλος μπορείς, πάντα, να χρησιμοποιήσεις άλλη γεννήτρια, όπως οι
arc4random() και arc4random_uniform(), να τρέξεις σε pipe την εντολή
`"openssl rand %d", sizeof(unsigned)' και να ταΐσεις την srand() με
αυτή την τιμή, κοκ.

HTH,
Γιώργος