python - 如何在指数大列表中找到第 k 个最大元素？

Question

假设有 n 组实数:S[1], S[2], ..., S[n] .关于这些集合，我们知道两件事:

每个集合 S[i] 正好有 3 个元素。

每个集合 S[i] 中的所有元素都是 [0, 1] 范围内的实数。 (不过，我不知道这个细节是否对解决方案有帮助)。

让我们考虑一个集合 T可以表示为 p[1] * p[2] * p[3] * ... * p[n] 的所有数字其中 p[i] 是 S[i] 的一个元素。这套 T ，显然，有 3^n 个元素。
我的问题是，给定集合 S[1], S[2], ..., S[n] (1 <= n <= 30) 和一些 1 <= k <= 10 作为输入，我们可以在 T 中找到第 k 个最大的数吗？比 O(3^n) 时间快？重要的是，我不仅需要第 k 大的数字，还需要产生它的相应数字( p[1], p[2], p[3], ... , p[n] )。
即使答案是否定的，我也很感激您提供有关如何使用启发式方法大致解决此问题的任何提示？我知道 beam search ，但也许你可以提出其他建议？即使对于波束搜索，也不清楚如何在这里以最佳方式实现它。
如果可以在小于 O(3^n) 的时间内通过算法获得确切的答案，如果您能指出解决方案，我将不胜感激。

Answer 1

嗯，您知道最大的乘积是使用每个集合中最大因子的乘积。
此外，所有其他乘积都可以通过从较大的乘积开始，然后减少恰好在一组中选择的因子来形成。
这导致了一个简单的搜索:

将最大的产品放入最大优先级队列。

重复k次:
一种。从优先队列中取出最大的产品 p
湾对于每一个比 p 中选择的数字更小的集合，
通过将该数字减少到该集合中的下一个较低的数字来生成乘积。如果之前没有看到这些因素选择，则将其添加到优先级队列中。

产品将按降序从队列中删除，因此您取出的第 k 个是第 k 个最大的。
复杂度约为 N*(k log kN)，具体取决于您如何实现。
请注意，可能有多种方法可以选择生产相同产品的因素。该解决方案将这些方式视为不同的产品，即在找到第 k 个最大时计算每种方式。这可能是也可能不是您想要的。