P: n/a

Hello.
Problem:
How can I select K random values from the elements 0,1,2,3,4...,N1 ?
I don't know if there's an easy way of doing this, but here are suggestions
for doing it.
One way is to select K random elements (using a rand()% N), and then see if
any number was choosen twice, and then reselect the duplicats until the
choosen numbers are distinct. That ought to work fine when K much smaller
than N. But I guess it will be more problematic when K is about N/2. (when
K>N/2, just select the numbers that are not selected).
Another foolproof method (but probably very error prone when coding) is to
select one element, then generate a rand()% (N1) and select the number
that is that many steps away from the last selected number (wrapping back
to 0 when reaching past N1. Fine, you have two numbers, then select the
number that is rand()%(N2) steps away, avoiding the already taken numbers,
and so on.... that way you will never get a number twice! The problem is
implementing it..
The third option is to use a vector and removing each choosen number, but
is that really efficient?
Do you have any clever idea for how to do this?  
Share this Question
P: n/a

Gunnar wrote: Hello.
Problem: How can I select K random values from the elements 0,1,2,3,4...,N1 ?
I don't know if there's an easy way of doing this, but here are suggestions for doing it.
One way is to select K random elements (using a rand()% N), and then see if any number was choosen twice, and then reselect the duplicats until the choosen numbers are distinct. That ought to work fine when K much smaller than N. But I guess it will be more problematic when K is about N/2. (when K>N/2, just select the numbers that are not selected).
Another foolproof method (but probably very error prone when coding) is to select one element, then generate a rand()% (N1) and select the number that is that many steps away from the last selected number (wrapping back to 0 when reaching past N1. Fine, you have two numbers, then select the number that is rand()%(N2) steps away, avoiding the already taken numbers, and so on.... that way you will never get a number twice! The problem is implementing it..
The third option is to use a vector and removing each choosen number, but is that really efficient?
Do you have any clever idea for how to do this?
Think about the following:
Take your vector
0,1,2,3,4...,N1
Now shuffle it
3,4,0,N1...,2,1
and take the first K elements
Look up <algorithm>. There alredy is a shuffle
algorithm ready to use (random_shuffle)

Karl Heinz Buchegger kb******@gascad.at  
P: n/a

>> Do you have any clever idea for how to do this?
You had one!
Thank you very much! Think about the following: Take your vector 0,1,2,3,4...,N1 Now shuffle it 3,4,0,N1...,2,1 and take the first K elements
Look up <algorithm>. There alredy is a shuffle algorithm ready to use (random_shuffle)  
P: n/a

Gunnar wrote: Do you have any clever idea for how to do this?
You had one!
Not really. If you are playing cards you have done the
exact same thing a thousend times before. You simply
didn't notice :)

Karl Heinz Buchegger kb******@gascad.at   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1489
 replies: 3
 date asked: Jul 22 '05
