Сгенерируйте все возможные перестановки подмножеств, содержащих все элементы набора

Пусть S (w) - набор слов. Я хочу сгенерировать все возможные n-комбинации подмножеств s, чтобы объединение этих подмножеств всегда было равно S (w).

Итак, у вас есть набор (a, b, c, d, e), и вам не нужны все 3 комбинации:

((a, b, c), (d), (e))

((a, b), (c, d), (e))

((a), (b, c, d), (e))

((a), (b, c), (d, e))

и т.д ...

Для каждой комбинации у вас есть 3 набора, и объединение этих наборов является исходным набором. Нет пустого набора, нет пропущенного элемента.

Должен быть способ сделать это с помощью itertools.combination + collection.Counter, но я даже не могу где-то начать ... Может кто-нибудь помочь?

Люк

РЕДАКТИРОВАТЬ: мне нужно было бы захватить все возможные комбинации, в том числе:

((a, e), (b, d) (c))

и т.д ...


python subset combinations powerset multiset
person Luke Skywalker    schedule 09.08.2013    source источник
comment
Здесь говорится, что вы можете использовать длину r, чтобы указать вас нужны комбинации размера r.   -  person squiguy    schedule 10.08.2013
comment
Да, но дает комбинацию отдельных элементов. Мне нужна комбинация наборов, включающая все мои элементы.   -  person Luke Skywalker    schedule 10.08.2013
comment
Чтобы уточнить: в решении Романа Пекара последний результат - (('e', 'd', 'c'), ('b',), ('a',)), а предпоследний результат - (('e', 'd', 'c'), ('a',), ('b',)). Вы этого хотели? Если это так, возможно, вам следует изменить заголовок на перестановки, а не на комбинации.   -  person Paulo Almeida    schedule 10.08.2013

Ответы (1)


arrow_upward
3
arrow_downward

что-то вроде этого?

from itertools import combinations, permutations
t = ('a', 'b', 'c', 'd', 'e')
slicer = [x for x in combinations(range(1, len(t)), 2)]
result = [(x[0:i], x[i:j], x[j:]) for i, j in slicer for x in permutations(t, len(t))]

общее решение для любого n и любой длины кортежа:

from itertools import combinations, permutations
t = ("a", "b", "c")
n = 2
slicer = [x for x in combinations(range(1, len(t)), n - 1)]
slicer = [(0,) + x + (len(t),) for x in slicer]
perm = list(permutations(t, len(t)))
result = [tuple(p[s[i]:s[i + 1]] for i in range(len(s) - 1)) for s in slicer for p in perm]

[
   (('a',), ('b', 'c')),
   (('a',), ('c', 'b')),
   (('b',), ('a', 'c')),
   (('b',), ('c', 'a')),
   (('c',), ('a', 'b')),
   (('c',), ('b', 'a')),
   (('a', 'b'), ('c',)),
   (('a', 'c'), ('b',)),
   (('b', 'a'), ('c',)),
   (('b', 'c'), ('a',)),
   (('c', 'a'), ('b',)),
   (('c', 'b'), ('a',))
]
person Roman Pekar    schedule 09.08.2013
comment
Хорошая, но этого не достаточно. Мне понадобится наборный срез (а не список), поэтому на срез не влияет порядок. Я отредактировал свой вопрос, чтобы было понятнее. - person Luke Skywalker; 10.08.2013
comment
Что я мог сделать, так это объединить ваш ответ с ответом Сквигуя. Сгенерируйте все различные комбинации и примените свой слайсер ... - person Luke Skywalker; 10.08.2013
comment
Вот и все ! Спасибо :) - person Luke Skywalker; 10.08.2013
comment
добавлено более общее решение - person Roman Pekar; 10.08.2013