Rank 和 unrank 与约束的组合
Rank and unrank Combination with constraints
我想使用元素距离约束对组合进行排名和取消排名。所选元素不能重复。
例如：
n := 10个元素选择
k := 5 个元素正在被选择
d := 3 2 个所选元素之间的最大距离
1,3,5,8,9 匹配约束
1,5,6,7,8 不匹配约束
1,2,3,4,5 小于 1,2,3,4,6 时，如何给定距离限制的组合排序？有没有一种方法可以在不计算具有较小Rank的组合的情况下进行排名？
您可以通过首先创建并填充一个 two-dimensional 数组来完成此操作，我将其称为 NVT for "number of valid tails"，以记录有效的数量"tails" 从给定值的特定位置开始。例如，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 的 "tail" 将由 5 加上 "tail" 从位置 #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，如下所示：
- 为"remaining rank"创建一个临时变量rr，初始等于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.
复杂度分析：
- Space:
- NVT 要求 O(nk) space.
- 将组合作为长度-k 数组返回本质上需要 O(k) space;但是如果我们 return 一次组合一个值（通过调用回调或打印到控制台或其他东西），那么计算本身实际上并不依赖于这个数组，只需要 O(1) 额外space.
- 除此之外，其他一切都可以在 O(1) space 中进行管理；我们不需要任何递归或临时数组或任何东西。
- 时间：
- 填充 NVT 需要 O(nkd) 时间。 （注意：如果d大于n，那么我们可以直接设置d等于n.)
- 给定 NVT，计算给定组合的排名需要 worst-case O(nk) 钛e.
- 给定 NVT，计算具有给定等级的组合需要 worst-case O(nk) 时间.
实现说明：上面的细节有点繁琐；如果您没有要查看的具体数据，很容易出现 off-by-one 错误，或者混淆两个变量，等等。由于您的示例只有 168 个有效组合，我建议生成所有这些组合，以便您在调试时可以参考它们。
可能的额外优化：如果您预计 n 非常大，并且您希望对 "rank" 和 "unrank" 组合进行大量查询，那么您可能会发现创建第二个数组很有用，我将其称为 NVTLT for "number of valid tails less than"，以记录从 a 开始的有效 "tails" 的数量某个位置的值 小于 给定值。例如，NVTLT[3][5] = NVT[3][1] + NVT [3][2] + NVT[3][3] + NVT[3][4]，或者如果您愿意，NVTLT[3][5] = NVTLT[3][4] + NVT[3][4 ]. （您可以将此作为 in-place 转换，完全覆盖 NVT，因此它是 O(nk) 无需额外 space.) 使用 NVTLT 而不是 NVT 进行查询将允许您进行二进制搜索对于值，而不是线性搜索，给出 worst-case O(k log n)时间而不是 O(nk) 时间。请注意，这个优化比上面的更棘手，所以即使你打算执行这个优化，我建议从上面开始，让它完美运行，然后再添加这个优化。
我想使用元素距离约束对组合进行排名和取消排名。所选元素不能重复。
例如：
n := 10个元素选择
k := 5 个元素正在被选择
d := 3 2 个所选元素之间的最大距离
1,3,5,8,9 匹配约束
1,5,6,7,8 不匹配约束
1,2,3,4,5 小于 1,2,3,4,6 时，如何给定距离限制的组合排序？有没有一种方法可以在不计算具有较小Rank的组合的情况下进行排名？
您可以通过首先创建并填充一个 two-dimensional 数组来完成此操作，我将其称为 NVT for "number of valid tails"，以记录有效的数量"tails" 从给定值的特定位置开始。例如，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 的 "tail" 将由 5 加上 "tail" 从位置 #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，如下所示：
- 为"remaining rank"创建一个临时变量rr，初始等于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.
复杂度分析：
- Space:
- NVT 要求 O(nk) space.
- 将组合作为长度-k 数组返回本质上需要 O(k) space;但是如果我们 return 一次组合一个值（通过调用回调或打印到控制台或其他东西），那么计算本身实际上并不依赖于这个数组，只需要 O(1) 额外space.
- 除此之外，其他一切都可以在 O(1) space 中进行管理；我们不需要任何递归或临时数组或任何东西。
- 时间：
- 填充 NVT 需要 O(nkd) 时间。 （注意：如果d大于n，那么我们可以直接设置d等于n.)
- 给定 NVT，计算给定组合的排名需要 worst-case O(nk) 钛e.
- 给定 NVT，计算具有给定等级的组合需要 worst-case O(nk) 时间.
实现说明：上面的细节有点繁琐；如果您没有要查看的具体数据，很容易出现 off-by-one 错误，或者混淆两个变量，等等。由于您的示例只有 168 个有效组合，我建议生成所有这些组合，以便您在调试时可以参考它们。
可能的额外优化：如果您预计 n 非常大，并且您希望对 "rank" 和 "unrank" 组合进行大量查询，那么您可能会发现创建第二个数组很有用，我将其称为 NVTLT for "number of valid tails less than"，以记录从 a 开始的有效 "tails" 的数量某个位置的值 小于 给定值。例如，NVTLT[3][5] = NVT[3][1] + NVT [3][2] + NVT[3][3] + NVT[3][4]，或者如果您愿意，NVTLT[3][5] = NVTLT[3][4] + NVT[3][4 ]. （您可以将此作为 in-place 转换，完全覆盖 NVT，因此它是 O(nk) 无需额外 space.) 使用 NVTLT 而不是 NVT 进行查询将允许您进行二进制搜索对于值，而不是线性搜索，给出 worst-case O(k log n)时间而不是 O(nk) 时间。请注意，这个优化比上面的更棘手，所以即使你打算执行这个优化，我建议从上面开始，让它完美运行，然后再添加这个优化。