Help with random array selection... Please
Charles LaCour
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int val;
} MyType;
int main( void )
{
MyType x[ 100 ]; /* Remember to initialize your own struct. */
int i, t, index[ 100 ];
/* Initialize the index array */
for ( i = 0; i < 100; ++i )
index[ i ] = i;
/* Scramble the index array */
for ( i = 0; i < 100; ++i )
{
/* Loop until we get a valid number */
do
{
r = rand();
} while ( r < 0 || r > 99 );
/* Swap the two locations. */
t = index[ i ];
index[ i ] = index[ r ];
index[ r ] = t;
}
/* Use the now scrambled index array. */
for ( i = 0; i < 100; ++i )
{
printf( "%d\n", x[ index[ i ] ].val );
}
return 0;
}
The idea is to create an array of indices and then to scramble the indices
in that array. Finally, use the scrambled list of indices as indices into
your array of structures. You could simply swap each element in your array
of structures; however, I have wondered if this method isn't a little faster
on larger structures.
This idea certainly works well, but I'd be more than happy to see other
suggestions.
--
Increase the Peace!
Charles LaCour
cla...@cwix.com
Shane wrote in message <76ctfi$4dc$1...@newsource.ihug.co.nz>...
>Hi there,
>
>I have a problem, I have created an array of structures lets say 0-99 and I
>want to randomly select one of these arrays.
>
>I guess this could be done by rand(99) but the problem is once i have
>executed this and got my answer of say 54 and done my stuff with it.
>
>I then want to be able to random select another struct but not 54 again
>until all other 98 possibilites have been selected. I thought of keeping a
>list of all previously selected numbers but that want work very efficently
>as rand() will eventually start returning a lot of repeat numbers.
>
>Any thoughts on this would be most appreciated...
>
>Thanks
>Shane
>
>
Jos A. Horsmeier
> I have a problem, I have created an array of structures lets say 0-99 and I
> want to randomly select one of these arrays.
>
> I guess this could be done by rand(99) but the problem is once i have
> executed this and got my answer of say 54 and done my stuff with it.
>
> I then want to be able to random select another struct but not 54 again
> until all other 98 possibilites have been selected. I thought of keeping a
> list of all previously selected numbers but that want work very efficently
> as rand() will eventually start returning a lot of repeat numbers.
There's no need to keep a list of indices; how about this approach:
void random_walk( your_struct_t* array, int size) {
int n, i;
your_struct_t temp;
/* for all struct element in the array */
for (n= 0; n < size; n++) {
/* select a random number between 0 and size-n-1 */
i= random(size-n);
do_something_with(arrayi);
/* swap element i and the last unused element size-n-1 */
temp= array[size-n-1];
array[size-n-1]= array[i];
array[i]= temp;
}
kind regards,
Jos aka j...@and.nl
Jeremy Elgar
Then as each one is used (entry 54 for example) let array[54] point to
array[n] and use Random(n) (where Random returns a int in range
(0-(n-1)) ) Decrement n and do again
A simple example using 4 structs
Will select all of the structs in a random order and run the func DoStuff
for each. tryed to keep it as plain as possible so it can be written
better.
int main (void)
{
MyStruct* Array[4] ;
// Init Structs and arrays
Array[0] = new MyStruct (...) ;
Array[1] = new MyStruct (...) ;
Array[2] = new MyStruct (...) ;
Array[3] = new MyStruct (...) ;
for (i=0;i<4;i++)
{
int element ;
element Random(4-i)
DoStuff (Array[element]) ;
Array[element] = Array[4-i] ;
Array[4-i] = 0 ;
}
return 0;
}
I think this soloution is quite nice, but possibly im wrong
Hope this helps
Jeremy
Luis Grave
Jeremy Elgar wrote:
[...]
> int main (void)
> {
> MyStruct* Array[4] ;
> // Init Structs and arrays
c++ comment, not (yet) available in c
> Array[0] = new MyStruct (...) ;
c++ not c
[...]
> for (i=0;i<4;i++)
> {
> int element ;
> element Random(4-i)
add: = ;
> DoStuff (Array[element]) ;
> Array[element] = Array[4-i] ;
> Array[4-i] = 0 ;
with i = 0, Array[4-i] = Array[4] = undefined behavior
change to Array[4-i-1]
> }
> return 0;
> }
>
> I think this soloution is quite nice, but possibly im wrong
yes you are. because this solution don't work and is in c++
>
> Hope this helps
> Jeremy
--
-----------------------------------------------------------
Luis Grave mailto:lgr...@ccg.uc.pt
Dept. Teletrabalho, Visualisacao and Tecnologias Multimedia
Centro de Computacao Grafica http://www.ccg.uc.pt
-----------------------------------------------------------
Jeremy Elgar
The 'new MyStruct (...) was just ment to indicate "Construct your data
here" again sorry for the use of new . (...) ment fill in you aruments
here.
And to be fair Most C imps allow // for comments now
But point take.
Yours 9going home to bed)
Jeremy
Beware of bugs in the above code I have only proved it
correct not tried it.
Jeremy Elgar
Jeremy...@WestGeo.com
Paul Lutus
do
{
r = rand();
} while ( r < 0 || r > 99 );
This is incredibly inefficient. It requires, on average, (99 / MAX_RAND)
tries to acquire a number in range. On a system that uses 32-bit integers
and has a working version of rand(), this means an average run will require
43 million-odd tries before the probability of a number in range rises to
50%.
Something tells me Intel didn't foresee this use of their super-fact
processors, and if this method is used, no one will realize it is fast.
Why not use:
r = rand() % 100;
This works the first time. Some will argue that, because of problems with
the standard random number generator, this will produce numbers that are not
very random. But this assertion can easily be tested to discover whether it
is true on your compiler.
Also, your scrambling method is not guaranteed to move all the numbers --
some numbers and sequences of numbers will remain in their original
locations, while others will be moved multiple times.
Paul Lutus
Charles LaCour wrote in message ...
>>I have a problem, I have created an array of structures lets say 0-99 and
I
>>want to randomly select one of these arrays.
>>
>>I guess this could be done by rand(99) but the problem is once i have
>>executed this and got my answer of say 54 and done my stuff with it.
>>
>>I then want to be able to random select another struct but not 54 again
>>until all other 98 possibilites have been selected. I thought of keeping a
>>list of all previously selected numbers but that want work very efficently
>>as rand() will eventually start returning a lot of repeat numbers.
>>
James Hu
>
>Why not use:
>
>r = rand() % 100;
>This works the first time. Some will argue that, because of problems
>with the standard random number generator, this will produce numbers
>that are not very random. But this assertion can easily be tested to
>discover whether it is true on your compiler.
The C-faq contains an excellent answer
r = (rand() / (1.0 + RAND_MAX)) * 100;
which will always be well-behaved so long as rand() is well-behaved. If
floating point arithmetic is truly problematical, I could suggest
r = rand () / (RAND_MAX/100 + 1);
--
James C. Hu <j...@cs.wustl.edu> Computer Science Doctoral Candidate
http://www.cs.wustl.edu/~jxh/ Washington University in Saint Louis
>>>>>>>>>>>>> I use *SpamBeGone* <URL:http://www.internz.com/SpamBeGone/>
Charles LaCour
--
Increase the Peace!
Charles LaCour
cla...@cwix.com
Paul Lutus wrote in message <76dob2$prv$1...@remarQ.com>...
>/* Loop until we get a valid number */
> do
> {
> r = rand();
> } while ( r < 0 || r > 99 );
>
>This is incredibly inefficient. It requires, on average, (99 / MAX_RAND)
>tries to acquire a number in range. On a system that uses 32-bit integers
>and has a working version of rand(), this means an average run will require
>43 million-odd tries before the probability of a number in range rises to
>50%.
>
>Something tells me Intel didn't foresee this use of their super-fact
>processors, and if this method is used, no one will realize it is fast.
>
>Why not use:
>
>r = rand() % 100;
I had forgotten about this. Thanks for reminding me.
>
>This works the first time. Some will argue that, because of problems with
>the standard random number generator, this will produce numbers that are
not
>very random. But this assertion can easily be tested to discover whether it
>is true on your compiler.
>
>Also, your scrambling method is not guaranteed to move all the numbers --
>some numbers and sequences of numbers will remain in their original
>locations, while others will be moved multiple times.
I don't think the fact that some locations will not be moved and that others
might be moved many times is relevent. I believe the original poster's
concern was one of using the information only once.
Paul Lutus
others
might be moved many times is relevent. I believe the original poster's
concern was one of using the information only once. >>
Only once, but the point was to randomize the array for this single use. It
isn't randomized systematically -- there are gaps in the logic behind the
algorithm. If the array actually needs to be randomized, this algorithm
cannot do it.
Paul Lutus
Charles LaCour wrote in message <2kvi2.270$z21....@news.cwix.com>...
<snip>
Paul Lutus
r = (rand() / (1.0 + RAND_MAX)) * 100;
which will always be well-behaved so long as rand() is well-behaved. >>
Not to argue, just a comment. If the random number generator was
well-behaved, this method would not be required. A well-behaved pseudorandom
number generator would provide satisfactory results no matter what method
one used to specify the range. The only reason this floating-point method
works and the modulo result does not work (when this is true) is because of
the specifics of the problem in the generator. And a different design might
well favor the modulo approach and disfavor the division approach.
Surely someone has gone to the trouble to create a well-behaved generator,
one that passes a critical handful of statistical tests? Again, just a
comment.
Paul Lutus
James Hu wrote in message ...
>On Wed, 30 Dec 1998 09:36:30 -0800, Paul Lutus <nos...@nosite.com> wrote:
>>
>>Why not use:
>>
>>r = rand() % 100;
>
>>This works the first time. Some will argue that, because of problems
>>with the standard random number generator, this will produce numbers
>>that are not very random. But this assertion can easily be tested to
>>discover whether it is true on your compiler.
>
Matthew A. Givens
suggestion.
The simplest way to do this would be to add a field to the structure to
function as a flag, and call it something like (int alreadyUsed). When
loading the structure, set it to FALSE (0). After you have generated the
random number and used the array element, set the flag to TRUE (1). When a
random number is generated, check the flag in the structure at that array
position to see if it has already been used.
Matthew in Montgomery
Shane
Thanks for all your suggestions.
I will go away and have a play with them now
Thanks again
Shane
James Hu
><< The C-faq contains an excellent answer
>r = (rand() / (1.0 + RAND_MAX)) * 100;
>which will always be well-behaved so long as rand() is well-behaved. >>
>
>Not to argue, just a comment. If the random number generator was
>well-behaved, this method would not be required.
But, it is argumentative. The C-faq explains why using modulus may fail.
When I said well-behaved, I obviously meant over the range
[0,RAND_MAX]. For example, a decent P-RNG will produce numbers less
than RAND_MAX/2 about 1/2 the time, and the other 1/2 the time
produces numbers greater than RAND_MAX/2. However, it may very well
alternate between an odd and even number between successive calls.
The C-faq answer also generalizes nicely to a method of producing
random numbers in the range [0,1).
Don't forget the alternative non-floating point version version --
Paul Lutus
several compilers, I must concur with the general view expressed in your
post -- it is not very well-behaved.
Although using modulo to set a range seems an obvious approach, and although
it performs well in so many other similar applications, rand() is really
quite poorly behaved and I will have to stop offering the modulo aproach. I
offered a caution in my original post, but I should stop sugggesting this
method -- that would be a better caution.
Ironically, reversing the bits in rand()'s output produces a better result
than using it as it is delivered. And using a modulo value that is a power
of 2 makes things much worse -- a very brief cycle of the same numbers.
I shouldn't have argued from principle in this case -- rand() is out there,
it isn't likely to suddenly change, and it is really dreadful.
Thanks for your feedback on this issue.
Paul Lutus
James Hu wrote in message ...
Lawrence Kirby
m3c...@earthlink.net "Matthew A. Givens" writes:
>I came late to this thread, so excuse me if I duplicate somebody elses
>suggestion.
>
>The simplest way to do this would be to add a field to the structure to
>function as a flag, and call it something like (int alreadyUsed). When
>loading the structure, set it to FALSE (0). After you have generated the
>random number and used the array element, set the flag to TRUE (1). When a
>random number is generated, check the flag in the structure at that array
>position to see if it has already been used.
Unfortunately this method becomes slower and slower as you pick more random
numbers. At the end you only have a 1/100 chance of picking the remaining
number. Some approaches already posted don't sudder from this problem.
Here's another:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
int main(void)
{
int nums[SIZE];
int i;
srand(time(NULL));
for (i = 0; i < SIZE; i++) {
int r = rand() % (i+1); /* Choose your favorite RNG algorithm */
if (r != i)
nums[i] = nums[r];
nums[r] = i;
}
for (i = 0; i < SIZE; i++)
printf("%4d", nums[i]);
putchar('\n');
return 0;
}
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------