Programa Oneliner Scramble
https://stackoverflow.com/questions/1735561
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
É nessa época do ano novamente que os programadores querem embaralhar uma lista de modo que nenhum elemento reside em sua posição original (pelo menos na Holanda, comemoramos Sinterklaas e escolha palhas para decidir quem escreve quem um poema). Alguém tem um bom python declaração única por isso?
Então, exemplo de entrada: range(10)
Exemplo de saída: [2,8,4,1,3,7,5,9,6,0]
Saída errada seria [2,8,4,1,3,5,7,9,6,0] porque o 5 está em sua posição original. Isso significaria que a pessoa 5 deve escrever um poema para si mesmo e isso é menos divertido.
editar Muitas pessoas repetem a tarefa o tempo que é necessário para ter sorte e descobri que, de fato, a solução é satisfatória. Essa é uma abordagem ruim, pois, em teoria, isso pode levar infinitamente longo. A melhor abordagem é de fato sugerida por Bart, mas não posso colocar isso em um oneliner por um motivo ou outro ...
editar Por Oneliner, quero dizer declaração única. Como parece, o Python também é capaz de comprimir várias instruções em uma única linha. Eu não sabia disso. Atualmente, existem soluções muito boas usando o semicolon para imitar o comportamento multilina em uma única linha. Portanto: "Você pode fazer isso em uma única declaração?"
Solução
Eu descobri que o Shuffle pode ser abusado para resolver isso
from random import shuffle
L = ["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, int=lambda n: int(n - 1))
print L
A distribuição não é uniforme, no entanto, isso não era um requisito.
#For 100,000 samples
(('Beth', 'Cath', 'Dave', 'Emma', 'Anne'), 13417)
(('Beth', 'Cath', 'Emma', 'Anne', 'Dave'), 6572)
(('Beth', 'Dave', 'Anne', 'Emma', 'Cath'), 3417)
(('Beth', 'Dave', 'Emma', 'Cath', 'Anne'), 6581)
(('Beth', 'Emma', 'Anne', 'Cath', 'Dave'), 3364)
(('Beth', 'Emma', 'Dave', 'Anne', 'Cath'), 6635)
(('Cath', 'Anne', 'Dave', 'Emma', 'Beth'), 1703)
(('Cath', 'Anne', 'Emma', 'Beth', 'Dave'), 1705)
(('Cath', 'Dave', 'Beth', 'Emma', 'Anne'), 6583)
(('Cath', 'Dave', 'Emma', 'Anne', 'Beth'), 3286)
(('Cath', 'Emma', 'Beth', 'Anne', 'Dave'), 3325)
(('Cath', 'Emma', 'Dave', 'Beth', 'Anne'), 3421)
(('Dave', 'Anne', 'Beth', 'Emma', 'Cath'), 1653)
(('Dave', 'Anne', 'Emma', 'Cath', 'Beth'), 1664)
(('Dave', 'Cath', 'Anne', 'Emma', 'Beth'), 3349)
(('Dave', 'Cath', 'Emma', 'Beth', 'Anne'), 6727)
(('Dave', 'Emma', 'Anne', 'Beth', 'Cath'), 3319)
(('Dave', 'Emma', 'Beth', 'Cath', 'Anne'), 3323)
(('Emma', 'Anne', 'Beth', 'Cath', 'Dave'), 1682)
(('Emma', 'Anne', 'Dave', 'Beth', 'Cath'), 1656)
(('Emma', 'Cath', 'Anne', 'Beth', 'Dave'), 3276)
(('Emma', 'Cath', 'Dave', 'Anne', 'Beth'), 6638)
(('Emma', 'Dave', 'Anne', 'Cath', 'Beth'), 3358)
(('Emma', 'Dave', 'Beth', 'Anne', 'Cath'), 3346)
Para uma distribuição uniforme, esta versão (mais longa) pode ser usada
from random import shuffle,randint
L=["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, random=lambda: 1, int=lambda n: randint(0, n - 2))
print L
# For 100,000 samples
(('Beth', 'Cath', 'Dave', 'Emma', 'Anne'), 4157)
(('Beth', 'Cath', 'Emma', 'Anne', 'Dave'), 4155)
(('Beth', 'Dave', 'Anne', 'Emma', 'Cath'), 4099)
(('Beth', 'Dave', 'Emma', 'Cath', 'Anne'), 4141)
(('Beth', 'Emma', 'Anne', 'Cath', 'Dave'), 4243)
(('Beth', 'Emma', 'Dave', 'Anne', 'Cath'), 4208)
(('Cath', 'Anne', 'Dave', 'Emma', 'Beth'), 4219)
(('Cath', 'Anne', 'Emma', 'Beth', 'Dave'), 4087)
(('Cath', 'Dave', 'Beth', 'Emma', 'Anne'), 4117)
(('Cath', 'Dave', 'Emma', 'Anne', 'Beth'), 4127)
(('Cath', 'Emma', 'Beth', 'Anne', 'Dave'), 4198)
(('Cath', 'Emma', 'Dave', 'Beth', 'Anne'), 4210)
(('Dave', 'Anne', 'Beth', 'Emma', 'Cath'), 4179)
(('Dave', 'Anne', 'Emma', 'Cath', 'Beth'), 4119)
(('Dave', 'Cath', 'Anne', 'Emma', 'Beth'), 4143)
(('Dave', 'Cath', 'Emma', 'Beth', 'Anne'), 4203)
(('Dave', 'Emma', 'Anne', 'Beth', 'Cath'), 4252)
(('Dave', 'Emma', 'Beth', 'Cath', 'Anne'), 4159)
(('Emma', 'Anne', 'Beth', 'Cath', 'Dave'), 4193)
(('Emma', 'Anne', 'Dave', 'Beth', 'Cath'), 4177)
(('Emma', 'Cath', 'Anne', 'Beth', 'Dave'), 4087)
(('Emma', 'Cath', 'Dave', 'Anne', 'Beth'), 4150)
(('Emma', 'Dave', 'Anne', 'Cath', 'Beth'), 4268)
(('Emma', 'Dave', 'Beth', 'Anne', 'Cath'), 4109)
Como funciona
Aqui está o código para random.shuffle()
def shuffle(self, x, random=None, int=int):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
"""
if random is None:
random = self.random
for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]
Ambas as soluções funcionam segmentando a linha j = int(random() * (i+1))
O primeiro (não uniforme) efetivamente faz a linha funcionar assim
j = int(random() * (i + 1) - 1)
Então, em vez de uma variedade de (1..i) obtemos (0..i-1)
A segunda solução substitui random() com uma função que sempre retorna 1 e usa randint ao invés de int. Então a linha agora funciona assim
j = randint(0, i - 1)
Outras dicas
Depois de embaralhar a lista de números, deixe o [i]a pessoa escreve um poema (e compre um presente!) Para o [i+1]A pessoa na lista: dessa maneira, nunca pode haver alguém que se atrai. Claro, o último deve apontar para o primeiro ...
Mudar todos os elementos da lista por um de maneira circular, Conforme sugerido por Bart, é fácil:
>>> def shift(seq):
... return seq[-1:] + seq[:-1]
...
>>> shift(range(10))
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
Quanto a uma solução aleatória: Nesse caso, a solicitação de uma linha não é uma boa idéia, já que a função óbvia de usar, a saber, random.shuffle, executa sua tarefa em vigor. Em outras palavras: tem um efeito colateral, algo geralmente tenta evitar as compreensões da lista. Há uma maneira de contornar isso, como Paulo ressalta, ou seja, usando random.sample. O código a seguir mostra duas frases que usam essas funções (observe o uso de not shuffle, para contornar o fato de que shuffle retorna None...):
>>> from itertools import repeat
>>> from random import shuffle
>>> def shake_it(seq):
... return next(c for c in repeat(seq[::]) if not shuffle(c) and all(a != b for a, b in zip(seq, c)))
...
>>> shake_it(range(10))
[7, 9, 0, 2, 6, 8, 5, 1, 4, 3]
>>>
>>> from itertools import count
>>> from random import sample
>>> def shake_it(seq):
... return next(c for c in (sample(seq, len(seq)) for _ in count()) if all(a != b for a, b in zip(seq, c)))
...
>>> shake_it(range(10))
[1, 3, 9, 5, 2, 6, 8, 4, 0, 7]
Eu mesmo, eu iria com este:
>>> def shake_it(seq):
... res = seq[::]
... while any(a == b for a, b in zip(res, seq)):
... shuffle(res)
... return res
...
>>> shake_it(range(10))
[5, 7, 9, 2, 6, 8, 3, 0, 4, 1]
Aqui está como você faz isso com o (n) tempo e o (1) memória extra:
Código compreensível:
def shuffle(a)
n = a.length
(0..n - 2).each do |i|
r = rand(n - i - 1) + i + 1
a[r], a[i] = a[i], a[r]
end
a
end
Uma linha (assume "a" é a matriz):
n = a.length and (0..n - 2).each {|i| r = rand(n - i - 1) + i + 1; a[r], a[i] = a[i], a[r]}
O código está em Ruby, mas sem dúvida é facilmente traduzível para Python
Felicidades
PS: A solução modifica a matriz.
"One-liner" no tempo fixo O (n):
import random; a=range(10) # setup (could read in names instead)
for i in range(len(a)-1,0,-1): j=random.randint(0,i-1); a[j],a[i]=a[i],a[j]
print a # output
O loop escolhe os elementos do índice máximo (len (a) -1) até o próximo mais fmal (1). O pool de opções para o elemento K inclui apenas índices de 0 a K-1; Uma vez escolhido, um elemento não será movido novamente.
Após a disputa, nenhum elemento pode residir em sua posição original, porque:
- Se o elemento j for escolhido para algum slot i> j, ele ficará lá
- Caso contrário, o elemento J será trocado com algum outro elemento do slot i
- Exceto pelo elemento no slot 0, que será trocado incondicionalmente com o elemento no slot 1 (na iteração final do loop), se ainda não tiver sido deslocado.
Editar: Isso é logicamente equivalente à resposta do rubi, eu acho
Este é O (n). Ter a importação nos loops é um pouco bobo, mas você queria um revestimento único
L=range(10)
for i in range(1,len(L)):import random;r=random.randint(0,i-1);L[i],L[r]=L[r],L[i]
print L
Aqui está a distribuição de saída quando l = intervalo (5) para 100000 amostras
((1, 2, 3, 4, 0), 4231)
((1, 2, 4, 0, 3), 4115)
((1, 3, 0, 4, 2), 4151)
((1, 3, 4, 2, 0), 4108)
((1, 4, 0, 2, 3), 4254)
((1, 4, 3, 0, 2), 4101)
((2, 0, 3, 4, 1), 4158)
((2, 0, 4, 1, 3), 4177)
((2, 3, 1, 4, 0), 4190)
((2, 3, 4, 0, 1), 4117)
((2, 4, 1, 0, 3), 4194)
((2, 4, 3, 1, 0), 4205)
((3, 0, 1, 4, 2), 4325)
((3, 0, 4, 2, 1), 4109)
((3, 2, 0, 4, 1), 4131)
((3, 2, 4, 1, 0), 4153)
((3, 4, 0, 1, 2), 4081)
((3, 4, 1, 2, 0), 4118)
((4, 0, 1, 2, 3), 4294)
((4, 0, 3, 1, 2), 4167)
((4, 2, 0, 1, 3), 4220)
((4, 2, 3, 0, 1), 4179)
((4, 3, 0, 2, 1), 4090)
((4, 3, 1, 0, 2), 4132)
Meu primeiro programa Python há muito tempo. Ao contrário de muitos dos programas acima, este leva o tempo (n).
s = set(range(10))
r = list()
for i in range(10):
s2 = s - set([i])
val = s2.pop()
r.append(val)
s.discard(val)
print r
ATUALIZAR: Paulo mostrou que o programa acima estava incorreto. Obrigado, Paul. Aqui está uma versão diferente e melhor do mesmo programa:
s = range(10)
for i in range(9):
r = random.randrange(i+1, 10)
s[i], s[r] = s[r], s[i]
print s
Desculpe, isso não é uma linha, mas isso funciona
import random
def sinterklaas(n):
l=[]
for a in range(n):
l.append(-1)
i = 0
while i < 10:
index = random.randint(0,n-1)
if l[index] == -1 and index != i:
l[index] = i
i += 1
Felicidades
import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)
(Ok, eu tenho uma linha 0 lá também ...)
Para um em O (n):
u=range(10); random.shuffle(u); v=[ u[u[i]] for i in range(10) ]; return [ v[(u[i]+1)%10] for i in u ]
u é o inverso da função v, assim v[u[i]+1] é efetivamente o elemento seguinte a I na matriz v.
Aqui está a mudança circular do Stephan202 implementada como uma linha com um incremento de mudança escolhido aleatoriamente:
from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
