On Jan 5, 8:50 pm, Paul Hankin <[EMAIL PROTECTED]> wrote:
> On Jan 5, 5:12 pm, Paul Hankin <[EMAIL PROTECTED]> wrote:
>
>
>
> > On Jan 5, 4:14 pm, [EMAIL PROTECTED] wrote:
>
> > > On Jan 5, 5:07 pm, [EMAIL PROTECTED] wrote:
>
> > > > Hello, Paul and Arnaud.
> > > > While I think about your answers: do you think there is any way to
> > > > avoid shuffle?
> > > > It may take unnecessary long on a long list most of whose elements
> > > > have the property.
>
> > You could generate a random shuffle of range(len(seq)) lazily, and use
> > that to iterate over your sequence.
>
> > import random
> > import itertools
>
> > def randxrange(n):
> > "Generate the numbers 0 to n-1 in a random order"
> > x = range(n)
> > for i in xrange(n):
> > r = random.randrange(n - i)
> > yield x[r]
> > x[r] = x[n - i - 1]
>
> > def shuffled(seq):
> > "Generate the elements of seq in a random order"
> > return (seq[i] for i in randxrange(len(seq)))
>
> > def pick_random(seq, prop):
> > return itertools.ifilter(prop, shuffled(seq)).next()
>
> At the risk of filling this thread with my posts, here's a much
> simplified and faster version of this code that uses no extra storage.
>
> import random
>
> def pick_random(seq, prop):
> L = len(seq)
> for i in xrange(L):
> r = random.randrange(L - i)
> if prop(seq[r]):
> return seq[r]
> seq[r] = seq[L - i - 1]
>
> --
> Paul Hankin
Great! This is so simple it must be the best way to do it. Thanks
for that: I could feel there must be an elegant way, but I couldn't
put my finger on it. The only downside, of course, is that it mutates
seq. Moreover, it can be slightly modified to be a generator (in case
one wants to draw many elements from the sequence), improving vastly
on the generator function I proposed earlier.
def pick_random(seq, prop):
for i in xrange(len(seq), 0, -1):
r = random.randrange(i)
if prop(seq[r]):
return seq[r]
seq[r] = seq[i - 1]
# Generator version.
def random_picker(seq, prop):
for i in xrange(len(seq), 0, -1):
while True:
r = random.randrange(i)
if not prop(seq[r]): break
yield seq[r]
seq[r] = seq[i - 1]
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
