生成包含集合中所有元素的子集的所有可能排列 [英] Generate all possible permutations of subsets containing all the element of a set

问题描述

让S(w)为一组单词.我想生成子集s的所有可能的n组合，以便这些子集的并集始终等于S(w).

Let S(w) be a set of words. I want to generate all the possible n-combination of subsets s so that the union of those subsets are always equal to S(w).

因此，您有一组(a，b，c，d，e)，并且不需要所有3种组合:

So you have a set (a, b, c, d, e) and you wan't all the 3-combinations:

(((a，b，c)，(d)，(e))

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

(((a，b)，(c，d)，(e))

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

(((a)，(b，c，d)，(e))

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

(((a)，(b，c)，(d，e))

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

等...

对于每个组合，您有3个组合，这些组合的并集是原始组合.没有空集，没有丢失的元素.

For each combination you have 3 set and the union of those set is the original set. No empty set, no missing element.

一定有一种使用itertools.combination + collection.Counter来做到这一点的方法，但我什至无法从某处开始... 有人可以帮忙吗?

There must be a way to do that using itertools.combination + collection.Counter but I can't even start somewhere... Can someone help ?

卢克

我需要捕获所有可能的组合，包括:

I would need to capture all the possible combination, including:

(((a，e)，(b，d)(c))

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

等...

推荐答案

类似的东西?

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和任何元组长度:

general solution, for any n and any tuple length:

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',))
]

这篇关于生成包含集合中所有元素的子集的所有可能排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！