1

我正在开发一个应用程序，我想要获取 M 中所有可能的元素 k 组合的集合 C（带有 ||M|| = m），并用子集的 k 组合集合覆盖 C M 中的 N_i，与 ||N_i|| = n < m ∀ N_i

所以有 (m 选择 k) 个组合要覆盖，n 个元素的每个集合 Q_i 将包含 (n 选择 k) 个组合。

我想要的是一种构造集合 Qi 的算法，使得 q 最小化（即，尽可能接近（m 选择 k）/（n 选择 k））

因此，例如，如果 m=100、k=3 和 n=10，我想要最小的 10 个元素集，使得它们各自的 3-组合集覆盖 (100 选择 3) 3- M的组合

4

2 回答 2

1

我在 Math Overflow 上交叉发布了这个问题

事实证明，这是一个在组合学中被广泛使用的问题，称为覆盖设计问题。

一般来说，没有算法可以保证最小值，尽管有些算法非常接近最小值。你可以在这里找到现有的已知覆盖物和研究

于 2012-05-31T16:21:38.670 回答
1

我不确定这是否有帮助，但我已经编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。它执行以下任务：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。这种方法使得解决这类问题变得非常简单。

  2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我可能是错的。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

将此类转换为您选择的语言应该不难。

从您对问题的描述来看，您似乎应该为 N 设置一个循环（如果 K 也发生变化，则为另一个循环），然后为该 N，K 组合创建一个二项式系数对象（BC）。使用 BC 对象调用 GetBinCoeff() 的无符号长版本以获取组合总数。然后设置另一个循环来遍历每个 BC 对象的组合总数。在该循环中，调用 BC GetKIndexes 方法来获取每个索引（即组合）的 K-Indexes，然后进行计算。我不确定您要最小化什么。如果我的建议不够清晰或不够有用，请尝试发布更详细的示例，清楚地显示您正在寻找的结果。

于 2012-09-25T10:40:59.087 回答