在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 的块，其中 (1,2,3) 位于一个块中，(7,8) 位于一个块中。

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

我们先忘记键盘，来分析问题

恕我直言，你应该区分 3 种情况：

• 1,2,3 位于大小为 4 的块中（情况 1）
• 7,8 位于大小为 4 的块中（情况 2）
• 既不是 1,2,3 也不是 7,8 并且在大小为 4 的块中（情况 3）

情况1

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

总计：5*4 = 20 个不同的分区

案例2

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

总计：5*4/2 = 10 个不同的分区（/2 因为您需要组合而不是排列）

案例3

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

总计：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])]

（手动格式化以方便阅读......）