python - 在 Python 中设置带约束的分区

Question

我很难处理组分区问题。会不会有人掉 请给我点灯好吗？

让我简化一下我的问题。我想除以十个数字(即 0, 1, ..., 9) 分成三组，每组有 (4, 3, 3) 个数字。条件是:

1. 组内顺序无关紧要。例如，[(0, 1, 2, 3), (4, 5, 6), (7, 8, 9)] 将被视为与 [(3, 0, 1, 2), (5, 6, 4), (7, 8, 9)]。

2. 我想让 (1, 2, 3) 始终在同一组中，(7, 8) 也是如此。

如何列出所有满足上述条件的可能分组场景？非常感谢!

我正在使用 Python 2.7。

Answer 1

所以你想分成 3 个大小为 4、3、3 的 block ，其中 (1,2,3) 在一个 block 中，(7,8) 在一个 block 中。

这意味着 1,2,3 和 7,8 不能在同一个 block 中。

先忘掉键盘再分析问题

恕我直言，您应该将 3 个案例分开:

• 1,2,3 在大小为 4 的 block 中(情况 1)
• 7,8 在大小为 4 的 block 中(案例 2)
• 既不是 1,2,3 也不是 7,8，并且在大小为 4 的 block 中(情况 3)

案例一

• 来自 (0,4,5,6,9) 的一个元素进入包含 (1, 2, 3) 的 block
• 来自 (0,4,5,6,9) 的另一个元素进入包含 (7,8) 的 block

总共:5*4 = 20 个不同的分区

案例2

• 来自 (0,4,5,6,9) 的两个元素进入包含 (7,8) 的 block

总计:5*4/2 = 10 个不同的分区(/2 因为你想要组合而不是排列)

案例3

• 来自 (0,4,5,6,9) 的一个元素进入包含 (7,8) 的 block

总共:5 个不同的分区

所以你知道你应该有 35 个不同的分区

Python 代码:

def gen():
    B1 = [1,2,3]
    B2 = [7,8]
    C = [x for x in range(10) if x not in B1 + B2 ]
    def gen1():
        for x in C:
            c = C[:]
            b1 = B1[:]
            b1.append(x)
            c.remove(x)
            for y in c:
                c1 = c[:]
                b2 = B2[:]
                b2.append(y)
                c1.remove(y)
                yield(b1, b2, c1)
    def gen2():
        for i in range(len(C)-1):
            for j in range(i+1, len(C)):
                b2 = B2 + [C[i], C[j]]
                c = [C[k] for k in range(len(C)) if k not in (i,j)]
                yield (B1, b2, c)
    def gen3():
        for x in C:
            b2 = B2[:]
            c = C[:]
            c.remove(x)
            b2.append(x)
            yield(B1, b2, c)
    for g in (gen1, gen2, gen3):
        for t in g():
            yield t

你得到正确的:

>>> list(gen())
[([1, 2, 3, 0], [7, 8, 4], [5, 6, 9]), ([1, 2, 3, 0], [7, 8, 5], [4, 6, 9]),
 ([1, 2, 3, 0], [7, 8, 6], [4, 5, 9]), ([1, 2, 3, 0], [7, 8, 9], [4, 5, 6]),
 ([1, 2, 3, 4], [7, 8, 0], [5, 6, 9]), ([1, 2, 3, 4], [7, 8, 5], [0, 6, 9]),
 ([1, 2, 3, 4], [7, 8, 6], [0, 5, 9]), ([1, 2, 3, 4], [7, 8, 9], [0, 5, 6]),
 ([1, 2, 3, 5], [7, 8, 0], [4, 6, 9]), ([1, 2, 3, 5], [7, 8, 4], [0, 6, 9]),
 ([1, 2, 3, 5], [7, 8, 6], [0, 4, 9]), ([1, 2, 3, 5], [7, 8, 9], [0, 4, 6]),
 ([1, 2, 3, 6], [7, 8, 0], [4, 5, 9]), ([1, 2, 3, 6], [7, 8, 4], [0, 5, 9]),
 ([1, 2, 3, 6], [7, 8, 5], [0, 4, 9]), ([1, 2, 3, 6], [7, 8, 9], [0, 4, 5]),
 ([1, 2, 3, 9], [7, 8, 0], [4, 5, 6]), ([1, 2, 3, 9], [7, 8, 4], [0, 5, 6]),
 ([1, 2, 3, 9], [7, 8, 5], [0, 4, 6]), ([1, 2, 3, 9], [7, 8, 6], [0, 4, 5]),
 ([1, 2, 3], [7, 8, 0, 4], [5, 6, 9]), ([1, 2, 3], [7, 8, 0, 5], [4, 6, 9]),
 ([1, 2, 3], [7, 8, 0, 6], [4, 5, 9]), ([1, 2, 3], [7, 8, 0, 9], [4, 5, 6]),
 ([1, 2, 3], [7, 8, 4, 5], [0, 6, 9]), ([1, 2, 3], [7, 8, 4, 6], [0, 5, 9]),
 ([1, 2, 3], [7, 8, 4, 9], [0, 5, 6]), ([1, 2, 3], [7, 8, 5, 6], [0, 4, 9]),
 ([1, 2, 3], [7, 8, 5, 9], [0, 4, 6]), ([1, 2, 3], [7, 8, 6, 9], [0, 4, 5]),
 ([1, 2, 3], [7, 8, 0], [4, 5, 6, 9]), ([1, 2, 3], [7, 8, 4], [0, 5, 6, 9]),
 ([1, 2, 3], [7, 8, 5], [0, 4, 6, 9]), ([1, 2, 3], [7, 8, 6], [0, 4, 5, 9]),
 ([1, 2, 3], [7, 8, 9], [0, 4, 5, 6])]

(手动格式化以方便阅读...)