打印具有 n 个元素的集合的所有组合，这些元素在具有 j 个元素的子集之间拆分，同时保留字母顺序

Question

假设我有一个包含 n=3 个元素的集合：[a,b,c]

使用组合学我们知道这个集合有 8 个子集，其中包含 j 个元素：

[∅], [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c]

现在我想使用 Python 打印这 8 个子集的所有排列，限制是每个排列必须恰好有 3 个子集（空子集很好），所有元素必须使用，并且必须在每个子集内维护字母顺序（不需要在子集之外维护字母顺序——例如 [c],[a],[b] 就可以）。

我尝试过这样的事情：

x=1
y=3

for i in set(permutations(chain.from_iterable(set_n))):
    while x<=3:
        permuted = sorted([i[:y], i[x:]])
        x = x+1
        y = y-1

    print permuted

其中 set_n 是我的 n 个元素的集合，但这当然只给出了两个子集的排列，并且只给出了这两个子集的一个排列。它也不维护子集中的字母顺序。

Answer 1

首先，请注意集合没有隐式排序：不在 Python 中，不在集合代数中。

我建议你从一个困难的角度来解决这个问题。与其从 C(8,3) 可能性中准确找到您想要的排列，不如生成您想要的排列，仅此而已？

从空 sub-lists 开始。遍历 3^3 种可能性，将每个字母放在指示的 sub-list 中。对 sub-lists 进行排序并打印。

for ai in range(3):
    for bi in range(3):
        for ci in range(3):
            permute = [ [], [], [] ]
            permute[ai].append('a')    
            permute[bi].append('b')    
            permute[ci].append('c')
            print(permute)

输出：

[['a', 'b', 'c'], [], []]
[['a', 'b'], ['c'], []]
[['a', 'b'], [], ['c']]
[['a', 'c'], ['b'], []]
[['a'], ['b', 'c'], []]
[['a'], ['b'], ['c']]
[['a', 'c'], [], ['b']]
[['a'], ['c'], ['b']]
[['a'], [], ['b', 'c']]
[['b', 'c'], ['a'], []]
[['b'], ['a', 'c'], []]
[['b'], ['a'], ['c']]
[['c'], ['a', 'b'], []]
[[], ['a', 'b', 'c'], []]
[[], ['a', 'b'], ['c']]
[['c'], ['a'], ['b']]
[[], ['a', 'c'], ['b']]
[[], ['a'], ['b', 'c']]
[['b', 'c'], [], ['a']]
[['b'], ['c'], ['a']]
[['b'], [], ['a', 'c']]
[['c'], ['b'], ['a']]
[[], ['b', 'c'], ['a']]
[[], ['b'], ['a', 'c']]
[['c'], [], ['a', 'b']]
[[], ['c'], ['a', 'b']]
[[], [], ['a', 'b', 'c']]

是的，这是 brute-force。简化（例如参见 [=12=]）留作 reader 的练习。 :-)

打印具有 n 个元素的集合的所有组合，这些元素在具有 j 个元素的子集之间拆分，同时保留字母顺序

Print all combinations of a set with n elements split between subsets with j elements while retaining alphabetical order

python

arrays

sorting

permutation

combinatorics