Я хотел бы сделать случайную перетасовку списка, но с одним условием: элемент не может находиться в том же исходном положении после тасования.
Есть ли один способ сделать это в python для списка?
Пример:
list_ex = [1,2,3]
каждый из следующих перетасованных списков должен иметь такую же вероятность быть отбракованным после тасования:
list_ex_shuffled = [2,3,1]
list_ex_shuffled = [3,1,2]
но перестановки [1,2,3], [1,3,2], [2,1,3] и [3,2,1] недопустимы, поскольку все они повторяют одну из позиций элементов.
ПРИМЕЧАНИЕ. Каждый элемент в list_ex является уникальным идентификатором. Не допускается повторение одного и того же элемента.
Любые идеи? спасибо!
Рандомизируйте в цикле и продолжайте отклонять результаты до тех пор, пока ваше условие не будет удовлетворено:
import random
def shuffle_list(some_list):
randomized_list = some_list[:]
while True:
random.shuffle(randomized_list)
for a, b in zip(some_list, randomized_list):
if a == b:
break
else:
return randomized_list
Вы можете создать все возможные действительные перетасовки:
>>> list_ex = [1,2,3]
>>> import itertools
>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
... itertools.permutations(list_ex, len(list_ex))))
[(2, 3, 1), (3, 1, 2)]
Для некоторой другой последовательности:
>>> list_ex = [7,8,9,0]
>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
... itertools.permutations(list_ex, len(list_ex))))
[(8, 7, 0, 9), (8, 9, 0, 7), (8, 0, 7, 9), (9, 7, 0, 8), (9, 0, 7, 8), (9, 0, 8, 7), (0, 7, 8, 9), (0, 9, 7, 8), (0, 9, 8, 7)]
Вы также можете сделать это немного более эффективным, если коротко замыкать итератор, если вам нужен только один результат:
>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
... itertools.permutations(list_ex, len(list_ex)))
>>> next(i)
(2, 3, 1)
Но это не случайный выбор. Вам нужно будет сгенерировать все из них и выбрать один для фактического случайного результата:
>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
... itertools.permutations(list_ex, len(list_ex)))
>>> import random
>>> random.choice(list(i))
(2, 3, 1)
Я бы описал такие перетасовки как "перестановки без фиксированных точек". Они также известны как отклонения.
Вероятность того, что случайная перестановка является расстройством, составляет приблизительно 1/e (интересно доказать). Это верно, однако длинный список. Таким образом, очевидный алгоритм, чтобы дать случайное нарушение, состоит в том, чтобы перетасовать карты обычным образом и продолжать перетасовку, пока у вас не возникнет расстройство. Ожидаемое количество необходимых перетасовки - около 3, и вам редко приходится перетасовывать более десяти раз.
(1-1/e)**11 < 1%
Предположим, что на вечеринке есть русские люди, каждый из которых принес зонтик. В конце вечеринки каждый человек берет зонтик в случайном порядке из корзины. Какова вероятность того, что никто не держит свой собственный зонтик?
Вот еще один пример. Вы можете выбрать одно решение в зависимости от ваших потребностей. Это не один лайнер, а перетасовка индексов элементов, а не самих элементов. Таким образом, исходный список может иметь повторяющиеся значения или значения типов, которые не могут сравниться или могут быть дорогими для сравнения.
#! /usr/bin/env python
import random
def shuffled_values(data):
list_length = len(data)
candidate = range(list_length)
while True:
random.shuffle(candidate)
if not any(i==j for i,j in zip(candidate, range(list_length))):
yield [data[i] for i in candidate]
list_ex = [1, 2, 3]
list_gen = shuffled_values(list_ex)
for i in range(0, 10):
print list_gen.next()
Это дает:
[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[2, 3, 1]
[3, 1, 2]
[2, 3, 1]
Если list_ex - [2, 2, 2], этот метод будет продолжать приносить [2, 2, 2] снова и снова. Другие решения предоставят вам пустые списки. Я не уверен, что вы хотите в этом случае.
Вот еще один алгоритм. Возьмите карты в случайном порядке. Если ваша i-я карта - карта i, верните ее и повторите попытку. Только проблема, что, если, когда вы доберетесь до последней карты, это тот, который вам не нужен. Поменяйте его на один из других.
Я думаю, что это справедливо (равномерно случайное).
import random
def permutation_without_fixed_points(n):
if n == 1:
raise ArgumentError, "n must be greater than 1"
result = []
remaining = range(n)
i = 0
while remaining:
if remaining == [n-1]:
break
x = i
while x == i:
j = random.randrange(len(remaining))
x = remaining[j]
remaining.pop(j)
result.append(x)
i += 1
if remaining == [n-1]:
j = random.randrange(n-1)
result.append(result[j])
result[j] = n
return result