algorithm - 什么软件算法将从一个大集合中选择不同的项目子集

Question

设置

假设我有很多元素。每件元素都有形状、大小和颜色。他们可能是

• 三角形、圆形或正方形
• 红色、绿色或蓝色
• 小或大

我无法对这些属性在项目中的分布做出任何假设。我有理由确定它不是一百万个大的红色三角形，但这总是有可能的。

问题

我想选择 36 个形状，在所有属性类中尽可能“多样化”地表示。澄清一下，从非常大的集合中抽取 36 个项目，我理想情况下喜欢 12 个红色、12 个绿色、12 个蓝色、12 个三角形、18 个小等。

现在有 18 种可能的不同项目类型(3 种颜色 * 3 种形状 * 2 种尺寸)，因此一种方法是在每种不同类型中包含两种(假设我有)。

如果我没有足够的每种不同类型，另一种(不切实际的蛮力)方法是迭代 36 个项目的每个可能子集并保留最佳子集。

我确信这是一个更广泛的问题类别的具体实例，可以通过众所周知的算法解决，但我无法确定 Google 的魔法词。我已将其标记为knapsack-problem，因为感觉可能就是这样，但我想知道是否有更好的方法来解决这个问题？

您能否提供解决方案或至少提供适当的搜索字词？

Answer 1

看reservoir sampling .为每种形状/颜色/尺寸组合制作一个储液器(因此 36 个储液器)，每个储液器的容量为 36。对所有元素进行一次传递，并为每个元素选择其合适的储液器并执行储液器采样步骤。

这会将您的问题减少到最多 36*36 = 1296 个元素，从所有元素中公平地采样，甚至涵盖只有一个组合的最坏情况。

然后您可以简单地洗牌储层，从每个储层中随机选择一个元素(跳过空储层)，然后将它们从储层中移除。如果您拥有每种形状/颜色/尺寸中的一种，您将立即完成。如果没有，则再次洗牌并进行另一遍，并继续这样做，直到您选择了 36 个元素。这为您提供了数据集中的统一样本，并根据形状/颜色/大小偏差进行了归一化。