Does anyone have suggestions for a smart random number algorithm.
Something that will generate random numbers within a range until all the
numbers in the range have been used.

It would be just like a CD shuffle program, where the CD player plays the
songs in random order.

So far I have an array of 1s and 0s that indicates which number has been
selected.  If the number has already been selected then the random()
generation is repeated.  The problem here is that if the range is large,
the closer you get to selection of all the numbers the longer it will
take to get the missing numbers.

thanks
Felipe

==============================================================================
Felipe R B Jordao                                 fjordao@eniac.seas.upenn.edu
MEAM                                                      fjordao@industry.com
University of Pennsylvania                       73133.436@compuserve.com
                                http://www.seas.upenn.edu/~fjordao/felipe.html
==============================================================================

Felipe R B Jordao (fjordao@blue.seas.upenn.edu) wrote:

: Does anyone have suggestions for a smart random number algorithm.
: Something that will generate random numbers within a range until all the
: numbers in the range have been used.

The way most programmers handle this is to fill an array with
all of the values, and then randomly shuffle the array.
This is the best shuffler that I have ever seen:
(does anyone know of any better ones?)

for(int i = 0; i < numElems; i++) {
    int r = rand() % (i+1);
    table[i] = table[r];
    table[r] = i;
}

Does anyone know of any better shuffler algorithms (don't
comment on the quality of the random number generator, as
I use my own).

-- Joshua Allen

In article <3p91p7$ne@netnews.upenn.edu>, fjordao@blue.seas.upenn.edu
(Felipe R B Jordao) wrote:

: Does anyone have suggestions for a smart random number algorithm.
: Something that will generate random numbers within a range until all the
: numbers in the range have been used.
:
: It would be just like a CD shuffle program, where the CD player plays the
: songs in random order.
:
: So far I have an array of 1s and 0s that indicates which number has been
: selected.  If the number has already been selected then the random()
: generation is repeated.  The problem here is that if the range is large,
: the closer you get to selection of all the numbers the longer it will
: take to get the missing numbers.

Several posters suggested the most general solution of shuffling arrays.
The only problem with this approach is that it doesn't scale well to
extremely large ranges.  For an interesting algorithm that uses a feedback
function to achieve a similar effect with negligible storage requirements,
you might be interested in an article entitled "A Digital Dissolve Effect"
by Mike Morton from Graphics Gems 1.

Robert Coie                              rac@intrigue.com
Implementor, Intrigue Corporation     AppleLink: INTRIGUE

In <3p91p7$ne@netnews.upenn.edu>, fjordao@blue.seas.upenn.edu (Felipe R B Jordao) writes:
>
>Does anyone have suggestions for a smart random number algorithm.
>Something that will generate random numbers within a range until all the
>numbers in the range have been used.

  This does NOT belong in comp.std.c++. I will reply by email.

In article <3p91p7$ne@netnews.upenn.edu>, fjordao@blue.seas.upenn.edu (Felipe R B Jordao) writes:
|>
|> Does anyone have suggestions for a smart random number algorithm.
|> Something that will generate random numbers within a range until all the
|> numbers in the range have been used.
|>
|> It would be just like a CD shuffle program, where the CD player plays the
|> songs in random order.
|>
|> So far I have an array of 1s and 0s that indicates which number has been
|> selected.  If the number has already been selected then the random()
|> generation is repeated.  The problem here is that if the range is large,
|> the closer you get to selection of all the numbers the longer it will
|> take to get the missing numbers.


// (1) Fill in an array of indices

for(int i=0; i<Range; i++) { Indices[i] = i; }


// (2) Shuffle that array of indices. To do it, swap each consecutive
//     element with the random one from the rest of the array

for(i=0; i<Range; i++) {
     // int random(int n) should return a value in range 0,...,n-1
 swap( &Indices[i], &Indices[ i+random(Range-i) ] );
}

// Done. To produce a new sequence, just reshuffle (repeat (2)).


--
Dima
{ Warning: the following appendum is a Cauchi random variable }

My haircut is totally traditional!

In article <3p91p7$ne@netnews.upenn.edu>,
   fjordao@blue.seas.upenn.edu (Felipe R B Jordao) wrote:
>
>Does anyone have suggestions for a smart random number algorithm.
>Something that will generate random numbers within a range until all the
>numbers in the range have been used.
>
> [...]
>
>thanks
>Felipe
>

I'd like to add:
If it's not difficult, point to any respectable source (like Knuth),
or post the P-code here in the newsgroup. Much of appreciation.

Victor.

-------< Internet: vbazarov@imsisoft.com, CompuServe: 74633,2430 >

joshua@myhost.subdomain.domain (joshua) wrote:

>Felipe R B Jordao (fjordao@blue.seas.upenn.edu) wrote:

>: Does anyone have suggestions for a smart random number algorithm.
>: Something that will generate random numbers within a range until all the
>: numbers in the range have been used.

>The way most programmers handle this is to fill an array with
>all of the values, and then randomly shuffle the array.

I had once decided on one without a "lengthy" initial shuffle step.
First fill the array with all the values in order and then randomly
remove them.  Like this:

int deck[52];  /* deck of cards */
int highest;            /* top of the deck */

/* Init the deck */
void shuffle(void)
{
    int i;
    for(i = 0; i < 52; i++)
        deck[i] = i;
    highest = 52;
}

int pick(void)
{
    int i, card;

    if(highest == 0)
        return -1;         /* deck is exhausted */

    i = rand() % highest;  /* pick a card from the middle */
    highest--;             /* deck top is reduced */
    card = deck[i];        /* save the card's value */
    deck[i] = deck[highest]; /* Move the top card into */
                             /* the removed card's spot */
    return card;
}

--
Richard Krehbiel, rich@kastle.com

In article <3padvl$rn8@mars.worldlinx.com>, joshua@myhost.subdomain.domain
says...
>
>Felipe R B Jordao (fjordao@blue.seas.upenn.edu) wrote:
>
>: Does anyone have suggestions for a smart random number algorithm.
>: Something that will generate random numbers within a range until all the
>: numbers in the range have been used.
>
>The way most programmers handle this is to fill an array with
>all of the values, and then randomly shuffle the array.
>This is the best shuffler that I have ever seen:
>(does anyone know of any better ones?)
>
>for(int i = 0; i < numElems; i++) {
>    int r = rand() % (i+1);
>    table[i] = table[r];
>    table[r] = i;
>}
>
>Does anyone know of any better shuffler algorithms (don't
>comment on the quality of the random number generator, as
>I use my own).

If you want the values one at a time:

j = numElems;
.
.
.
int r = rand() % (j+1);
randomInt = table[r];
table[r] = table[j];
j--;

This 'compacts' the array as you're going along;  you never
see a value you've seen before.
>-- Joshua Allen

In article <bry.800711267@bambam> bry@dasc.nl (Ben van Rijnsoever)
writes:

|> fjordao@blue.seas.upenn.edu (Felipe R B Jordao) writes:


|> >Does anyone have suggestions for a smart random number algorithm.
|> >Something that will generate random numbers within a range until all the
|> >numbers in the range have been used.

|> >It would be just like a CD shuffle program, where the CD player plays the
|> >songs in random order.

|> >So far I have an array of 1s and 0s that indicates which number has been
|> >selected.  If the number has already been selected then the random()
|> >generation is repeated.  The problem here is that if the range is large,
|> >the closer you get to selection of all the numbers the longer it will
|> >take to get the missing numbers.

|> If you want to generate a number between 0 and x, where x is a power of 2,
|> then the algoritm:
|>  j = ( j * c1 + c2) % x
|> gives a list of numbers. When c1 and c2 are carefull choosen prime numbers,
|> the period of this congruential algorithm is x.

It's bad enough people responding to off topic posts, but when the
answer is wrong as well..

Read Knuth, and possibly "Random Number Generators: Good Ones Are Hard
to Find" (in an issue of CACM a couple of years back).  The above is a
very poor random number generator.  It alternates even and odd, for
all odd values of c1 and c2.  (The proof of this statement is left as
an exercise for the reader, but it shouldn't take more than about five
minutes.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                              -- Beratung in industrieller Datenverarbeitung