[kw-pm] picking a random list element, the hard way

Abram Hindle abram.hindle at softwareprocess.es
Sun Feb 27 18:42:56 PST 2011


Well you did golf better than Daniel's.

I've got an extension to the puzzle ;)

Now you want N elements picked uniformly from the stream without
duplicates (don't choose the same element twice). All the elements must
be uniformly randomly chosen. You don't know the size of the stream, but
we'll guarantee it is of size N or longer. You're allowed to store N
elements in memory + any meta data.

An example run:
$ seq 1 100 | perl chooser.pl 10
51
63
100
58
12
23
90
11
69
7

The format doesn't have to be the same, but you want to choose N
elements from a stream without storing the entire stream and the output
should not be biased, the choices should be uniformly random.

abram


On 02/27/2011 06:23 PM, Cees Hek wrote:
> I hate it when people dangle exercises like this in front of my face
> because i always get sucked into trying them out when i should be
> doing more productive work ;)
> 
> Here is a (very ugly) golfed solution which is most likely of no use
> to you in your intro class :)
> 
> seq 1 10 | perl -pe '$v=$_ if rand()<1/$.}{$_=$v'
> 
> I agree with you though, the algorithm is interesting and yet it is
> still trivial enough to implement, which makes it a great example for
> a beginner class.
> 
> Cheers,
> 
> Cees Hek
> 
> On Sat, Feb 26, 2011 at 5:52 AM, Robert P. J. Day <rpjday at crashcourse.ca> wrote:
>>
>>  for your entertainment value, here's an optional exercise i'm going
>> to give out in next week's perl class.  it's not so much a perl
>> question as it is an algorithmic analysis question that's actually
>> quite simple to code once you figure it out.
>>
>>  JOB: pick a random element from a list, such that each element in
>> the list is equally likely to be selected.
>>
>>  sounds trivial, yes?  except here's the extra condition.  you're
>> given the list elements only *one at a time*.  you're not allowed to
>> store them, and you have no idea how many are coming.  and yet, you
>> still need to pick a random element out of that list.
>>
>>  thoughts?
>>
>> rday
>> _______________________________________________
>> kw-pm mailing list
>> kw-pm at pm.org
>> http://mail.pm.org/mailman/listinfo/kw-pm
>>
> _______________________________________________
> kw-pm mailing list
> kw-pm at pm.org
> http://mail.pm.org/mailman/listinfo/kw-pm


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://mail.pm.org/pipermail/kw-pm/attachments/20110227/ce6a1c6f/attachment.bin>


More information about the kw-pm mailing list