Qual é a maneira mais pythônica de retirar um elemento aleatório de uma lista?

Digamos que eu tenha uma lista xcom comprimento desconhecido da qual desejo pop aleatoriamente um elemento para que a lista não contenha o elemento posteriormente. Qual é a maneira mais pítônica de fazer isso?

Eu posso fazer isso usando um combincation vez unhandy de pop, random.randinte len, e gostaria de ver soluções mais curtos ou mais agradáveis:

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

O que estou tentando alcançar é pop consecutivamente elementos aleatórios de uma lista. (ou seja, pop aleatoriamente um elemento e movê-lo para um dicionário, pop aleatoriamente outro elemento e movê-lo para outro dicionário, ...)

Observe que estou usando Python 2.6 e não encontrei nenhuma solução por meio da função de pesquisa.

O que você parece estar fazendo não parece muito pitônico em primeiro lugar. Você não deve remover coisas do meio de uma lista, porque as listas são implementadas como matrizes em todas as implementações de Python que eu conheço, então esta é uma O(n)operação.

Se você realmente precisa dessa funcionalidade como parte de um algoritmo, deve verificar uma estrutura de dados como a blistque oferece suporte à exclusão eficiente do meio.

No Python puro, o que você pode fazer se não precisar de acesso aos elementos restantes é apenas embaralhar a lista primeiro e, em seguida, iterar sobre ela:

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

Se você realmente precisa do resto (que é um pouco cheiro de código, IMHO), pelo menos você pode pop()partir do final da lista agora (que é rápido!):

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

Em geral, você pode expressar seus programas com mais elegância se usar um estilo mais funcional, em vez de um estado de mutação (como você faz com a lista).

Você não vai conseguir muito melhor do que isso, mas aqui está uma pequena melhoria:

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

Documentação em random.randrange():

random.randrange ([start], stop [, step])
Retorna um elemento selecionado aleatoriamente range(start, stop, step). Isso é equivalente a choice(range(start, stop, step)), mas na verdade não cria um objeto de intervalo.

Para remover um único elemento em um índice aleatório de uma lista se a ordem do restante dos elementos da lista não importa:

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)

A troca é usada para evitar o comportamento O (n) na exclusão de um meio de uma lista.

Aqui está outra alternativa: por que você não embaralha a lista primeiro e, em seguida, começa a destacar elementos dela até que não haja mais elementos? como isso:

import random

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

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

Uma maneira de fazer isso é:

x.remove(random.choice(x))

Apesar de não ter saído da lista, encontrei esta pergunta no Google ao tentar obter X itens aleatórios de uma lista sem duplicatas. Aqui está o que acabei usando:

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

Isso pode ser um pouco ineficiente, pois você está embaralhando uma lista inteira, mas usando apenas uma pequena parte dela, mas não sou um especialista em otimização, então posso estar errado.

Eu sei que esta é uma pergunta antiga, mas apenas para fins de documentação:

Se você (a pessoa pesquisando a mesma pergunta no Google) está fazendo o que eu acho que está fazendo, que é selecionar k número de itens aleatoriamente de uma lista (onde k <= len (sua lista)), mas certificando-se de que cada item nunca seja selecionado mais de uma vez (= amostragem sem substituição), você pode usar random.sample como @ jf-sebastian sugere. Mas sem saber mais sobre o caso de uso, não sei se é disso que você precisa.

Esta resposta é cortesia de @ niklas-b :

" Você provavelmente deseja usar algo como pypi.python.org/pypi/blist "

Para citar a página PYPI :

... um tipo de lista com melhor desempenho assintótico e desempenho semelhante em listas pequenas

O blist é um substituto imediato para a lista Python que fornece melhor desempenho ao modificar listas grandes. O pacote blist também fornece sortedset, sortedset, weaksortedlist, weaksortedset, Sortedict e tipos btuple.

Seria de se supor um desempenho reduzido no final de acesso aleatório / execução aleatória , pois é uma estrutura de dados de "cópia na gravação". Isso viola muitas suposições de casos de uso nas listas Python, portanto , use-o com cuidado .

NO ENTANTO, se o seu principal caso de uso é fazer algo estranho e não natural com uma lista (como no exemplo forçado dado por @OP, ou meu problema de fila FIFO com passagem de Python 2.6), então isso se encaixará perfeitamente .

apesar de muitas respostas sugerindo uso random.shuffle(x)e x.pop()é muito lento em grandes dados. e o tempo necessário em uma lista de 10000elementos levou cerca de 6 secondsquando o shuffle está ativado. quando o shuffle está desativado, a velocidade era0.2s

o método mais rápido depois de testar todos os métodos fornecidos acima foi escrito por @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)

em apoio à minha afirmação, aqui está o gráfico de complexidade de tempo desta fonte

SE não houver duplicatas na lista,

você pode atingir seu objetivo usando conjuntos também. uma vez que a lista feita em duplicatas definidas será removida. remove by valuee remove randomcusto O(1), ou seja, muito eficiente. este é o método mais limpo que eu poderia inventar.

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.

Ao contrário de listsqual A+Bopção de suporte , setstambém suporte A-B (A minus B)junto com A+B (A union B)e A.intersection(B,C,D). super útil quando você deseja realizar operações lógicas nos dados.

OPCIONAL

SE você quiser velocidade quando as operações forem executadas no início e no fim da lista, use python dequeue (fila dupla) para apoiar minha afirmação, aqui está a imagem. uma imagem vale mil palavras.