我想使用元素距离约束对组合进行排名和取消排名。所选元素不能重复。
例如：
n := 10元素选择
k := 5被选择的元素
d := 32 个选定元素之间的最大距离
1,3,5,8,9匹配约束条件
1,5,6,7,8与约束不匹配
如何对具有给定距离约束的组合进行排序，其中1,2,3,4,5小于1,2,3,4,6？有没有一种方法可以在不计算 Rank 较小的组合的情况下进行排名？
您可以通过首先创建并填充一个二维数组来完成此操作，我将其称为NVT对于“有效尾数”，记录从给定值的某个位置开始的有效“尾数”的数量。例如，NVT[4][6] = 3，因为位置 #4 中有 6 的组合可以以 3 种不同的方式结束：(…, 6, 7)、(…, 6, 8) 和 (…, 6, 9) 。
- 填充NVT， 从...开始NVT[k][…]，这只是一行全 1。然后回到之前的位置；例如，NVT[2][5] =NVT[3][6] +NVT[3][7] +NVT[3][8]，因为从位置 #3 开始、值为 5 的“尾部”将由该 5 加上从位置 #4 开始、值为 6、7 或 8 的“尾部”组成。
- 请注意，我们并不关心是否确实存在有效的方法reach给定的尾巴。例如，NVT[4][1] = 3，因为有效的尾部 (1, 2)、(1, 3) 和 (1, 4)，即使没有complete(…, 1, _) 形式的组合。
完成此操作后，您可以计算组合的排名C如下：
- 对于位置 #1，计算从位置 #1 开始且值小于的所有有效尾部C[1]。例如，如果C从 3 开始，那么这将是NVT[1][1] +NVT[1][2]，代表以1或2开头的所有组合。
- 然后对所有后续位置执行相同操作。这些将代表以相同方式开始的组合C直到给定位置，但随后在该位置具有较小的值。
- 例如，如果C是 (1, 3, 5, 8, 9)，结果是
0 +
(NVT[2][1] +NVT[2][2]) +
(NVT[3][1] +NVT[3][2] +NVT[3][3] +NVT[3][4]) +
(NVT[4][1] +NVT[4][2] +NVT[4][3]+NVT[4][4]+NVT[4][5]+NVT[4][6] +NVT[4][7]) +
（NVT[5][1] +NVT[5][2] +NVT[5][3] +NVT[5][4] +NVT[5][5] +NVT[5][6] +NVT[5][7] +NVT[5][8]).
反之，你可以找到组合C具有给定的排名r如下：
- 创建临时变量rr，对于“剩余排名”，最初等于r.
- To find C[1] — 位置 #1 中的值 — 从位置 #1 开始计算有效尾数，从最小可能值（即 1）开始，一旦超过则停止rr。例如，自从NVT[1][1] = 66 且NVT[1][2] = 27，排名为 75 的组合必须以 2 开头（因为 75 ≥ 66 且 75 rr（在本例中剩下 75 − 66 = 9）。
- 然后对所有后续位置执行相同的操作，确保记住考虑到前一个位置的最小可能值。继续我们的例子r = 75, C[1] = 2，并且rr= 9，我们知道C[2] ≥ 3；自从NVT[2][3]=23>rr，我们立即发现C[2] = 3.
复杂度分析：
- Space:
-
NVT需要O(nk) space.
- 返回一个组合作为长度k数组本质上需要O(k） 空间;但是如果我们一次返回一个值的组合（通过调用回调或打印到控制台或其他东西），那么计算本身实际上并不依赖于这个数组，只需要O(1)额外空间。
- 除此之外，其他一切都可以在其中管理O(1) 空间；我们不需要任何递归或临时数组或任何东西。
- Time:
- 人口增加NVT takes O(nkd） 时间。 （注：如果d大于n，那么我们可以设置d等于n.)
- Given NVT，计算给定组合的排名采用最坏情况O(nk) time.
- Given NVT，计算给定排名的组合采用最坏情况O(nk) time.
实现说明：上面的细节有点繁琐；如果您没有具体的数据可供查看，那么很容易出现相差一的错误，或者混淆两个变量，或者诸如此类的情况。由于您的示例只有 168 个有效组合，因此我建议生成所有组合，以便您可以在调试期间引用它们。
可能的额外优化：如果您期望n如果相当大，并且您希望执行大量查询来“排名”和“取消排名”组合，那么您可能会发现创建第二个数组很有用，我将其称为NVTLT对于“有效尾数小于”，记录从某个位置开始的有效“尾数”的数量少于给定值。例如，NVTLT[3][5]=NVT[3][1] +NVT[3][2] +NVT[3][3] +NVT[3][4]，或者如果您愿意，NVTLT[3][5]=NVTLT[3][4] +NVT[3][4]。 （您可以将其作为就地转换来执行，完全覆盖NVT，所以这是一个O(nk）通过，没有额外的空间。）使用NVTLT代替NVT对于您的查询，您可以对值进行二分搜索，而不是线性搜索，给出最坏的情况O(k log n) 时间而不是O(nk） 时间。请注意，此优化比上述优化更加棘手，因此即使您打算执行此优化，我也建议从上述开始，使其完美运行，然后再添加此优化。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
