algorithm - 找到 bin 和 objects 的所有可能性

Question

给定一组有限的箱子和对象，其中箱子的大小是无限的(它们可以容纳的对象数量没有限制。什么是计算箱子中对象的所有可能性的有效算法。

例如:

假设我们有容器:B1、B2 和对象 O1、O2，解决方案是:

B1 => [O1, O2] 
B2 => []

B1 => []
B2 => [O1, O2]

B1 => [O2]
B2 => [O1]

B1 => [O1]
B2 => [O2]

Answer 1

假设 B 是箱数，O 是对象数。该算法应仅以 base-B 计数(而不是 base-10 或 base-2)，从 0_B 到 AA...AA_B 计数，其中 A = B - 1 , 位数等于 O.

在 base-B 中计数的最简单方法是使用长度为 O 的数组。在每个步骤中，将 ...XAA..AA 转换为 ...Y00..00，其中 X < A 和 Y = X + 1 以及部分 AA。 .AA 的长度甚至可以为零。尽可能重复。转换子数组的最简单方法是在内部运行一个循环，该循环从数组的一端运行，以模 B 递增项目，并在递增后第一个不为零的项目之后停止，或在数组的另一端停止数组。

每一步对数组内容的解释就是每一个O位告诉我们O_n对象在哪个bin中。