问题标签 [combinatorics]

这本身不是一个编程问题，尽管最终目标是设计一种算法。我正在寻找参考资料或至少是一种游戏的名称。它在电视游戏节目中非常普遍。游戏如下：

您有许多插槽，每个插槽都包含一个您不知道的项目（来自某个有限集合）。您必须猜测每个插槽包含什么。您将您的猜测告诉法官（他知道每个插槽包含什么），他会告诉您有多少猜测是正确的，而不会告诉您哪个。当您成功猜出所有项目时，游戏结束。

我会对有关此类游戏的任何信息感兴趣，包括对以尽可能少的猜测进行求解的算法的引用等。只是名称，以便我可以在谷歌上搜索它也可以。

谢谢！

第一：维基百科中的问题名称是“集合的有序分区”。

我有一个计算可能分区的算法。为了加快速度，我使用了缓存：

此外，我还有另一种算法，它显示了这些可能分区的列表。但它还没有使用缓存，所以它很慢：

所以我有两个问题：1）是否也可以在第二种算法中实现缓存？如果是的话，你能帮我做这件事吗？2）是否可以将第二种算法的结果写入结构化数组而不是字符串？

我希望你能帮助我。非常感谢您！

PS：感谢simonn和Dan Dyer这两个函数！

由于分配问题可以以单个矩阵的形式提出，我想知道 NumPy 是否具有解决这样一个矩阵的功能。到目前为止，我还没有找到。也许你们中的一个人知道 NumPy/SciPy 是否具有分配问题解决功能？

编辑：与此同时，我在http://software.clapper.org/munkres/找到了一个 Python（不是 NumPy/SciPy）实现。我仍然认为 NumPy/SciPy 实现可能会快得多，对吧？

我有一个成本优化请求，我不知道是否有相关文献。这有点难以解释，所以我提前为问题的长度道歉。

我正在访问的服务器以这种方式工作：

• 对记录 (r1, ...rn) 和字段 (f1, ...fp) 发出请求
• 您只能请求笛卡尔积 (r1, ..., rp) x (f1,...fp)
• 与此类请求相关的成本（时间和金钱）与请求的大小相关：

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

不失一般性（仅通过归一化），我们可以假设b=1成本为：

T((r1, ...,rn)x(f1,...fp)) = a + n * p

• 我只需要请求 pair 的一个子集(r1, f(r1)), ... (rk, f(rk))，一个来自用户的请求。我的程序充当用户和服务器（外部）之间的中间人。我有很多这样的请求（每天数万个）。

从图形上看，我们可以将其视为一个 nxp 稀疏矩阵，为此我想用一个矩形子矩阵覆盖非零值：

有：

• 由于成本不变，子矩阵的数量保持合理
• 所有的 'x' 必须位于子矩阵内
• 由于线性成本，覆盖的总面积不能太大

我将 g 命名为我的问题的稀疏系数（所需对的数量超过可能的对总数，g = k / (n * p)。我知道系数a。

有一些明显的观察结果：

• 如果 a 很小，最好的解决方案是独立请求每个 (record, field) 对，总成本为：k * (a + 1) = g * n * p * (a + 1)
• 如果 a 很大，最好的解决方案是请求整个笛卡尔积，总成本为：a + n * p
• 第二种解决方案更好g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
• 当然笛卡尔积中的顺序并不重要，因此我可以转置矩阵的行和列以使其更容易覆盖，例如：

可以重新排序为

并且有一个最佳的解决方案是要求(f1,f3) x (r1,r3) + (f2) x (r2)

• 尝试所有解决方案并寻找更低的成本不是一种选择，因为组合学爆炸了：

所以我正在寻找一个近似的解决方案。我已经有某种贪心算法，可以在给定矩阵的情况下找到覆盖（它从单一单元格开始，如果合并中空单元格的比例低于某个阈值，则合并它们）。

记住一些数字，我的 n 介于 1 和 1000 之间，而我的 p 介于 1 和 200 之间。覆盖模式真的是“块状”，因为记录来自所要求的字段相似的类。不幸的是，我无法访问记录类...

问题 1：有人有什么想法、一个巧妙的简化或可能有用的论文参考吗？由于我有很多请求，因此我正在寻找一种平均运行良好的算法（但我无法承受它在某些极端情况下运行不佳，例如当 n 和 p 很大时请求整个矩阵，并且请求确实非常稀疏）。

问题2：其实问题更复杂：cost其实更像是这样的形式：a + n * (p^b) + c * n' * p'，其中b是一个常数<1（一个记录一旦求一个字段，再求其他也不算太贵字段）并且n' * p' = n * p * (1 - g)是我不想请求的单元格的数量（因为它们是无效的，并且请求无效的东西需要额外的费用）。我什至无法想到一个快速解决这个问题的方法，但仍然......任何人的想法？

假设我们有从 1 到 25 的数字，我们必须选择 15 个数字的集合。

如果我是对的，可能的集合是 3268760。

在这 3268760 个选项中，您必须生成 100000 个

生成 100000 个唯一且随机的子集的最佳方法是什么？

有没有办法，一种算法来做到这一点？

如果不是，那么检测重复项的最佳选择是什么？

我打算在 PHP 上执行此操作，但一个通用的解决方案就足够了，任何不涉及太多“学术”（更实用）的参考都会对我有很大帮助。

我有一个组合任务，涉及从特定的字符串组合中获取长度小于或等于 6 的每个单词。

在这种情况下，它是 S = { 'a', 'ab', 'ba' }。教授刚开始列出它们，但我认为使用程序会更容易解决。唯一的问题是我无法获得一个可以实际计算所有可能选项的好算法。

如果有人可以提供帮助，我将不胜感激。我通常用 Python 编程，但实际上我只需要算法方面的帮助。

我有 n 个元素。举个例子，假设有 7 个元素，1234567。我知道有 7 个！= 这 7 个元素可能有 5040 种排列。

我想要一个包含两个函数的快速算法：

f(number) 将 0 到 5039 之间的数字映射到唯一的排列，并且

f'(permutation) 将排列映射回生成它的数字。

我不关心数字和排列之间的对应关系，只要每个排列都有自己唯一的数字。

所以，例如，我可能有函数

想到的最快算法是枚举所有排列并在两个方向上创建一个查找表，这样，一旦创建了表，f(0) 将是 O(1) 而 f('1234567') 将是在字符串上查找。但是，这会占用大量内存，尤其是当 n 变大时。

任何人都可以提出另一种可以快速运行且没有内存缺点的算法吗？

我有一个具有如下属性的数据集：

等等。大约有 200 个这样的变量。

我需要一种算法来生成属性组合，一次只有一个值。

换句话说，我的第一个组合是：

下一组将是：

我尝试使用一个简单的组合生成器，将每个属性的每个值都视为一个属性本身。它不起作用，因为组合中包含相互排斥的选择，并且可能的组合数量非常大（准确地说是133873417996074857185490633899939406700260683726864088366400）

您能否建议一种算法（最好用 Java 编码）？

谢谢！！

我试图找出一种有效的算法来获取项目列表并生成所有唯一子集，这些子集是通过将列表拆分为恰好 2 个子列表而产生的。我确信有一种通用的方法可以做到这一点，但我对一个特定的案例感兴趣。我的列表将被排序，并且可以有重复的项目。

一些例子：

输入
{1,2,3}

输出
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

输入
{1,2,3,4}

输出
{{1},{2,3,4}}
{{2},{1,3,4}}
{{3},{1,2,4}}
{{4},{1,2, 3}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}

输入
{1,2,2,3}

输出
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2, 3}}
{{1,3},{2,2}}

我可以在纸上做到这一点，但我正在努力找出一种以编程方式完成它的简单方法。我只是在寻找有关如何执行此操作的快速伪代码描述，而不是任何特定的代码示例。

任何帮助表示赞赏。谢谢。

我遇到了无法仅通过算法解决的问题。

假设我有一个视频捕获，它总是以固定速率 F（假设每秒 30 帧）捕获视频帧。

我想要的是将此帧序列“拆分”为 n 个（比如说四个）子序列。每个子序列都有其帧速率 fn，这显然 < F。子序列中的帧在时间上是等距的，因此例如一些有效的 10 fps 序列 f1 将像 F = 30 fps 和时间 = 1 秒那样构造：

（0 是不属于子序列的帧，1 是属于的帧）：

或者

或者，对于 F = 30 和 f = 8：

（并且在以“1”重新开始之前需要 MCD (30,8) = 120 帧）。

问题是子序列不能碰撞，所以如果 F=30，f1 = 10 fps（每三帧）和 f2 = 5 fps（每六帧），这个序列是可以的：

但是如果我们加上 f3 = 6 fps

或者

第三个子序列将与第一个子序列发生冲突。

问题是：

• 有没有办法找到n个（n <= 4）子序列的帧速率的每个组合，它们不会发生冲突并且会等距？

（我需要一般情况，但在这种特殊情况下，我只需要一个序列的所有有效组合（平凡），两个序列的所有有效组合，三个序列的所有有效组合，以及四个序列的所有有效组合） .

希望有人能启发我的想法。谢谢！