generating random unique numbers

[Giorgos Keramidas]

On Mon, 26 Oct 2009 03:02:58 +0200, Christos Bacharakis <cmpahar at gmail.com> wrote:
> Κώστα, το θέμα όμως είναι ότι θέλω μοναδικούς αριθμούς, όχι απλά
> τυχαίους!

Τότε εκτός από μια γεννήτρια χρειάζεται και έλεγχο αν το αποτέλεσμα που
πήρες το έχεις ξαναδεί.  Αν είναι λίγοι αριθμοί (π.χ. κάτω από μερικές
δεκάδες), μπορείς απλά να τους κρατάς σε ένα array, π.χ.:

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

    #ifndef MAXNUM
    #define MAXNUM  10
    #endif

    int
    main(void)
    {
            int vec[MAXNUM];
            int vlen, k;
            int value, valnew;

            srand(time(0) + getpid());
            for (vlen = 0; vlen < MAXNUM; vlen++) {
                    valnew = 0;
                    while (valnew == 0) {
                            value = rand();
                            valnew = 1;
                            for (k = 0; k < vlen; k++)
                                    if (vec[k] == value)
                                            valnew = 0;
                    }
                    vec[vlen] = value;
            }
            for (k = 0; k < vlen; k++)
                    printf("%d\n", vec[k]);
            return EXIT_SUCCESS;
    }

Δεν έβαλα κάποιο range limit στις «τυχαίες» τιμές, αλλά κάτι τέτοιο
θέλεις αν κατάλαβα καλά:

    keramida at kobe:/home/keramida$ cc bachar.c
    keramida at kobe:/home/keramida$ ./a.out | sort -n | uniq -c
       1 128600753
       1 149849101
       1 511229364
       1 645924256
       1 706317930
       1 869921758
       1 1024306789
       1 1295288371
       1 1663006223
       1 1943332541
    keramida at kobe:/home/keramida$

Ακόμα και για 10000 unique random αριθμούς ο χρόνος που χρειάζεται η
«απλή» λύση με το iteration & check σε κάθε νέο αποτέλεσμα της rand(),
τρέχει κατά μέσο όρο σε λιγότερο από 0.3 sec:

    keramida at kobe:/home/keramida$ for run in $(jot 20 1 20) ; do \
        time ./a.out > /dev/null ; \
    done
            0.572 real      0.537 user      0.008 sys
            0.244 real      0.237 user      0.001 sys
            0.219 real      0.212 user      0.000 sys
            0.216 real      0.212 user      0.000 sys
            0.226 real      0.217 user      0.000 sys
            0.223 real      0.211 user      0.000 sys
            0.225 real      0.210 user      0.000 sys
            0.223 real      0.208 user      0.003 sys
            0.219 real      0.210 user      0.002 sys
            0.216 real      0.211 user      0.003 sys
            0.223 real      0.211 user      0.002 sys
            0.224 real      0.214 user      0.000 sys
            0.219 real      0.203 user      0.007 sys
            0.225 real      0.214 user      0.000 sys
            0.216 real      0.202 user      0.009 sys
            0.224 real      0.214 user      0.000 sys
            0.225 real      0.211 user      0.000 sys
            0.225 real      0.205 user      0.009 sys
            0.226 real      0.209 user      0.004 sys
            0.216 real      0.214 user      0.000 sys
    keramida at kobe:/home/keramida$

Οπότε, παρόλο που δεν είναι ακριβώς "optimized" αλγόριθμος, ίσως να μην
αξίζει καν να ασχοληθείς με πιο περίπλοκα τρικ (π.χ. με hash table).