等级和等级与约束的组合 [英] Rank and unrank Combination with constraints

问题描述

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

I want to rank and unrank combinations with an Element distance constraint. Selected elements cannot repeated.

例如：

n：= 10 个元素

k：= 5 个元素被选择

d：= 3 2个所选元素之间的最大距离

d := 3 max distance between 2 choosen elements

1,3,5,8,9 匹配约束

1,5,6,7， 8 不匹配约束

如何在给定距离约束的情况下对组合进行排名，其中 1,2,3， 4,5 小于 1,2,3,4,6 吗？

How can ranking the combination with given distance constraint, where 1,2,3,4,5 is smaller than 1,2,3,4,6 ? Is there a way do the ranking without compute the combinations with smaller Rank?

推荐答案

您可以通过首先创建并填充一个二维数组，我将其称为有效尾数的 NVT ，以记录从给定值开始于特定位置的有效尾数。例如， NVT [4] [6] =  3，因为在＃4位置具有6的组合可以以3种不同的方式结束：（…，  6，  7），（…，6、8）和（…，6、9）。

You can do this by first creating and populating a two-dimensional array, which I will call NVT for "number of valid tails", to record the number of valid "tails" that start at a certain position with a given value. For example, NVT[4][6] = 3, because a combination that has 6 in position #4 can end in 3 distinct ways: (…, 6, 7), (…, 6, 8), and (…, 6, 9).

• 要填充 NVT ，请从 NVT [ k ] […]开始，该行仅占1的一行。然后回到原来的位置；例如， NVT [2] [5]  =  NVT [3] [6]&+ b> NVT [ 3] [7] +  NVT [3] [8]，因为在位置＃3处开始的尾巴的值5将由该5加上在位置开始的尾巴位置＃4，其值分别为6、7或8。


• 请注意，我们不在乎是否存在有效的方法来到达给定的尾巴。例如， NVT [4] [1] =  3是因为有效的尾巴（1，  2），（1，  3）和（1，  4），即使不存在形式（...，  1， __）的 complete 组合。

• To populate NVT, start with NVT[k][…], which is just a row of all 1s. Then work your way back to earlier positions; for example, NVT[2][5] = NVT[3][6] + NVT[3][7] + NVT[3][8], because a "tail" starting at position #3 with value 5 will consist of that 5 plus a "tail" starting at position #4 with value 6, 7, or 8.
• Note that we don't care whether there's actually a valid way to reach a given tail. For example, NVT[4][1] = 3 because of the valid tails (1, 2), (1, 3), and (1, 4), even though there are no complete combinations of the form (…, 1, _).

完成此操作后，可以计算组合 C 的等级，如下所示：

Once you've done that, you can compute the rank of a combination C as follows:

• 对于位置1，从位置1开始计数所有有效尾部，且其值小于 C [1]。例如，如果 C 以3开头，则为 NVT [1] [1] ++ nemNVT [1] [2]，代表以1或2开头的所有组合。


• 然后对所有后续位置执行相同的操作。这些表示的组合将以与 C 相同的方式开始直到指定位置，然后在该位置具有较小的值。


• 例如，如果 C 是（1，  3，  5，  8，  9），结果是
  
  0  +
  
  （ NVT [2] [1]  +  NVT [2] [2]）+
  
  （ NVT [3] [1] +  NVT [3] [2] ++ nbsp; 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]）。

• For position #1, count up all the valid tails starting at position #1 with a value less than C[1]. For example, if C starts with 3, then this will be NVT[1][1] + NVT[1][2], representing all combinations that start with 1 or 2.
• Then do the same for all subsequent positions. These will represent combinations that start off the same way as C up until a given position, but then have a lesser value at that position.
• For example, if C is (1, 3, 5, 8, 9), this comes out to
  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]).

相反，您可以找到combinat离子 C 具有给定等级 r 如下：

Conversely, you can find the combination C with a given rank r as follows:

• 创建一个临时变量 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& minus; 66  =  = 9）。


• 然后对所有后续操作都这样做位置时，请务必记住与先前位置相同的最小值。继续我们的示例，其中 r   =  75， C [1]  =  2和 rr   =  ; 9，我们知道 C [2] ≥  3;并且由于 NVT [2] [3]  =  23 >  rr ，我们立即发现 C [2]   =  3。

• Create a temporary variable rr, for "remaining rank", initially equal to r.
• To find C[1] — the value in position #1 — count up valid tails starting at position #1, starting with the least possible value (namely 1), stopping once this would exceed rr. For example, since NVT[1][1] = 66 and NVT[1][2] = 27, the combination with rank 75 must start with 2 (because 75 ≥ 66 and 75 < 66 + 27). Then subtract this sum from rr (in this case leaving 75 − 66 = 9).
• Then do the same for all subsequent positions, making sure to keep in mind the least possible value given what was in the previous position. Continuing our example with r = 75, C[1] = 2, and rr = 9, we know that C[2] ≥ 3; and since NVT[2][3] = 23 > rr, we immediately find that C[2] = 3.

复杂度分析：

• 空格：
  
  
  
  
  • NVT 需要 O （ nk ）空间。
  
  
  • 将组合返回为长度 k 数组本质上需要 O （ k ）空间；但是如果我们一次返回一个组合值（通过调用回调或打印到控制台等），则计算本身实际上并不依赖于此数组，只需要 O （ 1）多余的空间。
  
  
  • 除此之外，其他所有内容都可以在 O （1）空间中进行管理；我们不需要任何递归或临时数组之类的东西。
  
  
  • Space:
    • NVT requires O(nk) space.
    • Returning a combination as a length-k array inherently requires O(k) space; but if we return the combination one value at a time (by invoking a callback or printing to a console or something), then the computation itself doesn't actually depend on this array, and only requires O(1) extra space.
    • Aside from that, everything else can be managed in O(1) space; we don't need any recursion or temporary arrays or anything.
    
    
    • 填充 NVT 需要花费 O （ nkd ）时间。 （注意：如果 d 大于 n ，那么我们可以将 d 设置为等于 n 。）
    
    
    • 给出 NVT ，计算给定组合的排名需要最坏情况的 O （ nk ）时间
    
    
    • 给定 NVT ，计算具有给定等级的组合会采用最坏情况的 O （ nk ）时间。
    
    
    • Populating NVT takes O(nkd) time. (Note: if d is greater than n, then we can just set d equal to n.)
    • Given NVT, computing the rank of a given combination takes worst-case O(nk) time.
    • Given NVT, computing the combination with a given rank takes worst-case O(nk) time.

    实施注意：上面的细节有些古怪；如果您没有具体的数据需要查看，那么很容易出现一个错误，或者混淆两个变量，或者什么都不会。由于您的示例只有168个有效组合，因此我建议生成所有组合，以便在调试期间可以引用它们。

    Implementation note: The details of the above are a bit fiddly; it would be easy to get an off-by-one error, or mix up two variables, or whatnot, if you don't have concrete data to look at. Since there are only 168 valid combinations for your example, I recommend generating all of them, so that you can reference them during debugging.

    可能的其他优化：如果您期望 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 ）时间。请注意，此优化甚至比上述优化更为棘手，因此，即使您打算执行此优化，我还是建议从上述内容开始，使其完美运行，然后再添加此优化。

    Possible additional optimization: If you expect n to be quite large, and you expect to do a lot of queries to "rank" and "unrank" combinations, then you might find it useful to create a second array, which I will call NVTLT for "number of valid tails less than", to record the number of valid "tails" that start at a certain position with a value less than a given value. For example, NVTLT[3][5] = NVT[3][1] + NVT[3][2] + NVT[3][3] + NVT[3][4], or if you prefer, NVTLT[3][5] = NVTLT[3][4] + NVT[3][4]. (You can do this as an in-place transformation, completely overwriting NVT, so it's an O(nk) pass with no additional space.) Using NVTLT instead of NVT for your queries will let you do binary search for values, rather than linear search, giving worst-case O(k log n) time instead of O(nk) time. Note that this optimization is even trickier than the above, so even if you intend to perform this optimization, I recommend starting with the above, getting it working perfectly, and only then adding this optimization.

    这篇关于等级和等级与约束的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！