programma di scramble oneliner
https://stackoverflow.com/questions/1735561
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
E 'tempo che l'anno nuovo che i programmatori vogliono mescolare una lista in modo tale che nessun elemento risiede sulla sua posizione originale (almeno nei Paesi Bassi, si celebra Sinterklaas e scegliere cannucce per decidere chi scrive che un poema). Qualcuno ha un bel Python singola istruzione per questo?
Così, ad esempio ingresso: range(10)
Esempio di stampa: [2,8,4,1,3,7,5,9,6,0]
uscita errata sarebbe [2,8,4,1,3,5,7,9,6,0] perché il 5 è nella sua posizione originale. Ciò significa che la persona 5 deve scrivere una poesia a se stesso e che è meno divertente.
Modifica Molte persone ripetono l'assegnazione solo il tempo necessario per avere fortuna e scoprire che in realtà la soluzione è soddisfacente. Questo è un approccio male come in teoria questo può richiedere infinitamente lungo. L'approccio migliore è infatti suggerito da Bart, ma non riesco a ottenere che in un oneliner per un motivo o l'altro ...
modifica Per oneliner, voglio dire singola istruzione . Come appare, Python è anche in grado di comprimere istruzioni multiple su una singola linea. Non lo sapevo. Al momento non ci sono soluzioni molto bello solo utilizzando il punto e virgola per simulare il comportamento più righe su una sola riga. Quindi: "si può fare in un unico prospetto?"
Soluzione
Ho trovato casuale possono essere oggetto di abusi nella soluzione di questo
from random import shuffle
L = ["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, int=lambda n: int(n - 1))
print L
La distribuzione non è uniforme, ma questo non era un 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)
Per una distribuzione uniforme, questa versione (più) può essere utilizzato
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)
Come funziona
Ecco il codice per 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]
Entrambe le soluzioni di lavoro di mira il j = int(random() * (i+1)) riga
Il primo (non uniforme) rende effettivamente la linea di lavoro simili
j = int(random() * (i + 1) - 1)
Così, invece di una serie di (1..i) otteniamo (0..i-1)
La seconda soluzione sostituisce random() con una funzione che restituisce sempre 1, e utilizza randint anziché int. Così la linea ora funziona come questo
j = randint(0, i - 1)
Altri suggerimenti
Dopo aver mescolato l'elenco dei numeri, lasciare la persona [i]th scrivere una poesia (e comprare un regalo!) Per la persona [i+1]th nella lista: in questo modo, non ci può mai essere qualcuno che lui o lei stessa disegna. Naturalmente, l'ultimo dovrebbe puntare al primo ...
Spostamento ogni elemento nell'elenco di uno in modo circolare, come suggerito da Bart , è facile:
>>> def shift(seq):
... return seq[-1:] + seq[:-1]
...
>>> shift(range(10))
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
Come per una soluzione casuale : in questo caso la richiesta di una battuta non è una buona idea, poiché la funzione ovvia per l'utilizzo, cioè random.shuffle , svolge il suo compito in atto. In altre parole: ha un effetto collaterale , qualcosa che di solito si cerca di evitare in list comprehension. C'è un modo per aggirare questo, però, come Paul sottolinea, vale a dire utilizzando random.sample . Il codice seguente mostra due battute che utilizzano queste funzioni (si noti l'uso di not shuffle, per aggirare il fatto che shuffle ritorna 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]
Io, mi piacerebbe andare con questo:
>>> 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]
Ecco come si fa con O (n) e O (1) memoria aggiuntiva:
Codice comprensibile:
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
una battuta (assume "a" è la matrice):
n = a.length and (0..n - 2).each {|i| r = rand(n - i - 1) + i + 1; a[r], a[i] = a[i], a[r]}
Il codice è in Ruby, ma senza alcun dubbio è facilmente traducibile a Python
Saluti
P.S .: La soluzione modifica la matrice.
"One-liner" in O (n) fisso:
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
Il ciclo riprende elementi dall'indice massimo (len (a) -1) fino al successivo-piccola (1). La piscina scelta per l'elemento k comprende solo gli indici da 0 a k-1; una volta scelto, un elemento non verrà spostato nuovamente.
Dopo la corsa, nessun elemento può risiedere nella sua posizione originale, perché:
- se elemento j viene raccolto per alcuni slot i> j, ci rimarrà
- altrimenti, elemento j sarà scambiato con un altro elemento di alloggiamento i
- eccezione per l'elemento in slot 0, che verrà scambiato incondizionatamente con l'elemento nello slot 1 (nell'iterazione finale del loop) se non è già stato spostato.
[edit: questo è logicamente equivalente alla risposta Ruby, penso]
Questo è O (N). Avendo l'importazione negli anelli è un po 'sciocco, ma si voleva un uno di linea
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
Ecco la distribuzione d'uscita quando L = gamma (5) per 100000 campioni
((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)
Il mio primo programma Python in un lungo tempo. A differenza di molti dei programmi di cui sopra, questo prende O (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
UPDATE : Paolo ha dimostrato che il programma di cui sopra non era corretto. Grazie, Paul. Ecco un diverso, migliore versione dello stesso programma:
s = range(10)
for i in range(9):
r = random.randrange(i+1, 10)
s[i], s[r] = s[r], s[i]
print s
Spiacente, questo non è un one-liner, ma questo funziona
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
Saluti
import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)
(Ok, ho una linea 0 a anche lì ...)
Per uno in 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 è l'inverso della funzione v, così v[u[i]+1] è effettivamente l'elemento seguente i nella matrice v.
Ecco spostamento circolare di Stephan202 implementato come una battuta con un incremento di spostamento scelto casualmente:
from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
