What is the most pythonic way to pop a random element from a list?

Say I have a list x with unkown length from which I want to randomly pop one element so that the list does not contain the element afterwards. What is the most pythonic way to do this?

I can do it using a rather unhandy combincation of pop, random.randint, and len, and would like to see shorter or nicer solutions:

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

What I am trying to achieve is consecutively pop random elements from a list. (i.e., randomly pop one element and move it to a dictionary, randomly pop another element and move it to another dictionary, ...)

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

Solution 1:

What you seem to be up to doesn't look very Pythonic in the first place. You shouldn't remove stuff from the middle of a list, because lists are implemented as arrays in all Python implementations I know of, so this is an O(n) operation.

If you really need this functionality as part of an algorithm, you should check out a data structure like the blist that supports efficient deletion from the middle.

In pure Python, what you can do if you don't need access to the remaining elements is 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 the remainder (which is a bit of a code smell, IMHO), at least you can pop() from the end of the list now (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, instead of mutating state (like you do with the list).

Solution 2:

You won't get much better than that, but here is a slight improvement:

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

Documentation on random.randrange():

random.randrange([start], stop[, step])
Return a randomly selected element from range(start, stop, step). This is equivalent to choice(range(start, stop, step)), but doesn’t actually build a range object.

Solution 3:

To remove a single element at random index from a list if the order of the rest of list elements doesn't 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)

The swap is used to avoid O(n) behavior on deletion from a middle of a list.

Solution 4:

Here's another alternative: why don't you shuffle the list first, and then start popping elements of it until no more elements remain? like this:

import random

x = [1,2,3,4,5,6]
random.shuffle(x)

while x:
    p = x.pop()
    # do your stuff with p

Solution 5:

despite many answers suggesting use random.shuffle(x) and x.pop() its very slow on large data. and time required on a list of 10000 elements took about 6 seconds when shuffle is enabled. when shuffle is disabled speed was 0.2s

the fastest method after testing all the given methods above was turned out to be written by @jfs

import random

L = ['1',2,3,'4'...1000] #you can take mixed or pure list
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)

in support of my claim here is the time complexity chart from this source enter image description here

IF there are no duplicates in list,

you can achieve your purpose using sets too. once list made into set duplicates will be removed. remove by value and remove random cost O(1), ie very effecient. this is the cleanest method i could come up with.

L=set([1,2,3,4,5,6...]) #directly input the list to inbuilt function set()
while 1:
    r=L.pop()
    #do something with r , r is random element of initial list L.

Unlike lists which support A+B option, sets also support A-B (A minus B) along with A+B (A union B)and A.intersection(B,C,D). super useful when you want to perform logical operations on the data.

OPTIONAL

IF you want speed when operations performed on head and tail of list, use python dequeue (double ended queue) in support of my claim here is the image. an image is thousand words.

enter image description here