找到多种方法将不同颜色的球分组的算法

Question

这个问题困扰了我很长一段时间。

We are given n balls (edit: in a line) that we want to put into different groups. Each ball has a color denoted by an integer. Two groupings are considered different if there are two balls in the same group in one grouping but not in the other grouping.

Find the number of ways to group the balls such that the number of colors represented in each group is between two integers a and b (ie. a <= number of colors <= b).

Edit: The groupings are such that whenever we want to split the balls into separate groups, it must occur along the line. So if we want to split balls of colours 1,2,3,3,4,1,3 into groups and a=2, b=3, then the groupings are 1,2 | 3,3,4 | 1,3, 1,2,3 | 3,4 | 1,3.

我一直在尝试为此提出一个动态编程解决方案。我想到的一个解决方案是考虑当我们有 k - 1 个球的分组数时会发生什么，看看我们可以将 k 个球放入多少组 - 所以我们不断向现有组添加球，直到我们有足够多的不同球颜色超过创建新组所需的最少颜色数。但我意识到有很多方法可以做到这一点，我不确定这是否是一个可行的方向。有什么想法吗？

Answer 1

原版题目，所有颜色都不一样。 那么一个简单的解决方案就是：

X(n) = sum_{k=a to b} X(n-k)

使用记忆以避免在不同时间执行相同的计算。

由于球可以有不同的颜色，从给定的起点开始，我们必须从这个起点计算不同颜色的数量。这可以通过将颜色插入集合（或散列集合）并检查该集合的大小来实现。

在这种情况下，对于递归，我们可以使用声明点的索引

 X(index) = sum _{k = ...} X(index + k)

当 k 的范围由索引中不同颜色的数量控制时。

最终结果等于X(0)。