我正在研究一个应用程序，我想要获取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.的组合
2 回答
我不确定这是否有帮助，但是我已经编写了一个类来处理使用二项式系数的常用函数，这是你的问题所面临的问题类型 . 它执行以下任务：
以任意N选择K到文件的格式输出所有K索引 . K索引可以用更具描述性的字符串或字母代替 . 这种方法使解决这类问题变得非常简单 .
将K索引转换为已排序二项系数表中条目的正确索引 . 这种技术比依赖迭代的旧发布技术快得多 . 它通过使用Pascal三角形中固有的数学属性来实现 . 我的论文谈到了这一点 . 我相信我是第一个发现和发布这种技术的人，但我可能错了 .
将已排序的二项系数表中的索引转换为相应的K索引 .
使用Mark Dominus方法计算二项式系数，该二项式系数更不可能溢出并使用更大的数字 .
该类是用.NET C＃编写的，它提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法 . 此类的构造函数采用名为InitTable的bool值，当为true时，将创建一个通用列表来保存要管理的对象 . 如果此值为false，则不会创建表 . 为了执行上述4种方法，不需要创建该表 . 提供访问器方法来访问该表 .
有一个关联的测试类，它显示了如何使用该类及其方法 . 它已经过2个案例的广泛测试，并且没有已知的错误 .
要阅读有关此类并下载代码，请参阅Tablizing The Binomial Coeffieicent .
将此类转换为您选择的语言应该不难 .
根据您对问题的描述，看起来您应该为N设置一个循环（如果它也改变则为K另一个循环），然后为该N，K组合创建二项式系数对象（BC） . 使用BC对象调用无符号长版本的GetBinCoeff（）以获得组合的总数 . 然后设置另一个循环以遍历每个BC对象的组合总数 . 在该循环内部，调用BC GetKIndexes方法获取每个索引的K-Indexes（即组合），然后进行计算 . 我不确定你要尽量减少什么 . 如果我的建议不够明确或不够有用，请尝试发布一个更详细的示例，清楚地显示您要查找的结果 .
我发帖this question on Math Overflow
事实证明，这是组合学中一个被称为 covering design problem 的问题 .
通常，没有算法可以保证最小值，尽管有一些算法非常接近最小值 . 你可以找到现有的已知覆盖物和研究here