Prev: Troubles using Net::Pcap and Net::PcapUtils
Next: How to take two input streams?
From: Peng Yu on 31 May 2010 22:43
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?
From: Randal L. Schwartz on 31 May 2010 22:48
>>>>> "Peng" == Peng Yu <pengyu.ut(a)gmail.com> writes:

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
<merlyn(a)stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
From: Peng Yu on 31 May 2010 23:20
On May 31, 9:48 pm, mer...(a)stonehenge.com (Randal L. Schwartz) wrote:
> >>>>> "Peng" == Peng Yu <pengyu...(a)gmail.com> writes:
>
> 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

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.
From: J�rgen Exner on 31 May 2010 23:25
Peng Yu <pengyu.ut(a)gmail.com> wrote:
>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....

jue
From: Uri Guttman on 31 May 2010 23:44
>>>>> "PY" == Peng Yu <pengyu.ut(a)gmail.com> writes:

PY> On May 31, 9:48�pm, mer...(a)stonehenge.com (Randal L. Schwartz) wrote:
>> >>>>> "Peng" == Peng Yu <pengyu...(a)gmail.com> writes:
>>
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(a)stemsystems.com -------- http://www.sysarch.com --
----- Perl Code Review , Architecture, Development, Training, Support ------
--------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com ---------
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Troubles using Net::Pcap and Net::PcapUtils
Next: How to take two input streams?