# How to generate random number without replacement?

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

It seems that the int(rand(10)) generate random with replacement. I'm
wondering how to generate random number without replacement in perl.
Is there a function for it?

## Re: How to generate random number without replacement?

Peng> It seems that the int(rand(10)) generate random with replacement. I'm
Peng> wondering how to generate random number without replacement in perl.
Peng> Is there a function for it?

\$ perldoc -q shuffle
Found in /usr/local/lib/perl5/5.10.1/pod/perlfaq4.pod
How do I shuffle an array randomly?
If you either have Perl 5.8.0 or later installed, or if you have
Scalar-List-Utils 1.03 or later installed, you can say:

use List::Util 'shuffle';

@shuffled = shuffle(@list);

If not, you can use a Fisher-Yates shuffle.

sub fisher_yates_shuffle {
my \$deck = shift;  # \$deck is a reference to an array
return unless @\$deck; # must not be empty!

my \$i = @\$deck;
while (--\$i) {
my \$j = int rand (\$i+1);
@\$deck[\$i,\$j] = @\$deck[\$j,\$i];
}
}

# shuffle my mpeg collection
#
my @mpeg = <audio/*/*.mp3>;
fisher_yates_shuffle( \@mpeg );    # randomize @mpeg in place
print @mpeg;

Note that the above implementation shuffles an array in place, unlike
the "List::Util::shuffle()" which takes a list and returns a new
shuffled list.

You've probably seen shuffling algorithms that work using splice,
randomly picking another element to swap the current element with

srand;
@new = ();
@old = 1 .. 10;  # just a demo
while (@old) {
push(@new, splice(@old, rand @old, 1));
}

This is bad because splice is already O(N), and since you do it N times,
you just invented a quadratic algorithm; that is, O(N**2). This does not
scale, although Perl is so efficient that you probably won't notice this
until you have rather largish arrays.

print "Just another Perl hacker,"; # the original

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

## Re: How to generate random number without replacement?

On May 31, 9:48=A0pm, mer...@stonehenge.com (Randal L. Schwartz) wrote:

I don't really need shuffle. For example, if I want to sample 1000
number (without replacement) from the numbers between 1 and
1000,000,000, shuffle will take more runtime than necessary.

## Re: How to generate random number without replacement?

PY> On May 31, 9:48 pm, mer...@stonehenge.com (Randal L. Schwartz) wrote:
>>
Peng> It seems that the int(rand(10)) generate random with replacement. I'm
Peng> wondering how to generate random number without replacement in perl.
Peng> Is there a function for it?
>>
>> \$ perldoc -q shuffle

PY> I don't really need shuffle. For example, if I want to sample 1000
PY> number (without replacement) from the numbers between 1 and
PY> 1000,000,000, shuffle will take more runtime than necessary.

then just call rand but cache your hits with a hash. if found in the
hash, then try again. this will work if your sample size of 1k is much
lower than the large number. it will still work but be slow if the
sampling size is close to the total size.

uri

--
Uri Guttman  ------  uri@stemsystems.com  --------  http://www.sysarch.com --
-----  Perl Code Review , Architecture, Development, Training, Support ------
---------  Gourmet Hot Cocoa Mix  ----  http://bestfriendscocoa.com ---------

## Re: How to generate random number without replacement?

Could you please explain what you mean by "with/without replacement"?
A number is a number, it doesn't replace anything....

jue

## Re: How to generate random number without replacement?

These are standard concepts in statistics. Please see the following
webpage for the explanations on sampling 'with/without replacement'.

http://www.ma.utexas.edu/users/parker/sampling/repl.htm

## Re: How to generate random number without replacement?

Ok. For those like me not familiar with this term: he means random
numbers with and without repetition.

jue

## Re: How to generate random number without replacement?

>>> >It seems that the int(rand(10)) generate random with replacement. I'm
>>> >wondering how to generate random number without replacement in perl.
>>>
>>> Could you please explain what you mean by "with/without replacement"?
>>> A number is a number, it doesn't replace anything....
>>
>> These are standard concepts in statistics. Please see the following
>> webpage for the explanations on sampling 'with/without replacement'.
>>
>> http://www.ma.utexas.edu/users/parker/sampling/repl.htm

JE> Ok. For those like me not familiar with this term: he means random
JE> numbers with and without repetition.

and i told him how to do it. i won't tell him again. it is a simple
problem and hashes solve it.

uri

--
Uri Guttman  ------  uri@stemsystems.com  --------  http://www.sysarch.com --
-----  Perl Code Review , Architecture, Development, Training, Support ------
---------  Gourmet Hot Cocoa Mix  ----  http://bestfriendscocoa.com ---------

## Re: How to generate random number without replacement?

What do you mean? I didn't ask you to tell me again.

But I feel sorry that perl doesn't provide such a function out of the
box.

## Re: How to generate random number without replacement?

>>   JE> Ok. For those like me not familiar with this term: he means random
>>   JE> numbers with and without repetition.
>>
>> and i told him how to do it. i won't tell him again. it is a simple
>> problem and hashes solve it.

PY> What do you mean? I didn't ask you to tell me again.

i told you how to do it. either you didn't read it or you didn't get the
solution.

PY> But I feel sorry that perl doesn't provide such a function out of the
PY> box.

i feel sorry for you that you can't code this up in 5 minutes. it is
trivial to do as i outlined. name another lang that has this built in.
it isn't needed as it is easily made from a hash and a loop and calls to
rand. this is about 2 lines of code and possibly 1 line. here, i will
code it up on the fly and possibly even get it right. i leave making
into a sub as your exercise.

my %seen ;
while( 1 ) { \$x = int rand( 100_000_000 ) ; \$seen and next ;
\$seen = 1;  print \$x }

oops, it wrapped into 3 lines.

was that too complex? it will print numbers until it runs out of
them. no duplicates. make it a for loop to control the number of
prints. can you handle that? do you feel sorry for perl now? show me
another lang that could do that as easily.

uri

--
Uri Guttman  ------  uri@stemsystems.com  --------  http://www.sysarch.com --
-----  Perl Code Review , Architecture, Development, Training, Support ------
---------  Gourmet Hot Cocoa Mix  ----  http://bestfriendscocoa.com ---------

## Re: How to generate random number without replacement?

Uri, nobody asked you to tell him again. Why do insist on telling us
three times that you won't do it? Nobody asked me to write a haiku, but
I don't feel the slightest urge to tell you all that I won't write a
haiku,

hp

## Re: How to generate random number without replacement?

I see it differently.

He's got every right to get pissed off from time to time.

How many hours a week does he sit in front of the terminal
answering questions for us (when he could be making money,
presumably, a nice sacrifice for us all!) and after a while
of being eaten by "I have to get back to WORK sometime --
so I can pay some BILLS" or whatever else might be eating
him now and then, that almost it doesn't matter WHAT the
next question is, the least perceived-foolishness/stupidity
in it will elicit a ROAR and accompanying dragon-mouth FLAME
BLAST.

That done, he bypasses a few questions he might have liked

So thank you, Uri, for being there!

David

## Re: How to generate random number without replacement?

You see what "it"?

Differently from what?

Who "he"?

--
email: perl -le "print scalar reverse qq/moc.liamg0cm.j.dat/"
The above message is a Usenet post.
I don't recall having given anyone permission to use it on a Web site.

## Friendly (WAS: How to generate random number without replacement?)

wrote:

I hate web forum interfaces.

Without grumpy old men, what would Usenet be?

Seriously, though, some of us wear many hats and don't have time to
become expert in a tool like Perl.  So we wander in and out of various
newsgroups as the need or interest arises.

As for me, I was working on a local problem and found a good solution
using UNIX datagram sockets.  It was something I had never used before,
so it took me a while to figure things out and put the pieces together
into a working solution.  In the process, I noticed it was hard to find
good *working* examples of UNIX datagram socket code.  Since I coded my
solution in Perl I thought why not post it.  Maybe no one else needs it,
but if only one person does, it could save them time.

So along trot I, an unknown, into c.l.p.m, and post my news.  And what
is the first reply I see?  WHO THE HELL ARE YOU AND WHAT ARE YOU DOING
HERE?  That's what it felt like anyway.

Some newsgroups suffer from the presence of territorial control freaks.
In one, a particular individual has been obsessed with some of my posts,
to the point of stalking.  So if I overreacted upon my arrival here, I
apologize to anyone offended.  Except for the stalker. :-(

--
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php

## Re: How to generate random number without replacement?

UG>     my %seen ;
UG>     while( 1 ) { \$x = int rand( 100_000_000 ) ; \$seen and next ;
UG>         \$seen = 1;  print \$x }

This will grow pretty quickly with a hash.  Bit::Vector already has
Bit_On(\$index) and bit_test(\$index) so memory usage and probably
performance will be a bit (heh) better.

Ted

## Re: How to generate random number without replacement?

wrote:
UG> my %seen ;
UG> while( 1 ) { \$x = int rand( 100_000_000 ) ; \$seen and next ;
UG> \$seen = 1;  print \$x }

TZ> This will grow pretty quickly with a hash.  Bit::Vector already has
TZ> Bit_On(\$index) and bit_test(\$index) so memory usage and probably
TZ> performance will be a bit (heh) better.

he said he wanted 1k random numbers out of a large range so a hash would
be fine for that.

uri

--
Uri Guttman  ------  uri@stemsystems.com  --------  http://www.sysarch.com --
-----  Perl Code Review , Architecture, Development, Training, Support ------
---------  Gourmet Hot Cocoa Mix  ----  http://bestfriendscocoa.com ---------

## Re: How to generate random number without replacement?

WERE this to be a cpan module, maybe a mix would be nice.  Bit vector for
the first N of them, N of course requiring N/8 bytes preallocated probably,
and for > N, the hash scheme?

David

## Re: How to generate random number without replacement?

Ted Zlatanov wrote:

I'd be very surprised if Bit::Vector had faster performance, at least
until the other method started swapping.

Xho

## Re: How to generate random number without replacement?

wrote:

XJ> Ted Zlatanov wrote:

UG> my %seen ;
UG> while( 1 ) { \$x = int rand( 100_000_000 ) ; \$seen and next ;
UG> \$seen = 1;  print \$x }

XJ> I'd be very surprised if Bit::Vector had faster performance, at least
XJ> until the other method started swapping.

It's C internally so performance is pretty good.  But you're probably
right anyhow, I wasn't thinking.

UG> he said he wanted 1k random numbers out of a large range so a hash would
UG> be fine for that.

You're right, I wasn't paying enough attention.

Ted

## Re: How to generate random number without replacement?

What, you're saying a div and a mod (let's assume 64 bits, if integet) to
find the desired bit, versus dealing each time with a hash bucket to choose
an ensuing chain to hunt down through?

So you make the bucket-array longer, so the chains are short -- get it
long enough so only very, very few chains are longer than one (most
being zero) in length, and you're almost emulating the bit-vector
scheme, but taking up FAR FAR more space.

?

David