在 Python 中设置带约束的分区

Question

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

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

组内顺序无所谓。例如，[(0, 1, 2, 3), (4, 5, 6), (7, 8, 9)] 将被视为与 [(3, 0, 1, 2), (5, 6, 4), (7, 8, 9)]。
我想让 (1, 2, 3) 始终在同一组中，(7, 8) 也是如此。

如何列出所有符合上述条件的可能分组场景？非常感谢！

我正在使用 Python 2.7.

Answer 1

如果我对你的问题理解正确，这应该可以满足你的要求：

from copy import deepcopy

# slice into appropriate chunks
def slice_lst(size_tup, lst):
  for index, length in enumerate(size_tup):
    running_total = sum(size_tup[:index])
    yield lst[running_total:running_total+length]

# perform integer partition
def integer_partition(num):
  return {(x,) + y for x in range(1, num) for y in integer_partition(num-x)} | {(num,)}

# create all partitions given the starting list
def subsets(lst):
  for partition in integer_partition(len(lst)):
    yield list(slice_lst(partition, deepcopy(lst)))

# check that 1,2 and 3 are always contained within the same subset
def triplet_case(lst):
  bool_arr = [1 in lst, 2 in lst, 3 in lst]
  return all(bool_arr) or not any (bool_arr)

# check that 7 and 8 are always contained within the same subset
def duplet_case(lst):
  bool_arr = [7 in lst, 8 in lst]
  return all(bool_arr) or not any(bool_arr)

for subset in subsets([1,2,3,4,5,6,7,8,9]):
  if all([triplet_case(s) for s in subset]) and all([duplet_case(s) for s in subset]):
    print subset

如有任何后续问题，请随时提出！

Answer 2

For comb in combination k=3 in (0,4,5,6,9), remaining a, b:
(g1+a, g2+b, comb)    (g1+b, g2+a, comb)
(g2+a+b, g3, g1)

For comb in combination k=4 in (0,4,5,6,9), remaining a:
(comb, g1, g2+a)

from itertools import combinations, permutations

def partition_generator():
  wildcards = (0,4,5,6,9)
  g1, g2 = (1,2,3), (7,8)
  for comb in combinations(wildcards, 3):
    unused = remaining(wildcards, comb)
    for r in permutations(unused):
      yield part(g1, g2, comb, r)
    yield part(g2, g1, comb, unused)
  for comb in combinations(wildcards, 4):
    yield part(comb, g1, g2, remaining(wildcards, comb))

def remaining(a, b):
  return [ x for x in a if x not in b ]

def part(x,y,z,remaining):
  q = list(remaining)
  while len(x) < 4:
    x = x + (q.pop(0),)
  if len(y) < 3:
    y = y + (q.pop(0),)
  if len(z) < 3:
    z = z + (q.pop(0),)
  return (x,y,z)

>>> for partition in partition_generator():
...   print(partition)
...
((1, 2, 3, 6), (7, 8, 9), (0, 4, 5))
((1, 2, 3, 9), (7, 8, 6), (0, 4, 5))
((7, 8, 6, 9), (1, 2, 3), (0, 4, 5))
((1, 2, 3, 5), (7, 8, 9), (0, 4, 6))
((1, 2, 3, 9), (7, 8, 5), (0, 4, 6))
((7, 8, 5, 9), (1, 2, 3), (0, 4, 6))
((1, 2, 3, 5), (7, 8, 6), (0, 4, 9))
((1, 2, 3, 6), (7, 8, 5), (0, 4, 9))
((7, 8, 5, 6), (1, 2, 3), (0, 4, 9))
((1, 2, 3, 4), (7, 8, 9), (0, 5, 6))
((1, 2, 3, 9), (7, 8, 4), (0, 5, 6))
((7, 8, 4, 9), (1, 2, 3), (0, 5, 6))
((1, 2, 3, 4), (7, 8, 6), (0, 5, 9))
((1, 2, 3, 6), (7, 8, 4), (0, 5, 9))
((7, 8, 4, 6), (1, 2, 3), (0, 5, 9))
((1, 2, 3, 4), (7, 8, 5), (0, 6, 9))
((1, 2, 3, 5), (7, 8, 4), (0, 6, 9))
((7, 8, 4, 5), (1, 2, 3), (0, 6, 9))
((1, 2, 3, 0), (7, 8, 9), (4, 5, 6))
((1, 2, 3, 9), (7, 8, 0), (4, 5, 6))
((7, 8, 0, 9), (1, 2, 3), (4, 5, 6))
((1, 2, 3, 0), (7, 8, 6), (4, 5, 9))
((1, 2, 3, 6), (7, 8, 0), (4, 5, 9))
((7, 8, 0, 6), (1, 2, 3), (4, 5, 9))
((1, 2, 3, 0), (7, 8, 5), (4, 6, 9))
((1, 2, 3, 5), (7, 8, 0), (4, 6, 9))
((7, 8, 0, 5), (1, 2, 3), (4, 6, 9))
((1, 2, 3, 0), (7, 8, 4), (5, 6, 9))
((1, 2, 3, 4), (7, 8, 0), (5, 6, 9))
((7, 8, 0, 4), (1, 2, 3), (5, 6, 9))
((0, 4, 5, 6), (1, 2, 3), (7, 8, 9))
((0, 4, 5, 9), (1, 2, 3), (7, 8, 6))
((0, 4, 6, 9), (1, 2, 3), (7, 8, 5))
((0, 5, 6, 9), (1, 2, 3), (7, 8, 4))
((4, 5, 6, 9), (1, 2, 3), (7, 8, 0))

Answer 3

所以你想分成 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）

案例一

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

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

案例二

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

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

案例三

来自 (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])]

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

在 Python 中设置带约束的分区

Set partition with constraints in Python

python

constraints

partition

案例一

案例二

案例三