algorithm - 在排序列表中查找项目的索引

Question

我们有一个生成的列表：

（数字从 0 到 3，它们的总和是 3）

如何在不计算它们的情况下找到组合在什么地方？前任。201 -> index=8 在此先感谢。

score 4 · Accepted Answer

如果您的号码的数字是 ABC，那么索引是：

ndx = A * (8 - A + 1) / 2 + B + 1;

例如，对于值 ABC=201，我们将有：

ndx = 2 * (8 - 2 + 1) / 2 + 0 + 1 = 8;

实际上，值 201 的索引为 8。

score 1 · Accepted Answer

不是一个完整的答案，但我认为这是一个好的开始。

如果您将每个数字视为两个二进制数字，您会得到：

 1. 003  00 00 11
 2. 012  00 01 10
 3. 021  00 10 01
 4. 030  00 11 00
 5. 102  01 00 10
 6. 111  01 01 01
 7. 120  01 10 00
 8. 201  10 00 01
 9. 210  10 01 00
10. 300  11 00 00

如果忽略右侧的数字列，则前七项（值 003 到 120）是数字 0 到 6 的二进制表示。

接下来的两项具有值 8 和 9，最后一项是 12。

因此，我们可以将数字转换为粗略索引：

ix = 4*first_digit + second_digit

然后调整：

if (first_digit < 2)
    ix = ix + 1
else if (first_digit == 3)
    ix = ix - 2

我对那里的条件不满意。有没有一种数学方法可以进行这种翻译：

0 => 1
1 => 1
2 => 0
3 => -2

score 1 · Accepted Answer

对，我一直在做的问题下的评论是假设您想直接从当前值转到索引，而不执行搜索。也就是说，对条目的数字进行一些检查并将其转换为 1 索引的数字。

请注意，这个答案是定向且不完整的，只是显示了我解决问题的方式。

查看您的示例，如果我们将每个条目视为由 3 位数字(z_i, y_i, x_i)组成，那么您将获得以下序列：

003; z=0, y=0, x=3
012; z=0, y=1, x=2
021; z=0, y=2, x=1
030; z=0, y=3, x=0
102; z=1, y=0, x=2
111; z=1, y=1, x=1
120; z=1, y=2, x=0
201; z=2, y=0, x=1
210; z=2, y=1, x=0
300; z=3, y=0, x=0

如果最大位数为k (=3)，则：

x_i = 3, 2, 1, 0, 2, 1, 0, 1, 0, 0 = k, k-1, ..., 0, k-1, ... 0, ......, 0

y_i = 0, 1, 2, 3, 0, 1, 2, 0, 1, 0 = 0, 1, ..., k, 0, ..., k-1, ......, 0

z_i = 0, 0, 0, 0, 1, 1, 1, 2, 2, 3 = k+1 x 0, k x 1, ......., 1 x k

如您所见，y_i数字按顺序重复上升，在每次完成时将z_i向上敲。

如果你有更多的数字，模式会变得更复杂，但仍然遵循类似的模式。

对于k=4：