索引集合的（无序）对

这是一个自动回答的问题，源自这个更具体的问题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.

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

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

一些定义：

given I_N the set of the first N natural integers, let's call P_N the sequence of all unordered pairs (a,b) of I_N such that a <> b, sorted in lexicographic order.

用（希望）不那么神秘的英语，P 列举了 I 的两个元素之间所有可能的关系.

示例（对于 N = 4）：

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

Note that the cardinality of P_N is N(N-1)/2, so
the most compact zero-based index of P_N will be in the [0..N(N-1)/2-1] range.

问题：

how can we index P_N in a compact and efficient way?

换句话说，

• define a function p_N(a,b) that, given a pair (a,b) of elements of I_N, produces a unique index of P_N in the range [0..N(N-1)/2-1]
• define the reverse-indexing function p_N^-1 that, given an index of P_N, will produce the corresponding (a,b) pair

The way P_N is arranged is of lesser importance, but a lexicographic order would probably be the most convenient.

example:

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

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

考虑以下示例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 and n并且需要找到x and 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.