pythonic way of selecing a random value that satisfies a certain predicate

Question

Suppose I have a list of elements and I want to randomly select an element from the list that satisfies a predicate. What is the pythonic way of doing this?

I currently do a comprehension followed by a random.choice() but that is unnecessarily inefficient :

intlist = [1,2,3,4,5,6,7,8,9]
evenlist = [ i for i in intlist if i % 2 == 0 ] 
randomeven = random.choice(evenlist)

Thanks!

Answer 1

I could not find a function sort of random.selectspecific(list, predicate) in the documentation, so I would try something like the following:

import random
def selectspecific(l, predicate):
    result = random.choice(l)
    while (not predicate(result)):
        result = random.choice(l)
    return result

Answer 2

import random

intlist = [1,2,3,4,5,6,7,8,9]
randomeven = random.choice(filter(lambda x: x % 2 == 0, intlist))                                                                                                                                                         

Answer 3

The way you've written it above is actually good idiomatic python. If we analyze the algorithm we'll find it's essentially doing this:

1. Making a list of elements that satisfy the predicate. (Grows linearly with n)
2. Choosing a random element from that list. (Constant time)

The only other way to go about it would be to choose an element at random, decide if it satisfies the predicate, and choose again if it does not. This algorithm is a little more complex. In the case where 90% of the list satisfies the predicate, this will run much faster than your solution. In the case where only 10% of the list satisfies the predicate, it will actually run much slower, because there's a good chance it will randomly select a given element and check if the predicate is satisfied on that element more than once. Now you could consider memoizing your predicate, but you're still going to select a lot of random data. It comes down to this: Unless your solution is particularly unsuited for your data, stick with it, because it's great. Personally, I'd rewrite it like this:

intlist = range(1,10)
randomeven = random.choice([i for i in intlist if i % 2 == 0])

This is a little more concise, but it's going to run exactly the same as your existing code.

Answer 4

How pythonic is this?

from itertools import ifilterfalse
from random import choice
print choice([ i for i in ifilterfalse(lambda x: x%2, range(10)) ])

Answer 5

If you would like to encapsulate more you could create a method to handle the selection, that would accept a predicate method. You can then use this predicate method with filter().

import random
def selectSpecific(intlist, predicate):
  filteredList = filter(predicate, intlist)
  result = random.choice(filteredList)
  return result

You can pass a predicate to selectSpecific() as a lambda or any other method. Example:

intlist = range(1,10)
selectSpecific(intlist, lambda x: x % 2 == 0)

def makeEven(n):
  if n % 2 == 0:
    return n

selectSpecific(intlist, makeEven)