arrays - 排名和不排名结合约束

Question

我想对具有元素距离约束的组合进行排序和取消排序所选元素不能重复。
例如：
n := 10元素选择
k := 5正在选择的元素
d := 3两个选定元素之间的最大距离
1,3,5,8,9匹配约束
1,5,6,7,8不匹配约束
如果1,2,3,4,5小于1,2,3,4,6，如何对具有给定距离约束的组合进行排序有没有一种方法不计算排名较小的组合排名？

Answer 1

首先创建并填充一个二维数组，我将其称为nvt表示“有效尾数”，用给定值记录从某个位置开始的有效“尾数”。例如，NVT[4][6]=3，因为位置为4的6的组合可以以3种不同的方式结束：（…，6，7）、（…，6，8）和（…，6，9）。
要填充NVT，请从NVT[n][…]开始，这只是所有1的一行，然后返回到前面的位置；例如，NVT[2][5]=NVT[3][6]+NVT[3][7]+NVT[3][8]，因为从位置3开始的值为5的“尾”将由5加上从位置4开始的值为6、7或8的“尾”组成。
请注意，我们并不关心是否有一个有效的方法达到给定的尾巴。例如，NVT[4][1]=3是因为有效的尾部（1，2），（1，3）和（1，4），即使没有完整的形式组合（…，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]）。
相反，您可以找到具有给定秩r的组合c，如下所示：
为“剩余秩”创建一个临时变量r r，最初等于r。
要找到c[1]-位置1中的值-从位置1开始计算有效尾数，从最小可能值（即1）开始，一旦超过rr就停止。例如，由于nvt[1][1]=66和nvt[1][2]=27，因此与秩75的组合必须以2开头（因为75≥66和75<66+27）。然后从rr中减去这个和（在这种情况下，保留75-66=9）。
然后对所有后续位置执行相同的操作，确保记住给定的前一位置的最小可能值继续我们的例子r=75，c[1]=2，和rr=9，我们知道c[2]≥3；并且由于nvt[2][3]=23>rr，我们立即发现c[2]=3。
复杂性分析：
空间：
nvt需要o（nk）空间。
将组合作为length-k数组返回本质上需要o（k）空间；但如果我们每次返回一个值（通过调用回调或打印到控制台或其他地方），那么计算本身实际上并不依赖于此数组，只需要o（1）额外空间。
除此之外，其他一切都可以在O（1）空间中管理；我们不需要任何递归、临时数组或任何东西。
时间：
填充nvt需要o（nkd）时间。（注：如果d大于n，则可以将d设为n。）
给定nvt，计算给定组合的秩需要最坏情况o（nk）时间。
给定NVT，计算具有给定秩的组合需要最坏情况O（nk）时间。
实现说明：上面的细节有点烦琐；如果没有具体的数据可以查看，很容易一个错误就搞定，或者混淆两个变量，或者什么都不做。由于您的示例只有168个有效组合，我建议您生成所有组合，以便您可以在调试期间引用它们。
可能的额外优化：如果您希望n相当大，并且您希望对“rank”和“unrank”组合进行大量查询，那么您可能会发现创建第二个数组很有用，我将其称为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（n k）过程。）使用NVTLT而不是NVT进行查询将允许您对值执行二进制搜索，而不是线性搜索，从而提供最坏情况下的O（k log n）时间而不是O（nk）时间请注意，这个优化比上面的更复杂，所以即使您打算执行这个优化，我建议从上面开始，让它完美地工作，然后才添加这个优化。