need suggestion about random selection

[Gunnar]

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?

[Karl Heinz Buchegger]

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

[Gunnar]

>> 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 )

[Karl Heinz Buchegger]

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