Python中带约束的集合划分

2024-03-29 07:04:58 发布

您现在位置:Python中文网/ 问答频道 /正文

我很难处理组划分问题。会有人掉吗 请给我点灯?在

让我简化一下我的问题。我想除以十个数(即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)也是如此。

如何列出符合上述条件的所有可能的分组方案?谢谢!在

我使用的是python2.7。在


Tags: 顺序方案数字条件组内点灯
3条回答

所以你需要划分为3个大小为4,3,3的块,其中(1,2,3)在一个块中,(7,8)在一个块中。在

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

先忘了键盘,分析一下问题

IMHO,你应该分开三个案例:

  • 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

你得到的是:

^{pr2}$

(手动格式化以便于阅读…)

如果我正确地理解了您的问题,这应该符合您的要求:

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

如果您有任何后续问题,请随时提出!在

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)

^{pr2}$

>>> 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))

和13;
和13;

相关问题 更多 >