Selecting random elements in a list conditional on attribute

I see 3 options here:

• Create a list anyway, you can do so with a list comprehension:

  random.choice([a for a in agents if a.state == 0])
  

• Put the random.choice() call in a loop, keep trying until you get one that matches the criteria:

  while True:
      agent = random.choice(agents)
      if agent.state == 0:
          break
  

• Index your agents list, then pick from that index; these are really just lists still:

  agent_states_index = {}
  for index, agent in enumerate(agents):
      agent_states_index.setdefault(agent.state, []).append(index)
  
  agent_index = random.choice(agent_states_index[0])
  agent = agents[agent_index]
  

There are four algorithms I know of for this.

The first is detailed in this answer. Iterate through the array, then if you come across an element that satisfies a condition, check to see if a random integer is less than (1/(however many elements you've passed that satisfy the condition)).

The second is to iterate through your array, adding to a new array elements that fulfill the condition, then randomly pick one out of that list.

Both of these algorithms run in O(n) time, where n is the size of the array. They are guaranteed to find an element if it is there and satisfies the condition.

There are another two algorithms that are much faster. They both run in O(1) time but have some major weaknesses.

The first is to keep picking indexes randomly until you hit on one that satisfies the condition. This has a potentially infinite time complexity but is O(1) in practice. (If there are very few elements that satisfy the condition and the array is very large, something like 1 in 10000 elements, this becomes slower.) It is also not guaranteed to find an element if it is not there; if there is no element that satisfies the condition, you either have an infinite loop or have to write the algorithm to make a finite number of guesses and you might miss an element even if it is there.

The second is to pick a random index, then keep incrementing it until you find an index that satisfies the condition. It is guaranteed to either find an acceptable index or look through all of the indexes without entering into an infinite loop. It has the downside of not being completely random. Obviously, if you increment the index by 1 every time, it will be really, really nonrandom (if there are clumps of acceptable indexes in the array). However, if you choose the increment randomly from one of a handful of numbers that are coprime to the number of elements of the array, then it's still not fair and random, but is fairly fair and random, and guaranteed to succeed.

Again, these last 2 algorithms are very fast but are either not guaranteed to work or not guaranteed to be completely random. I don't know of an algorithm that is both fast, guaranteed to work, and completely fair and random.