在 Y 的批处理中对 X 数进行排序的算法

Question

谁能告诉我一个算法，我可以用它来对 Y 的批处理中的 X 数进行排序。这意味着你只能同时比较 Y 数，但你可以多次这样做。

例如有 X=100 个陈述，受访者必须根据它们与她的相关程度对它们进行排序，这样她一次只会看到和排序 Y=9 个陈述，但会多次这样做。

Answer 1

从你的假设来看，我相信你愿意做很多工作来找出下一个比较集(因为那是由计算机完成的)，并且希望尽可能少的比较(因为那是人)。

因此，我将概述的方法的想法是一种贪婪的启发式方法，它试图最大化每次比较给我们提供的信息量。这很复杂，但应该做得很好。

我们首先需要的是如何衡量信息。这是 mathematical theory .假设我们有一枚有偏差的硬币，正面朝上的概率为 p。其中出现的信息是- log2(p)。它的尾部信息是 - log2(1-p)。 (注意 log 0 和 1 之间的数字是负数，负数的负数是正数。所以信息总是正数。)如果你使用高效的编码并且有很多翻转来编码，翻转序列的信息总和就是您需要发送多少位来传达它。

因此，单次翻转的预期信息是- p log2(p) - (1-p) log2(1-p)。

因此，我们的想法是选择一个比较集，以便对其进行排序为我们提供尽可能多的关于最终排序的信息，而我们还没有这些信息。但是我们如何估计关于特定对的未知数呢？例如，如果我对 2 组 5 进行排序，则一组的顶部不太可能小于另一组的底部。可能是，但与将两个中间元素相互比较相比，该比较中的信息要少得多。我们如何捕获它？

我的想法是做一系列 topological sorts了解一下。特别是您随机进行第一个拓扑排序。您尝试通过在每次选择中选择上次排名最高的元素来使第二个拓扑排序尽可能不同。第三种拓扑排序选择在前面排序中的秩和尽可能大的元素。等等。执行此操作 20 次左右。

现在，对于任何一对元素，我们只需查看它们在我们的排序中不一致的频率，即可估计其中一个真正大于另一个的概率。我们可以使用之前的公式将其转化为预期的熵。

所以我们从排序中最大和最小排名之间差异最大的元素开始比较集。

第二个元素是与第一个元素具有最高熵的元素，通过其在排序中的最小和最大排名之间的最大差异打破平局。

第三个是与前两个熵之和最大的那个，同样以同样的方式打破平局。

算法将遵循的确切逻辑当然是随机的。事实上，您正在对找到的每个比较集执行 O(k^2 n​​) 工作。但平均而言，它会以少得惊人的比较集结束。

我没有证据，但我怀疑你平均只需要理论上最优的 O(log(n!)/log(k!)) = O(n log(n)/(k log(k))) 比较。对于 k=2，我进一步怀疑它会给出一个平均而言比归并排序更有效的解决方案。