具有给定约束的分区数

Question

考虑一组 13 名丹麦人、11 名日本人和 8 名波兰人。众所周知，这组人分组的不同方式的个数是第13+11+8=32:th贝尔数（集合分区数）。然而，我们被要求找到在给定约束下可能的集合分区的数量。题目如下：

一个集合分区被认为是好如果它没有由至少两个人组成的组仅包含一个国籍.这个集合有多少个 good 分区？（一组可能只有一个人。）

蛮力方法需要遍历大约 10^26 个分区并检查哪些分区是好的。这似乎是不可行的，尤其是如果团体人数较多或有人介绍其他国籍。有没有更聪明的方法？

编辑：作为旁注。可能没有希望找到一个非常好的解决方案。一位备受尊敬的组合学专家 answered 一个相关问题，我认为，基本上是说相关问题，因此这个问题也很难准确解决。

Answer 1

精确解析解很难，但多项式时间+space动态规划解很简单。

首先，我们需要对组的大小进行绝对排序。我们通过比较我们有多少丹麦人、日本人和波兰人来做到这一点。

接下来要写的函数就是这个

m is the maximum group size we can emit

p is the number of people of each nationality that we have left to split

max_good_partitions_of_maximum_size(m, p) is the number of "good partitions"
we can form from p people, with no group being larger than m

很明显，您可以将其写成一个有点复杂的递归函数，它总是 select 下一个要使用的分区，然后用它作为新的最大大小调用自身，并从 p 中减去分区。如果你有这个功能，那么你的答案就是 max_good_partitions_of_maximum_size(p, p) 和 p = [13, 11, 8]。但这将是一种蛮力搜索，不会在合理的时间内运行。

最终通过缓存对此函数的每次调用来应用https://en.wikipedia.org/wiki/Memoization，它将在多项式时间内运行。但是，您还必须缓存对它的多项式调用。

Answer 2

这是一个使用动态规划的解决方案。

从一个空集合开始，然后一次添加一个元素，并计算所有有效分区。

状态 space 是 巨大的 ，但请注意，为了能够计算下一步，我们只需要了解分区的以下内容：

对于每个国籍，它包含多少只由该国籍的一个成员组成的集合。（例如：{a}）
它包含多少组混合元素。（例如：{a, b, c}）

对于这些配置中的每一个，我只存储总数。示例：

[0, 1, 2, 2] -> 3
{a}{b}{c}{mixed} 
   e.g.: 3 partitions that look like: {b}, {c}, {c}, {a,c}, {b,c}

这是 python 中的代码：

import collections
from operator import mul
from fractions import Fraction

def nCk(n,k):
  return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

def good_partitions(l):
    n = len(l)
    i = 0
    prev = collections.defaultdict(int)
    while l:
        #any more from this kind?
        if l[0] == 0:
            l.pop(0)
            i += 1
            continue
        l[0] -= 1
        curr = collections.defaultdict(int)

        for solution,total in prev.iteritems():
            for idx,item in enumerate(solution):
                my_solution = list(solution)
                if idx == i:
                    # add element as a new set
                    my_solution[i] += 1
                    curr[tuple(my_solution)] += total
                elif my_solution[idx]:
                    if idx != n:
                        # add to a set consisting of one element
                        # or merge into multiple sets that consist of one element
                        cnt = my_solution[idx]
                        c = cnt
                        while c > 0:
                            my_solution = list(solution)
                            my_solution[n] += 1
                            my_solution[idx] -= c
                            curr[tuple(my_solution)] += total * nCk(cnt, c)
                            c -= 1
                    else:
                        # add to a mixed set
                        cnt = my_solution[idx]
                        curr[tuple(my_solution)] += total * cnt

        if not prev:
            # one set with one element
            lone = [0] * (n+1)
            lone[i] = 1
            curr[tuple(lone)] = 1

        prev = curr
    return sum(prev.values())

print good_partitions([1, 1, 1, 1])      # 15
print good_partitions([1, 1, 1, 1, 1])   # 52
print good_partitions([2, 1])            # 4
print good_partitions([13, 11, 8])       # 29811734589499214658370837

它为测试用例生成正确的值。我还针对蛮力解决方案（对于小值）对其进行了测试，它产生了相同的结果。

具有给定约束的分区数

Number of partitions with a given constraint

algorithm

partitioning

combinatorics