программа скремблирования oneliner
https://stackoverflow.com/questions/1735561
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Это снова то время года, когда программисты хотят перетасовать список таким образом, чтобы ни один элемент не находился на своем исходном месте (по крайней мере, в Нидерландах мы отмечаем Sinterklaas и подбирайте соломинки, чтобы решить, кто кому напишет стихотворение).У кого-нибудь есть хороший Python одиночный оператор за это?
Итак, входной пример: range(10)
Пример вывода: [2,8,4,1,3,7,5,9,6,0]
Неправильный вывод был бы [2,8,4,1,3,5,7,9,6,0] потому что 5 находится в своем исходном положении.Это означало бы, что человек 5 должен написать стихотворение самому себе, а это менее весело.
Редактировать Многие люди повторяют задание ровно столько, сколько необходимо для будь счастливчиком и обнаружите, что на самом деле решение является удовлетворительным.Это плохой подход, так как теоретически это может занять бесконечно много времени.Лучший подход действительно предложен Бартом, но я не могу включить его в oneliner по той или иной причине...
Редактировать Под oneliner я подразумеваю одиночный оператор.Как представляется, Python также способен сжимать несколько операторов в одной строке.Я этого не знал.В настоящее время существуют очень хорошие решения, использующие точку с запятой только для имитации многострочного поведения в одной строке.Следовательно:"вы можете сделать это в одном заявлении?"
Решение
Я обнаружил, что shuffle можно использовать для решения этой проблемы
from random import shuffle
L = ["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, int=lambda n: int(n - 1))
print L
Распределение неравномерно, однако это не было обязательным требованием.
#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)
Для равномерного распространения можно использовать эту (более длинную) версию
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)
Как это работает
Вот код для 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]
Оба решения работают, ориентируясь на линию j = int(random() * (i+1))
Первый (неравномерный) эффективно заставляет линию работать следующим образом
j = int(random() * (i + 1) - 1)
Таким образом, вместо диапазона (1..i) мы получаем (0..i-1)
Второе решение заменяет random() с функцией, которая всегда возвращает 1 и использует randint вместо того , чтобы int.Итак, линия теперь работает следующим образом
j = randint(0, i - 1)
Другие советы
После перетасовки списка чисел позвольте [i]этот человек напишет стихотворение (и купит подарок!) для [i+1]й человек в списке:таким образом, никогда не может быть того, кто рисует себя.Конечно, последнее должно указывать на первое...
Циклический сдвиг каждого элемента в списке на единицу, как предложил Барт, легко:
>>> def shift(seq):
... return seq[-1:] + seq[:-1]
...
>>> shift(range(10))
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
Что касается случайного решения:в этом случае запрос на однострочник не такая уж хорошая идея, поскольку очевидная функция для использования, а именно random.shuffle, выполняет свою задачу на месте.Другими словами:в нем есть побочный эффект, чего обычно пытаются избежать при понимании списка.Однако есть способ обойти это, поскольку Пол указывает, а именно, используя random.sample.Следующий код показывает две однострочные версии, которые используют эти функции (обратите внимание на использование not shuffle, чтобы обойти тот факт , что shuffle ВОЗВРАТ 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]
Лично я бы выбрал этот вариант:
>>> 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]
Вот как вы делаете это с O (n) временем и O (1) дополнительной памятью:
Понятный код:
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
Однострочный (предполагается, что "a" - это массив):
n = a.length and (0..n - 2).each {|i| r = rand(n - i - 1) + i + 1; a[r], a[i] = a[i], a[r]}
Код написан на ruby, но, без всякого сомнения, его легко перевести на python
Ваше здоровье
P.S.:Решение изменяет массив.
"Однострочный" в фиксированное время 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
Цикл выбирает элементы от максимального индекса (len(a)-1) до следующего по величине (1).Пул выбора для элемента k включает только индексы от 0 до k-1;после выбора элемент больше не будет перемещен.
После скремблирования ни один элемент не может находиться в своем исходном положении, потому что:
- если элемент j выбран для некоторого слота i> j, он останется там
- в противном случае элемент j будет заменен каким-либо другим элементом из слота i
- за исключением элемента в слоте 0, который будет безоговорочно заменен элементом в слоте 1 (на последней итерации цикла), если он еще не был перемещен.
[править:я думаю, это логически эквивалентно ответу Ruby]
Этот - O (N).Иметь импорт в циклах немного глупо, но вы хотели однострочный
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
Вот распределение выходных данных при L = range (5) для 100000 выборок
((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)
Моя первая программа на Python за долгое время.В отличие от многих из вышеперечисленных программ, эта занимает 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
Обновить:Пол показал, что приведенная выше программа была неверной.Спасибо, Пол.Вот другая, улучшенная версия той же программы:
s = range(10)
for i in range(9):
r = random.randrange(i+1, 10)
s[i], s[r] = s[r], s[i]
print s
Извините, что это не однострочник, но это работает
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
Ваше здоровье
import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)
(Хорошо, у меня там тоже есть строка 0 ...)
Для одного в 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 является обратной функцией v, так что v[u[i]+1] фактически является элементом, следующим за i в массиве v.
Вот циклический сдвиг Stephan202, реализованный как однострочный с произвольно выбранным шагом сдвига:
from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
