программа схватки oneliner

Question

Это то время года, когда программисты хотят перетасовать список таким образом, чтобы ни один элемент не находился на своей первоначальной позиции (по крайней мере, в Нидерландах мы отмечаем 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 должен написать стихотворение самому себе, и это не так весело.

edit Многие люди повторяют задание столько раз, сколько необходимо, чтобы везет и считают, что на самом деле решение является удовлетворительным. Это плохой подход, так как в теории это может занять бесконечно много времени. Барт действительно предлагает лучший подход, но по той или иной причине я не могу понять это…

edit Под oneliner я подразумеваю отдельное утверждение . Как видно, Python также может сжимать несколько операторов в одной строке. Я этого не знал. В настоящее время есть очень хорошие решения, использующие только точку с запятой для имитации многострочного поведения в одной строке. Отсюда: «Вы можете сделать это в одном утверждении?»

Answer 1

Я обнаружил, что 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)

Answer 2

После перетасовки списка чисел, пусть [i] -й человек напишет стихотворение (и купит подарок!) Для [i+1] -ого человека в списке: таким образом, никогда не будет того, кто его рисует или сама. Конечно, последний должен указывать на первый ...

Answer 3

Сдвигая каждый элемент в списке по кругу, , как предложил Барт , легко:

>>> 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]

Answer 4

Это 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 = диапазон (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)

Answer 5

«Однострочник» в фиксированное время 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, я думаю]

Answer 6

Вот как вы делаете это с 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 .: Решение модифицирует массив.

Answer 7

Моя первая программа на 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

Answer 8

Вот круговой сдвиг Stephan202, реализованный в виде однострочного с произвольно выбранным шагом сдвига:

from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]

Answer 9

Для одного в 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.

Answer 10

import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)

(Хорошо, у меня тоже есть строка 0 ...)