Oneliner Scramble -Programm
https://stackoverflow.com/questions/1735561
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es ist wieder in dieser Jahreszeit, in der Programmierer eine Liste mischen möchten, so dass kein Element in seiner ursprünglichen Position liegt (zumindest in den Niederlanden, feiern wir Sinterklaas und wählen Sie Strohhalme für die Entscheidung, wer ein Gedicht schreibt). Hat jemand eine schöne Python? Einzelaussage dafür?
Eingabebeispiel: range(10)
Ausgangsbeispiel: [2,8,4,1,3,7,5,9,6,0]
Falsche Ausgabe wäre sein [2,8,4,1,3,5,7,9,6,0] weil die 5 ist an seiner ursprünglichen Position. Dies würde bedeuten, dass Person 5 ein Gedicht vor sich schreiben muss und das weniger Spaß macht.
bearbeiten Viele Menschen wiederholen die Aufgabe so lange wie nötig Glück haben und stellen Sie fest, dass die Lösung tatsächlich zufriedenstellend ist. Dies ist ein schlechter Ansatz, da dies theoretisch unendlich lange dauern kann. Der bessere Ansatz wird von Bart tatsächlich vorgeschlagen, aber ich kann das aus dem einen oder anderen Grund nicht in einen Oneliner bekommen ...
bearbeiten Mit Oneliner meine ich Einzelaussage. Wie es scheint, ist Python auch in der Lage, mehrere Anweisungen auf einer einzelnen Zeile zu komprimieren. Das wusste ich nicht. Derzeit gibt es sehr schöne Lösungen, die nur das Semikolon verwenden, um das Multilinverhalten auf einer einzigen Linie nachzuahmen. Daher: "Kannst du es in einer einzigen Aussage machen?"
Lösung
Ich stellte fest, dass Shuffle in die Lösung dessen missbraucht werden kann
from random import shuffle
L = ["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, int=lambda n: int(n - 1))
print L
Die Verteilung ist nicht einheitlich, dies war jedoch keine Anforderung.
#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)
Für eine einheitliche Verteilung kann diese (längere) Version verwendet werden
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)
Wie es funktioniert
Hier ist der Code für 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]
Beide Lösungen wirken sich auf die Linie aus j = int(random() * (i+1))
Durch die erste (nicht einheitliche) wirkt die Linie so effektiv wie diese
j = int(random() * (i + 1) - 1)
Anstelle einer Reichweite von (1..i) erhalten wir (0..i-1)
Die zweite Lösung ersetzt random() mit einer Funktion, die immer 1 zurückgibt und verwendet randint Anstatt von int. Also funktioniert die Linie jetzt so
j = randint(0, i - 1)
Andere Tipps
Nachdem Sie die Liste der Zahlen gemischt haben, lassen Sie die [i]Die Person schreibe ein Gedicht (und kaufe ein Geschenk!) Für die [i+1]Die Person in der Liste: Auf diese Weise kann es niemals jemanden geben, der sich selbst zieht- oder sich selbst. Natürlich sollte der letzte auf den ersten zeigen ...
Jedes Element in der Liste auf kreisförmige Weise um eins verschieben, Wie von Bart vorgeschlagen, ist einfach:
>>> def shift(seq):
... return seq[-1:] + seq[:-1]
...
>>> shift(range(10))
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
Wie für eine zufällige Lösung: In diesem Fall ist die Anfrage für einen Ein-Liner keine so gute Idee, da die offensichtliche Funktion zu verwenden ist, nämlich random.shuffle, führt seine Aufgabe vor. Mit anderen Worten: Es hat eine Nebeneffekt, etwas, das man normalerweise in Listenverständnissen vermeiden kann. Es gibt jedoch einen Weg um das herum, als Paul weist darauf hin, dass durch die Verwendung random.sample. Der folgende Code zeigt zwei Einzeiler, die diese Funktionen verwenden (beachten Sie die Verwendung von not shuffle, um die Tatsache zu arbeiten, dass shuffle kehrt zurück 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]
Ich selbst, ich würde mit diesem gehen:
>>> 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]
Hier ist, wie Sie es mit O (n) Zeit und O (1) zusätzlicher Speicher machen:
Verständlicher Code:
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
Ein Einzeiler (annimmt "A" ist das Array):
n = a.length and (0..n - 2).each {|i| r = rand(n - i - 1) + i + 1; a[r], a[i] = a[i], a[r]}
Der Code ist in Ruby, aber ohne Zweifel ist er leicht in Python übersetzbar
Prost
PS: Die Lösung modifiziert das Array.
"Einzeiler" in fester o (n) Zeit:
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
Die Schleife wählt Elemente aus dem maximalen Index (Len (a) -1) bis zum nächsten kleinsten (1). Der Auswahlpool für Element K enthält nur Indizes von 0 bis K-1; Nach der Auswahl wird ein Element nicht wieder bewegt.
Nach dem Scramble kann sich kein Element in seiner ursprünglichen Position befinden, weil:
- Wenn Element J für einen Slot i> J ausgewählt wird, bleibt es dort
- Andernfalls wird Element J mit einem anderen Element aus Slot i getauscht
- Mit Ausnahme des Elements in Slot 0, das bedingungslos mit dem Element in Slot 1 (in der endgültigen Iteration der Schleife) ausgetauscht wird, wenn es noch nicht verschoben wurde.
Bearbeiten: Dies entspricht der Ruby -Antwort logischerweise, denke ich
Dieser ist o (n). Der Import in den Loops zu haben ist etwas albern, aber Sie wollten einen Einkaser -Liner
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
Hier ist die Ausgangsverteilung, wenn L = Bereich (5) für 100000 Proben
((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)
Mein erstes Python -Programm seit langer Zeit. Im Gegensatz zu vielen der oben genannten Programme nimmt dieser o (n) Zeit.
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
AKTUALISIEREN: Paul zeigte, dass das obige Programm falsch war. Danke, Paul. Hier ist eine andere, bessere Version desselben Programms:
s = range(10)
for i in range(9):
r = random.randrange(i+1, 10)
s[i], s[r] = s[r], s[i]
print s
Tut mir leid, dass dies kein Einzeiler ist, aber das funktioniert
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
Prost
import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)
(OK, ich habe dort auch eine Zeile 0 ...)
Für einen 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 ist die Umkehrung der Funktion v, Also v[u[i]+1] ist effektiv das Element nach I in Array v.
Hier ist die kreisförmige Verschiebung von Stephan202 als Ein-Liner mit einem zufällig ausgewählten Verschiebungsinkrement:
from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
