What is the most pythonic way to infer a random item from a list?

Question

Let's say I have a list x with an unknown length, from which I want to randomly pop one element so that the list does not subsequently contain this element. What is the most python way to do this?

I can do this using a rather inconvenient combination of pop , random.randint and len , and would like to see shorter or better solutions:

 import random x = [1,2,3,4,5,6] x.pop(random.randint(0,len(x)-1)) 

What I'm trying to achieve is to consistently extract random items from a list. (i.e. randomly push one element and move it to the dictionary, randomly push another element and move it to another dictionary, ...)

Please note that I am using Python 2.6 and did not find any solutions using the search function.

Answer 1

That you do not seem to be very similar to Pythonic. You should not remove material from the middle of the list, because lists are implemented as arrays in all Python implementations that I know of, so this is an O(n) operation.

If you really need this functionality as part of the algorithm, you should check out a data structure such as blist , which supports efficient removal from the middle.

In pure Python, what can you do if you do not need access to the rest of the elements, just shuffle the list first and then iterate over it:

 lst = [1,2,3] random.shuffle(lst) for x in lst: # ... 

If you really need a remainder (which looks a bit like code, IMHO), at least you can pop() from the end of the list (which is fast!):

 while lst: x = lst.pop() # do something with the element 

In general, you can often express your programs more elegantly if you use a more functional style rather than changing the state (such as with a list).

Answer 2

You will not be much better, but this is a slight improvement:

 x.pop(random.randrange(len(x))) 

Documentation at random.randrange() :

random.randrange ([start], stop [, step])
Return a randomly selected item from range(start, stop, step) . This is equivalent to choice(range(start, stop, step)) , but does not actually create a range object.

Answer 3

Here's another alternative: why don't you shuffle the list first, and then start popping up its elements until there are no more elements left? eg:

 import random x = [1,2,3,4,5,6] random.shuffle(x) while x: p = x.pop() # do your stuff with p 

Answer 4

To remove one element from a random index from a list, if the order of the remaining elements of the list does not matter:

 import random L = [1,2,3,4,5,6] i = random.randrange(len(L)) # get random index L[i], L[-1] = L[-1], L[i] # swap with the last element x = L.pop() # pop last element O(1) 

Swap is used to avoid O (n) behavior when removed from the middle of the list.

Answer 5

One way to do this:

 x.remove(random.choice(x)) 

Answer 6

Until you left the list, I came across this question on Google, trying to get X random elements from the list without duplicates. Here is what I ended up using:

 items = [1, 2, 3, 4, 5] items_needed = 2 from random import shuffle shuffle(items) for item in items[:items_needed]: print(item) 

This might be a little inefficient as you shuffle the whole list, but use only a small part, but I'm not an optimization expert, so I could be wrong.

Answer 7

This answer is courtesy of @ niklas-b :

"You might want to use something like pypi.python.org/pypi/blist "

To quote the PYPI page :

... a list type having better asymptotic characteristics and similar performance in small lists

Blist is a replacement for the Python list, which provides better performance when modifying large lists. The blist package also provides sorted list, sorting, weak lists, weaknesses, sorteddict and btuple.

One can assume a decrease in random access / random launch performance , as this is a copy-on-write data structure. This violates many assumptions for use in Python lists , so use it with caution .

HOWEVER, if your main use case is to do something strange and unnatural with a list (both in the forced example given by @OP and in case of a problem with Python 2.6 FIFO queue-with-pass-over), then this will correspond to the score beautifully.

Answer 8

I know this is an old question, but for documentation only:

If you (the person searching for the same question) are doing what I think you are doing, choose a random number k from the list (where k <= len (your list)), but make sure that everyone an element has never been selected more than once (= selection without replacement), you can use random.sample , as @ jf-sebastian suggests. But, not knowing more about the precedent, I do not know if you need it.