algorithm - 索引集合的(无序)对

Question

这是一个自动回答的问题，源自this more specific question在选择错误的(恕我直言)答案后，OP 似乎失去了兴趣。

我确实检查了以前关于这个主题的问题，但似乎没有一个能解决这个问题。

那有什么用？

假设您有 4 个人:Abdul、Beatrix、Charlie 和 Daria。
您想存储有关这些人对彼此的感觉的信息

Abdul and Beatrix are in love
Beatrix and Charlie hate each other
Abdul and Charlie are good friends
Daria and Beatrix don't know each other
etc.

在简洁且没有诗意的计算机世界中，这可以转化为:

relation (Abdul  , Beatrix) = love;
relation (Beatrix, Charlie) = hate;
relation (Abdul  , Charlie) = friendship;
etc.

换句话说，如果你想映射每一对人之间的关系，你将需要一个数据结构，允许你为每一对人维护一个唯一的值。

虽然有许多方法可以实现合适的数据结构，但在某些情况下您可能希望此表是一个固定大小的数组，直接由表示给定关系的对索引。

一些定义:

给定 I_N 前 N 个自然整数的集合，我们称 P_N 为 I_{N 的所有无序对 (a,b) 的序列} 这样 a <> b，按字典顺序排序。

在(希望)不太隐晦的英语中，P 列举了 I 的两个元素之间的所有可能关系。

示例(对于 N = 4):

I₄ = (0,1,2,3)
P₄ = ((0,1),(0,2),(0,3),(1,2),(1,3),(2,3))

注意P_N的基数是N(N-1)/2，所以
P_N 的最紧凑的从零开始的索引将在 [0..N(N-1)/2-1] 范围内。

问题:

我们如何以紧凑高效的方式索引 P_N？

换句话说，

• 定义函数 p_N(a,b)，给定 I_N 的一对 (a,b) 元素，生成 P< 的唯一索引sub>N 在范围 [0..N(N-1)/2-1]
• 定义反向索引函数 p_N^-1，给定 P_N 的索引，将生成相应的 (a, b) 对

P_N 的排列方式不太重要，但字典顺序可能是最方便的。

例子:

P₄ = ((0,1),(0,2),(0,3),(1,2),(1,3),(2, 3))
p₄(1,3) = 4
p₄^-1(4) = (1,3)

Answer 1

到目前为止，我在这里看到的两个答案都可以很好地进行第一次计算，但向后计算需要循环，这不是必需的。

考虑以下带有 n=5 的示例, 显示元素是如何编号的。

    0   1   2   3   4
  +---+---+---+---+---+
0 |   |   |   |   |   |
  +---+---+---+---+---+
1 | 0 |   |   |   |   |
  +---+---+---+---+---+
2 | 1 | 4 |   |   |   |
  +---+---+---+---+---+
3 | 2 | 5 | 7 |   |   |
  +---+---+---+---+---+
4 | 3 | 6 | 8 | 9 |   |
  +---+---+---+---+---+

给定一个元组 (x, y) (假设 x < y )，列中的第一个索引 x由

n-1 + n-2 + ... + n-x = (n-1 + n-x) * x / 2 = (2n - x - 1) * x / 2

该列中的偏移量只是 y - x - 1 .这会产生总表达式

p_n(x, y) = (2n - x - 1) * x / 2 + y-x-1 = (2n - x - 3) * x / 2 + y-1

---

现在，反过来是很棘手的。我们有一些值 p和 n并且需要找到 x和 y .假设我们正在寻找列中的第一个单元格，即 y = x+1，我们可以让我们的生活更简单。 .如果我们把它代入上面的公式，我们得到

p = (2n - x - 1) * x / 2

重写这个公式得到

x^2 - (2n-1) * x + 2p = 0

这是一个简单的二次方程，可以求解 x:

x = [(2n-1) - Sqrt((2n-1)^2 - 8p)] / 2

当然，我们可能高估了x ，因为我们假设 y 的可能值最低.然而，我们并没有那么远(仍在右列)，所以向下舍入该值足以得到真实的 x。 .

插入 x我们在原始公式中找到的值产生了一个非常简单的方程 y :

x = Floor( [(2n-1) - Sqrt((2n-1)^2 - 8p)] / 2 )
y = p - (2n - x - 3) * x / 2 + 1

---

可以说，取一个数的平方根是一个缓慢的操作(这是事实)，但是对于更大的 n 值，这种方法将优于循环。 .