What is the most pythonic way to pop a random elem

问题:

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.

回答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).

回答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.

回答3:

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

回答4:

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.

回答5:

One way to do it is:

x.remove(random.choice(x))

回答6:

While not popping from the list, I encountered this question on Google while trying to get X random items from a list without duplicates. Here's what I eventually used:

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

This may be slightly inefficient as you're shuffling an entire list but only using a small portion of it, but I'm not an optimisation expert so I could be wrong.

回答7:

This answer comes courtesy of @niklas-b:

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

To quote the PYPI page:

...a list-like type with better asymptotic performance and similar performance on small lists

The blist is a drop-in replacement for the Python list that provides better performance when modifying large lists. The blist package also provides sortedlist, sortedset, weaksortedlist, weaksortedset, sorteddict, and btuple types.

One would assume lowered performance on the random access/random run end, as it is a "copy on write" data structure. This violates many use case assumptions on Python lists, so use it with care.

HOWEVER, if your main use case is to do something weird and unnatural with a list (as in the forced example given by @OP, or my Python 2.6 FIFO queue-with-pass-over issue), then this will fit the bill nicely.

回答8:

I know this is an old question, but just for documentation's sake:

If you (the person googling the same question) are doing what I think you are doing, which is selecting k number of items randomly from a list (where k<=len(yourlist)), but making sure each item is never selected more than one time (=sampling without replacement), you could use random.sample like @j-f-sebastian suggests. But without knowing more about the use case, I don't know if this is what you need.