代码之家 › 专栏 › 技术社区 › Daniel

打印包含n个元素的集合的所有组合,在包含j个元素的子集之间拆分,同时保留字母顺序

combinatorics permutation sorting arrays python

Daniel · 技术社区 · 6 年前

假设我有一个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个元素的集合,但这当然只给出了两个子集的置换,也只给出了这两个子集的一个置换。它也没有在子集内保持字母顺序。

1 回复 | 直到 6 年前

Prune 6 年前

首先,请注意设置没有隐式排序:在Python中没有,在集合代数中也没有。

我建议你从一个困难的角度来解决这个问题。与其从C(8,3)的可能性中准确地找到你想要的排列,为什么不呢生成你想要的,就不要了?

从空的子列表开始。重复3^3种可能性,将每个字母放在指定的子列表中。对子列表排序并打印。

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

是的,这是蛮力。简化(例如,参见 itertools.product )留给读者作为练习。:-)