By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,804 Members | 1,659 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,804 IT Pros & Developers. It's quick & easy.

need suggestion about random selection

P: n/a
Hello.

Problem:
How can I select K random values from the elements 0,1,2,3,4...,N-1 ?

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 re-select 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()% (N-1) and select the number
that is that many steps away from the last selected number (wrapping back
to 0 when reaching past N-1. Fine, you have two numbers, then select the
number that is rand()%(N-2) 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?
Jul 22 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Gunnar wrote:

Hello.

Problem:
How can I select K random values from the elements 0,1,2,3,4...,N-1 ?

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 re-select 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()% (N-1) and select the number
that is that many steps away from the last selected number (wrapping back
to 0 when reaching past N-1. Fine, you have two numbers, then select the
number that is rand()%(N-2) 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...,N-1
Now shuffle it
3,4,0,N-1...,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
Jul 22 '05 #2

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...,N-1
Now shuffle it
3,4,0,N-1...,2,1
and take the first K elements

Look up <algorithm>. There alredy is a shuffle
algorithm ready to use (random_shuffle)

Jul 22 '05 #3

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
Jul 22 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.