组合算法
Combinatorics Algorithm
我遇到了一个有趣的编程问题，我似乎无法制定解决方案。假设你有 N 个不同颜色的 K 个球。您必须将所有球分成尽可能多的组，这样就没有两组是相同的。 （如果每个颜色的球数量相同，则两组被认为是相同的。）您最多可以组成多少组？
约束：
1<=K<=50,
1<=N<=14
澄清一下：我们想要一个接受 >= 1 整数数组的算法。数组的大小是 N，它包含的值的总和是 K。算法应该 return最大组数。
关于这个问题的算法方法有什么想法吗？
（我试图制定一个游戏策略，但我将 运行 保留为反例，所以我重写了答案，只保留那些似乎正在工作。）
输入
我假设输入的形式是：
{K:30, N:6, red:4, green:3, blue:1, cyan:10, magenta:5, yellow:7}
也可以写成：
rrrr ggg b cccccccccc mmmmm yyyyyyy
单球组
第一个观察是单个球只能将一个无效（重复）组变成一个有效（唯一）组，因此如果不使用单个球形成一个单球组，您只能获得一个组, 所以你不妨从创建每一种可用颜色的单球组开始。
r g gg ggg (ggg) = 4
g gg ggg rggg = 4
r g b bb bbb bbbbbb = 6
r g b bb bbb bbbb (bb) = 6
b bb bbb bbbb rb gb = 6
这有效地将具有 N 种颜色的 K 个球的输入变成了具有 N 种或更少颜色的 K-N 个球的问题，最大值为 49:1、48:2 ... 36:14 .上面提到的例子从30:6减少到24:5
rrrr ggg b cccccccccc mmmmm yyyyyyy
r g b c m y + rrr gg ccccccccc mmmm yyyyyy
从小到大的团体
如果在转到 S+1 尺寸之前创建尽可能多的 S 尺寸组，并且还剩下 S 个未使用的球，它们将形成一个重复的 S 尺寸组，但如果有办法避免这种情况，你会有一个 S 大小的组，所以这意味着 S 大小的组的解决方案首先不是最佳的。
如果您在转到 S+1 尺寸之前创建了尽可能多的 S 尺寸组，并且您还有超过 S 个未使用的球，那么您与它们组成的更大的组将永远不会重复 S 尺寸团体。
由此很容易假设创建单球组，然后是 2 球组，然后是 3 球组......将导致最佳解决方案。但是，有些例子没有：
{K:45, N:5, red:3, green:3, blue:3, cyan:3, yellow:33}
rrr ggg bbb ccc yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
r g b c y = 5
rg bc ry gy by cy yy = 7
yyy yyyy yyyyy yyyyyy yyyyyyy (y) = 5
TOTAL = 17
r g b c y = 5
ry gy by cy yy = 5
ryy gyy byy cyy = 4
yyy yyyy yyyyy yyyyyy = 4
TOTAL = 18
这似乎是最大 50 个球发挥作用的地方。如果您开始时制作尽可能多的 1-ball 组，然后是 2、3 ... 您可能必须拆分一个较小的组才能将剩下的球（或一个独特的组 + 剩余的球）分成两个或更多独特的群体。然而，似乎不可能改进没有剩余球的解决方案，至少在这个输入大小限制下。
找到 2 大小组的最佳数量意味着像这样填充 2D table：
r g b c m y
r +
g + -
b + - +
c - + - -
m + + - + +
y - + + - - +
有 1 + 2 + ... + N 个可能的组，但这并不意味着有 2 ^ (1 + 2 + ... + N) 个选项可供考虑。一方面，我们正在寻找最佳解决方案，因此没有必要寻找只有几个组的解决方案，另一方面，在制作 1-ball 组之后，最多只剩下 K - N 个球做组。还有一个事实是有些颜色可能没有 N + 1 个球，因此并非所有具有该颜色的组合都可以同时进行；事实上，当使用超过 6 种颜色时，不可能创建所有 2 球组合：
N K-N pairs combi
1 49 24 1
2 48 24 3
3 47 23 6
4 46 23 10
5 45 22 15
6 44 22 21
7 43 21 28
8 42 21 36
9 41 20 45
10 40 20 55
11 39 19 66
12 38 19 78
13 37 18 91
14 36 18 105
我将从 K 个单元素组开始，逐步细化它们，直到所有组都不同。在每一步中，我们删除两个组，加入它们并将新组放回原处。困难在于选择哪些组，我建议以下因素来排序选择（按重要性降序排列）：
- 更不同的结果获胜（例如，两个组合成一个新的不同组的组胜过两个组合成已知组的组）
- 较小的结果获胜（例如，二元素组优于三元素组）
- 要删除的最常见组
我不确定当有多个选择要select和加入两个组时是否需要暴力破解所有组合，或者是否采取任何路径已经导致最佳解决方案，但是当我们需要尝试多个时，需要使用动态编程方法来限制状态爆炸。
示例（每行按出现次数排序）：
b g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y-y c-c-c-c-c-c-c-c-c-c
b cc g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y-y c-c-c-c-c-c-c-c
b cc cy g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y c-c-c-c-c-c-c
b cc cy cm g-g-g r-r-r-r m-m-m-m y-y-y-y-y-y c-c-c-c-c-c
b cc cy cm yy g-g-g r-r-r-r m-m-m-m y-y-y-y c-c-c-c-c-c
b cc cy cm yy cr g-g-g r-r-r m-m-m-m y-y-y-y c-c-c-c-c
b cc cy cm yy cr cg g-g r-r-r m-m-m-m y-y-y-y c-c-c-c
b cc cy cm yy cr cg my g-g r-r-r m-m-m y-y-y c-c-c-c
b cc cy cm yy cr cg my rm g-g r-r m-m y-y-y c-c-c-c
b cc cy cm yy cr cg my rm g yg r-r m-m y-y c-c-c-c
b cc cy cm yy cr cg my rm g yg r y ry m-m c-c-c-c
b cy cm yy cr cg my rm g yg r y ry m-m cc-cc c-c
b cy cm yy cr cg my rm g yg r y ry m cc mcc c-c
cy cm yy cr cg my rm g yg r y ry m cc mcc c cb
g-g-g r-r-r-r-r b-b-b-b-b
rb g-g-g r-r-r-r b-b-b-b
rb rg g-g r-r-r b-b-b-b
rb rg br g r-r-r b-b-b
rb rg br g r rr b-b-b
rb rg br g r rr b bb
作为每一步的算法，我并没有生成所有可能的分组组合，通过上面的比较函数来移除和排序，而是倒退得到一些候选：
- 选择最常见的组并删除一个，然后选择（现在）最常见的组并删除一个
- 看起来它们的元素加在一起并没有比不太常见的组所能达到的元素更多
- 看起来他们组合到一个未知的组
- 如果是，就接受它们，如果不是，则从下一个常见组开始重复步骤 1
这基本上是在问问题
- 这个组（元素的组合）有多常见/出现的次数是多少？
- 是否已经生成了该组中低于特定大小的元素的所有可能组合？
- 是否已经生成了本组元素和下一组元素的可能组合？
其结果可以以类似动态编程的方式缓存，以便我们可以快速跳过一些候选者（直到真的没有好的选择并且我们必须执行不生成新的不同组的合并，在上面的例子中看到当线变短时）。我们还可以假设我们基本上从不 select 只出现一次的组，因为已知不会生成具有更多不同组的结果。
再次与我的教授交谈后，我了解到这是对 open.kattis.com problem 的改编。
两者几乎相同，因为原始问题的任何实例都可以通过对 N 进行质因数分解并将每个质因数视为一个球来解决。例如，900 = 2^2*3^2*5*2，所以等效球问题就是 2 2 2。
给定的界限是使用最大界限 10^15 找到的。 2^50 > 10^15，所以永远不会超过50个因子，前15个素数相乘也超过10^15，也就是说最多有14组。
然而，球数和组数之间的权衡被忽略了，在我看来，这使问题更容易解决。例如，如果有14组，每组只有1个球，而如果有50个球，则它们都属于同一组（这是由于原问题的10^15限制）
根据这些新信息，我能够解决问题。我将 N 分解为素数列表以及所有因子列表，然后使用多维背包算法（如果 N 具有 X 个唯一素因子，则背包 DP 将是 X+1 维，其中第一个维度是您正在考虑的项目和其他维度代表您对某个主要因素的剩余供应）。 N 的每个因子都代表一个可能放入背包的物品，它的质因数分解是它的成本向量。
这样做之后，问题在最大情况下仍然太慢，需要进行额外的优化。我发现总是存在使用尽可能多的单个球组的最佳解决方案。通过在开始时创建尽可能多的 1 球组并解决剩余的子问题，我能够在 Kattis 的时间限制内完成该问题。
我的算法取决于我已经证明的两个假设：
如果你可以不用所有的球做X组，你也可以用所有的球做X组。这使得您不使用 100% 容量的背包解决方案有效。这个假设可以通过取出所有未使用的球并将它们全部添加到最大的组来证明。这将创建一个比任何其他组都大的组，因此它必须是唯一的。这使您拥有相同数量的组，但使用了所有球。
总是存在使用尽可能多的 1 球组的最佳解决方案。这使得可以将原始问题简化为在时间限制内可解决的子问题。这也可以证明。采取任何最优解。对于任何不存在的 1 球分组，取一个包含该 1 球的组，并将该组中的每个其他球移动到最大的组。这将创建一个具有相同（最佳）组数的解决方案，该解决方案还具有尽可能多的 1 球组。
我的解决方案的运行时间为 O(F(N)^2)，其中 F(N) 是 N 的因子总数。
我遇到了一个有趣的编程问题，我似乎无法制定解决方案。假设你有 N 个不同颜色的 K 个球。您必须将所有球分成尽可能多的组，这样就没有两组是相同的。 （如果每个颜色的球数量相同，则两组被认为是相同的。）您最多可以组成多少组？
约束： 1<=K<=50, 1<=N<=14
澄清一下：我们想要一个接受 >= 1 整数数组的算法。数组的大小是 N，它包含的值的总和是 K。算法应该 return最大组数。
关于这个问题的算法方法有什么想法吗？
（我试图制定一个游戏策略，但我将 运行 保留为反例，所以我重写了答案，只保留那些似乎正在工作。）
输入
我假设输入的形式是：
{K:30, N:6, red:4, green:3, blue:1, cyan:10, magenta:5, yellow:7}
也可以写成：
rrrr ggg b cccccccccc mmmmm yyyyyyy
单球组
第一个观察是单个球只能将一个无效（重复）组变成一个有效（唯一）组，因此如果不使用单个球形成一个单球组，您只能获得一个组, 所以你不妨从创建每一种可用颜色的单球组开始。
r g gg ggg (ggg) = 4
g gg ggg rggg = 4
r g b bb bbb bbbbbb = 6
r g b bb bbb bbbb (bb) = 6
b bb bbb bbbb rb gb = 6
这有效地将具有 N 种颜色的 K 个球的输入变成了具有 N 种或更少颜色的 K-N 个球的问题，最大值为 49:1、48:2 ... 36:14 .上面提到的例子从30:6减少到24:5
rrrr ggg b cccccccccc mmmmm yyyyyyy
r g b c m y + rrr gg ccccccccc mmmm yyyyyy
从小到大的团体
如果在转到 S+1 尺寸之前创建尽可能多的 S 尺寸组，并且还剩下 S 个未使用的球，它们将形成一个重复的 S 尺寸组，但如果有办法避免这种情况，你会有一个 S 大小的组，所以这意味着 S 大小的组的解决方案首先不是最佳的。
如果您在转到 S+1 尺寸之前创建了尽可能多的 S 尺寸组，并且您还有超过 S 个未使用的球，那么您与它们组成的更大的组将永远不会重复 S 尺寸团体。
由此很容易假设创建单球组，然后是 2 球组，然后是 3 球组......将导致最佳解决方案。但是，有些例子没有：
{K:45, N:5, red:3, green:3, blue:3, cyan:3, yellow:33}
rrr ggg bbb ccc yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
r g b c y = 5
rg bc ry gy by cy yy = 7
yyy yyyy yyyyy yyyyyy yyyyyyy (y) = 5
TOTAL = 17
r g b c y = 5
ry gy by cy yy = 5
ryy gyy byy cyy = 4
yyy yyyy yyyyy yyyyyy = 4
TOTAL = 18
这似乎是最大 50 个球发挥作用的地方。如果您开始时制作尽可能多的 1-ball 组，然后是 2、3 ... 您可能必须拆分一个较小的组才能将剩下的球（或一个独特的组 + 剩余的球）分成两个或更多独特的群体。然而，似乎不可能改进没有剩余球的解决方案，至少在这个输入大小限制下。
找到 2 大小组的最佳数量意味着像这样填充 2D table：
r g b c m y
r +
g + -
b + - +
c - + - -
m + + - + +
y - + + - - +
有 1 + 2 + ... + N 个可能的组，但这并不意味着有 2 ^ (1 + 2 + ... + N) 个选项可供考虑。一方面，我们正在寻找最佳解决方案，因此没有必要寻找只有几个组的解决方案，另一方面，在制作 1-ball 组之后，最多只剩下 K - N 个球做组。还有一个事实是有些颜色可能没有 N + 1 个球，因此并非所有具有该颜色的组合都可以同时进行；事实上，当使用超过 6 种颜色时，不可能创建所有 2 球组合：
N K-N pairs combi
1 49 24 1
2 48 24 3
3 47 23 6
4 46 23 10
5 45 22 15
6 44 22 21
7 43 21 28
8 42 21 36
9 41 20 45
10 40 20 55
11 39 19 66
12 38 19 78
13 37 18 91
14 36 18 105
我将从 K 个单元素组开始，逐步细化它们，直到所有组都不同。在每一步中，我们删除两个组，加入它们并将新组放回原处。困难在于选择哪些组，我建议以下因素来排序选择（按重要性降序排列）：
- 更不同的结果获胜（例如，两个组合成一个新的不同组的组胜过两个组合成已知组的组）
- 较小的结果获胜（例如，二元素组优于三元素组）
- 要删除的最常见组
我不确定当有多个选择要select和加入两个组时是否需要暴力破解所有组合，或者是否采取任何路径已经导致最佳解决方案，但是当我们需要尝试多个时，需要使用动态编程方法来限制状态爆炸。
示例（每行按出现次数排序）：
b g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y-y c-c-c-c-c-c-c-c-c-c
b cc g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y-y c-c-c-c-c-c-c-c
b cc cy g-g-g r-r-r-r m-m-m-m-m y-y-y-y-y-y c-c-c-c-c-c-c
b cc cy cm g-g-g r-r-r-r m-m-m-m y-y-y-y-y-y c-c-c-c-c-c
b cc cy cm yy g-g-g r-r-r-r m-m-m-m y-y-y-y c-c-c-c-c-c
b cc cy cm yy cr g-g-g r-r-r m-m-m-m y-y-y-y c-c-c-c-c
b cc cy cm yy cr cg g-g r-r-r m-m-m-m y-y-y-y c-c-c-c
b cc cy cm yy cr cg my g-g r-r-r m-m-m y-y-y c-c-c-c
b cc cy cm yy cr cg my rm g-g r-r m-m y-y-y c-c-c-c
b cc cy cm yy cr cg my rm g yg r-r m-m y-y c-c-c-c
b cc cy cm yy cr cg my rm g yg r y ry m-m c-c-c-c
b cy cm yy cr cg my rm g yg r y ry m-m cc-cc c-c
b cy cm yy cr cg my rm g yg r y ry m cc mcc c-c
cy cm yy cr cg my rm g yg r y ry m cc mcc c cb
g-g-g r-r-r-r-r b-b-b-b-b
rb g-g-g r-r-r-r b-b-b-b
rb rg g-g r-r-r b-b-b-b
rb rg br g r-r-r b-b-b
rb rg br g r rr b-b-b
rb rg br g r rr b bb
作为每一步的算法，我并没有生成所有可能的分组组合，通过上面的比较函数来移除和排序，而是倒退得到一些候选：
- 选择最常见的组并删除一个，然后选择（现在）最常见的组并删除一个
- 看起来它们的元素加在一起并没有比不太常见的组所能达到的元素更多
- 看起来他们组合到一个未知的组
- 如果是，就接受它们，如果不是，则从下一个常见组开始重复步骤 1
这基本上是在问问题
- 这个组（元素的组合）有多常见/出现的次数是多少？
- 是否已经生成了该组中低于特定大小的元素的所有可能组合？
- 是否已经生成了本组元素和下一组元素的可能组合？
其结果可以以类似动态编程的方式缓存，以便我们可以快速跳过一些候选者（直到真的没有好的选择并且我们必须执行不生成新的不同组的合并，在上面的例子中看到当线变短时）。我们还可以假设我们基本上从不 select 只出现一次的组，因为已知不会生成具有更多不同组的结果。
再次与我的教授交谈后，我了解到这是对 open.kattis.com problem 的改编。
两者几乎相同，因为原始问题的任何实例都可以通过对 N 进行质因数分解并将每个质因数视为一个球来解决。例如，900 = 2^2*3^2*5*2，所以等效球问题就是 2 2 2。
给定的界限是使用最大界限 10^15 找到的。 2^50 > 10^15，所以永远不会超过50个因子，前15个素数相乘也超过10^15，也就是说最多有14组。
然而，球数和组数之间的权衡被忽略了，在我看来，这使问题更容易解决。例如，如果有14组，每组只有1个球，而如果有50个球，则它们都属于同一组（这是由于原问题的10^15限制）
根据这些新信息，我能够解决问题。我将 N 分解为素数列表以及所有因子列表，然后使用多维背包算法（如果 N 具有 X 个唯一素因子，则背包 DP 将是 X+1 维，其中第一个维度是您正在考虑的项目和其他维度代表您对某个主要因素的剩余供应）。 N 的每个因子都代表一个可能放入背包的物品，它的质因数分解是它的成本向量。
这样做之后，问题在最大情况下仍然太慢，需要进行额外的优化。我发现总是存在使用尽可能多的单个球组的最佳解决方案。通过在开始时创建尽可能多的 1 球组并解决剩余的子问题，我能够在 Kattis 的时间限制内完成该问题。
我的算法取决于我已经证明的两个假设：
如果你可以不用所有的球做X组，你也可以用所有的球做X组。这使得您不使用 100% 容量的背包解决方案有效。这个假设可以通过取出所有未使用的球并将它们全部添加到最大的组来证明。这将创建一个比任何其他组都大的组，因此它必须是唯一的。这使您拥有相同数量的组，但使用了所有球。
总是存在使用尽可能多的 1 球组的最佳解决方案。这使得可以将原始问题简化为在时间限制内可解决的子问题。这也可以证明。采取任何最优解。对于任何不存在的 1 球分组，取一个包含该 1 球的组，并将该组中的每个其他球移动到最大的组。这将创建一个具有相同（最佳）组数的解决方案，该解决方案还具有尽可能多的 1 球组。
我的解决方案的运行时间为 O(F(N)^2)，其中 F(N) 是 N 的因子总数。