秩和非秩约束组合

Question

我想用元素距离约束对组合进行排序和取消排序。选定的元素不能重复。

例如：

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，如何对组合进行排序？有没有一种方法可以在不计算较小秩的组合的情况下进行排序？

Answer 1

您可以通过首先创建并填充二维数组来实现这一点，我将其称为“有效尾数”的NVT，以记录从给定值的特定位置开始的有效“尾数”。例如，NVT[4][6]

• 要填充NVT，请从NVT[k][…]开始，这只是所有1的一行。然后回到之前的工作岗位；例如，NVT[2][5]

完成后，您可以计算组合C的秩，如下所示：

• 对于位置#1，从位置#1开始计算所有值小于C[1]的有效尾。例如，如果C以3开始，那么这将是NVT[1][1]

相反，你可以找到具有给定秩r的组合C，如下所示：

• 创建一个临时变量rr，用于"剩余排名"，最初等于r。
• 要查找C[1]-位置#1中的值-从位置#1开始计算有效的尾巴，从可能的最小值（即1）开始，一旦超过rr就停止。例如，由于NVT[1][1]

复杂性分析：

• 空间：

• 填充NVT需要O（nkd）时间。（注意：如果d大于n，那么我们可以设置d等于n。）
• 给定NVT，计算给定组合的秩需要最坏情况下的O（nk）时间。
• 给定NVT，计算给定秩的组合需要最坏情况下的O（nk）时间。

实施说明：以上细节有点繁琐；如果你没有具体的数据可以查看，那么很容易一个错误就搞定了，或者混淆了两个变量，或者诸如此类的事情。由于您的示例只有168个有效组合，我建议您生成所有组合，以便在调试期间可以引用它们。

可能的额外优化：如果您希望n相当大，并且希望对“rank”和“unrank”组合进行大量查询，那么您可能会发现创建第二个数组很有用，我将其称为NVTLT，表示“有效尾数小于”，记录从某个位置开始且值小于给定值的有效“尾数”。例如，NVTLT[3][5]