Сгенерируйте все перестановки, где длина перестановки & gt; # элементов в Python
Библиотека коллекций Scala предоставляет специализированные реализации для наборов из менее 5 значений (см. источник ). Итераторы для этих реализаций возвращают элементы в том порядке, в котором они были добавлены , а не в согласованном порядке на основе хешей, используемом для больших наборов.
Кроме того, sameElements ( scaladoc ) определен на Iterable s (он реализован в IterableLike - см. источник ); он возвращает true, только если итераторы возвращают одни и те же элементы в одном порядке.
Итак, хотя Set(1,2,3) и Set(3,2,1) должны быть эквивалентными, их итераторы различны, поэтому sameElements возвращает false.
Такое поведение является неожиданным и, возможно, является ошибкой, поскольку оно нарушает математические ожидания для Set (но только для определенных размеров Set!).
As И.К. указывает на комментарии, == отлично работает, если вы просто сравниваете Sets друг с другом, то есть Set(1,2,3) == Set(3,2,1). Однако sameElements является более общим в том смысле, что он может сравнивать элементы любых двух итераций. Например, List(1, 2, 3) == Array(1, 2, 3) является ложным, но List(1, 2, 3) sameElements Array(1, 2, 3) является истинным.
В более общем плане, равенство может сбивать с толку - обратите внимание, что:
List(1,2,3) == Vector(1,2,3)
List(1,2,3) != Set(1,2,3)
List(1,2,3) != Array(1,2,3)
Array(1,2,3) != Array(1,2,3)
У меня есть отправлено fix для упражнений Scala , которые объясняют проблему sameElements.
5 ответов
Вы можете создать рекурсивную функцию:
def group(d, current = [], in_place = [None, 3]):
need, _occurs = in_place
if len(current) == 5 and current.count(need) == _occurs:
yield current
else:
for i in d:
_c = current+[i]
if len(_c) <= 5 and _c.count(need) <= _occurs:
yield from group(d, current = _c)
Выход:
[[None, None, None, 0, 0], [None, None, None, 0, 1], [None, None, None, 0, 2], [None, None, None, 1, 0], [None, None, None, 1, 1], [None, None, None, 1, 2], [None, None, None, 2, 0], [None, None, None, 2, 1], [None, None, None, 2, 2], [None, None, 0, None, 0], [None, None, 0, None, 1], [None, None, 0, None, 2], [None, None, 0, 0, None], [None, None, 0, 1, None], [None, None, 0, 2, None], [None, None, 1, None, 0], [None, None, 1, None, 1], [None, None, 1, None, 2], [None, None, 1, 0, None], [None, None, 1, 1, None], [None, None, 1, 2, None], [None, None, 2, None, 0], [None, None, 2, None, 1], [None, None, 2, None, 2], [None, None, 2, 0, None], [None, None, 2, 1, None], [None, None, 2, 2, None], [None, 0, None, None, 0], [None, 0, None, None, 1], [None, 0, None, None, 2], [None, 0, None, 0, None], [None, 0, None, 1, None], [None, 0, None, 2, None], [None, 0, 0, None, None], [None, 0, 1, None, None], [None, 0, 2, None, None], [None, 1, None, None, 0], [None, 1, None, None, 1], [None, 1, None, None, 2], [None, 1, None, 0, None], [None, 1, None, 1, None], [None, 1, None, 2, None], [None, 1, 0, None, None], [None, 1, 1, None, None], [None, 1, 2, None, None], [None, 2, None, None, 0], [None, 2, None, None, 1], [None, 2, None, None, 2], [None, 2, None, 0, None], [None, 2, None, 1, None], [None, 2, None, 2, None], [None, 2, 0, None, None], [None, 2, 1, None, None], [None, 2, 2, None, None], [0, None, None, None, 0], [0, None, None, None, 1], [0, None, None, None, 2], [0, None, None, 0, None], [0, None, None, 1, None], [0, None, None, 2, None], [0, None, 0, None, None], [0, None, 1, None, None], [0, None, 2, None, None], [0, 0, None, None, None], [0, 1, None, None, None], [0, 2, None, None, None], [1, None, None, None, 0], [1, None, None, None, 1], [1, None, None, None, 2], [1, None, None, 0, None], [1, None, None, 1, None], [1, None, None, 2, None], [1, None, 0, None, None], [1, None, 1, None, None], [1, None, 2, None, None], [1, 0, None, None, None], [1, 1, None, None, None], [1, 2, None, None, None], [2, None, None, None, 0], [2, None, None, None, 1], [2, None, None, None, 2], [2, None, None, 0, None], [2, None, None, 1, None], [2, None, None, 2, None], [2, None, 0, None, None], [2, None, 1, None, None], [2, None, 2, None, None], [2, 0, None, None, None], [2, 1, None, None, None], [2, 2, None, None, None]]
-
1Не перестановки без дублирования? Является, например, [None, None, None, 0, 0] valid (я имею в виду номера в этом случае)? – Andrej Kesely 13 July 2018 в 18:21
-
2@AndrejKesely В математике перестановки должны включать все элементы. То, что хочет автор, уже не является перестановкой. Тогда вопрос в том, чего он действительно хочет ... – btilly 13 July 2018 в 18:38
-
3@AndrejKesely: [Нет, Нет, Нет, 0, 0]. На самом деле не знали, что перестановки без дублирования (вероятно, поэтому я должен был положить три Nones и два 0s, 1s и 2s в список элементов, чтобы сделать «перестановки» из). – tien 13 July 2018 в 18:56
-
4@tien Хорошо, я был в замешательстве, мне нужно изменить свой ответ. – Andrej Kesely 13 July 2018 в 19:04
from itertools import product
elemets = [None, 0, 1, 2]
l = product(elemets, repeat=5)
s = set(p for p in l if p.count(None) == 3)
print(s)
Выход:
{(None, None, None, 0, 2), (None, None, 0, None, 2), (1, 2, None, None, None), (0, None, None, 1, None), (1, None, 2, None, None), (1, None, None, 2, None), (None, 2, 1, None, None), (None, None, None, 2, 1), (None, None, 2, None, 1), (None, None, None, 1, 1), (None, 0, None, 0, None), (None, 0, 0, None, None), (None, 1, None, None, 1), (2, 1, None, None, None), (2, None, None, 1, None), (None, 0, None, None, 1), (None, 0, None, 1, None), (0, None, None, 0, None), (0, None, 0, None, None), (None, None, 1, 1, None), (1, None, None, 1, None), (2, None, None, 2, None), (2, None, 2, None, None), (None, None, 2, None, 0), (None, None, None, 2, 0), (None, None, None, 1, 2), (0, 0, None, None, None), (None, 0, None, None, 0), (2, 0, None, None, None), (None, None, 0, 1, None), (None, None, 1, 2, None), (None, 0, None, 2, None), (None, 0, 2, None, None), (0, 1, None, None, None), (None, 2, None, 2, None), (None, 2, 2, None, None), (None, 1, None, 1, None), (None, None, 1, None, 0), (2, None, None, None, 2), (2, 2, None, None, None), (2, None, None, 0, None), (2, None, 0, None, None), (None, 1, None, 2, None), (None, 1, 2, None, None), (0, None, 1, None, None), (0, None, None, None, 1), (None, None, None, 0, 1), (None, None, 0, None, 1), (None, 2, None, 1, None), (None, 0, None, None, 2), (None, None, 1, None, 1), (2, None, 1, None, None), (2, None, None, None, 1), (None, None, 0, 2, None), (1, None, None, None, 0), (None, 1, None, None, 2), (None, 0, 1, None, None), (0, None, None, None, 2), (None, 2, None, None, 2), (0, None, None, None, 0), (None, None, 0, 0, None), (None, None, 2, 2, None), (None, None, None, 0, 0), (None, None, 0, None, 0), (None, 2, None, 0, None), (None, 2, 0, None, None), (1, None, 1, None, None), (None, None, 1, None, 2), (2, None, None, None, 0), (0, 2, None, None, None), (1, None, None, 0, None), (1, None, None, None, 1), (1, None, 0, None, None), (None, None, 1, 0, None), (None, 1, None, 0, None), (None, 1, 0, None, None), (None, None, 2, 1, None), (None, 2, None, None, 1), (1, 1, None, None, None), (None, None, None, 2, 2), (1, None, None, None, 2), (0, None, None, 2, None), (0, None, 2, None, None), (None, 1, 1, None, None), (None, None, None, 1, 0), (None, None, 2, None, 2), (None, 1, None, None, 0), (None, None, 2, 0, None), (1, 0, None, None, None), (None, 2, None, None, 0)}
Предполагая (из вывода вашего кода и того факта, что вы намеренно добавили несколько копий 0, 1 и 2), что вы делаете «перестановки с заменой» или в основном декартовский продукт с требованием 3 Nones, я 'd сделайте что-то вроде:
def tien_gen(size, values, number_of_nones):
to_fill = size - number_of_nones
for locs in itertools.combinations(range(size), to_fill):
for fill_values in itertools.product(values, repeat=to_fill):
out = [None] * size
for loc, fill_value in zip(locs, fill_values):
out[loc] = fill_value
yield tuple(out)
, которое соответствует вашему выходу:
In [137]: result = list(tien_gen(5, [0,1,2], 3))
In [138]: len(result)
Out[138]: 90
In [139]: result
Out[139]:
[(0, 0, None, None, None),
(0, 1, None, None, None),
(0, 2, None, None, None),
(1, 0, None, None, None),
[...]
(None, 0, None, 1, None),
(None, 0, None, 2, None),
(None, 1, None, 0, None),
[...]
(None, 2, None, 1, None),
(None, 2, None, 2, None),
(None, 0, None, None, 0),
(None, 0, None, None, 1),
[...]
(None, None, None, 1, 2),
(None, None, None, 2, 0),
(None, None, None, 2, 1),
(None, None, None, 2, 2)]
In [140]: orig = [state for state in list(set(it.permutations((None, None, None, 0, 0, 1, 1, 2, 2), 5))) if state.count(None)==3]
In [141]: len(result) == len(orig) and set(result) == set(orig)
Out[141]: True
Для небольших размеров преимущества ограничены, но для более крупных, таким образом, вы избегаете создания каких-либо кортеж, который вы не используете, и поскольку это генератор, вам не нужно их материализовывать, если вы этого не хотите.
Вот как я подходил бы к нему, если бы я действительно не хотел генерировать и отфильтровывать кучу несоответствующих записей:
Вам нужно от 0 до 3 None s (назовите это число n1 ]), за которым следует один элемент не None из списка, за которым следует 0 - 3 n1 None s (n2), за которым следует второй элемент [[8]] из списка. 3 n1 - n2 None s.
states = []
for (i1, i2) in permutations((0,1,2), 2):
for n1 in range(4):
for n2 in range(4-n1):
states.append((None,)*n1 + (i1,) + (None,)*n2 + (i2,) + (None,)*(3-n1-n2))
Понятно, что самый простой «эффективный» алгоритм можно объяснить следующим образом: сначала сгенерируйте перестановки длины 2. Затем вставьте 3 экземпляра None всеми возможными способами.
Однако, это более эффективен: во-первых, сгенерируйте все индексы, в которых вы хотите, чтобы ваши два элемента были. Затем для каждого набора индексов для каждой перестановки длины 2 подставляем эти элементы в заданные индексы.
from itertools import combinations, permutations, product
base_list = [None] * 5
values = [0, 1, 2]
all_indices = combinations(range(5), 2)
all_perms = permutations(values, 2)
for (i, j), (x, y) in product(all_indices, all_perms):
list_copy = base_list[:]
list_copy[i] = x
list_copy[j] = y
print(list_copy)
# [0, 1, None, None, None]
# [0, 2, None, None, None]
# ...
# [None, None, None, 2, 0]
# [None, None, None, 2, 1]
Это должно быть легко расширяемым для входов различной длины.
def inserted_permutations(size, values, insert_count, default=None):
base = [default] * size
all_indices = combinations(range(size), insert_count)
all_perms = permutations(values, insert_count)
for indices, values in product(all_indices, all_perms):
base_copy = base[:]
for index, value in zip(indices, values):
base_copy[index] = value
yield base_copy