Python 生成所有可能的字母模式列表

其中一条来自@JacobRR的 comments 非常接近我们的需要.每个"模式"实际上对应于将集合{1，2，…，N}划分为K个子集.每个子集(甚至为空！)对应字母l\u k应放置的位置(l\u 1=A，l\u 2=B等).这里有一个演示.

例如，在K=3，N=3的情况下，分区将是

{1,2,3}, ∅, ∅
{1}, {2, 3}, ∅
{2}, {1, 3}, ∅
{3}, {1, 2}, ∅
{1}, {2}, {3}

对于K=2，N=3，它是

{1,2,3}, ∅
{1}, {2, 3}
{2}, {1, 3}
{3}, {1, 2}

与给定示例完全对应.

这个问题也是相关的.

https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions

我还编写了自己的天真实现.

import copy

N = 3
K = 2

iter = min(N, K)

def partitions(S, K):

    if K == 1:
        return [[S]]
    if len(S) == 0:
        return [[]]
    
    result = []
    S_new = copy.copy(S)
    first = S_new.pop(0)
    
    if (K-1 <= len(S_new)):
        p1 = partitions(S_new, K-1)
        for p in p1:
            p.append([first])
            result.append(p)
    if (K <= len(S_new)):
        p2 = partitions(S_new, K)

        for p in p2:
            for idx in range(len(p)):
                p_new = copy.deepcopy(p)
                p_new[idx].append(first)
                result.append(p_new)
                
        
    return result

for idx in range(1, iter+1):
    print(partitions([i for i in range(0, N)], idx))