索引（无序）对一组 [英] Indexing the (unordered) pairs of a set

问题描述

这是一个自动回答的问题，源自<一个href="http://stackoverflow.com/questions/21326087/decoding-via-number-combinations-algorithm-in-python-3/21328523#21328523">this更具体的问题其中OP似乎有选择错误的（恕我直言）答案后失去了兴趣。

This is an auto-answered question, originating from this more specific question where the OP seems to have lost interest after selecting a wrong (IMHO) answer.

我做了关于这个问题的检查previous的问题，但似乎没有解决这个问题。

I did check previous questions on the subject, but none seemed to tackle the problem.

假设你有4人：阿卜杜勒，贝娅特丽克丝，查理和达里亚
要存储有关这些人的感觉对彼此的方式信息

Imagine you have 4 people: Abdul, Beatrix, Charlie and Daria.
You want to store informations about the way these persons feel toward each other

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.

在简洁，缺乏诗歌界的计算机，即可以转化为：

In the terse and devoid of poetry world of computers, that could translate to:

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

在换句话说，如果你想映射每对人与人之间的关系，你需要一个数据结构，它可以让你保持每对人的独特的价值。

In other words, if you want to map the relations between each pair of people, you will need a data structure that allows you to maintain a unique value for each pair of people.

虽然有几十个实现合适的数据结构的方式，你可能会在某些情况下，希望这个表是一个固定大小的数组由对直接索引重新presenting一个给定的关系。

Although there are dozens of ways of implementing a suitable data structure, you might want in some case this table to be a fixed-size array directly indexed by the pairs representing a given relation.

给我 _N 集合中的第n个自然整数的，我们姑且称之为P <子> N 所有无序对的序列（A，B）的I <子>ñ 使得＆LT;> B，排序字典序

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.

在（希望）不太神秘的英语， 点列举两个元素之间所有可能的关系，我的

In (hopefully) less cryptic English, P enumerates all the possible relations between two elements of I.

例如（对于N = 4）：

example (for N = 4):

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;我 ₄ ＆NBSP;＆NBSP; =（0,1,2,3）
＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP，P <子> 4 =（（0,1），（0,2），（0,3），（1,2），（1,3） ，（2,3））

     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]范围

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.

怎能指数P <子> N 在一个紧凑和有效的方式？

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

在等温线，

• 定义一个函数P <子> N （A，B），给定一对（一，二）我的元素 _N ，产生P的唯一索引<子> N 的范围[0..N（N-1）/ 2-1]
• 定义反向索引功能，P <子> N ¹ ，鉴于P <子> N 的索引，就会产生相应的（A， B）对

• 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

方式P <子> N 安排是不太重要，但字典顺序很可能是最方便的。

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

例如：

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; P <子> 4 =（（0,1），（0,2），（0,3），（1,2） ，（1,3），（2,3））
＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; P <子> 4 （1,3）= 4
＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; P <子> 4 ¹ （4）=（1,3）

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

推荐答案

这两个答案我在这里看到，到目前为止做的第一件计算罚款，但落后的计算需要一个循环，这是没有必要的。

Both answers I see here so far do the first calculation fine, but the backward calculation requires looping, which is not necessary.

考虑下面的例子与 N = 5 ，展示如何元素编号。

Consider the following example with n=5, showing how the elements are numbered.

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

给出一个数组（X，Y）（假设 X＆LT; Y ），第一列的索引 X 是

Given a tuple (x, y) (assuming x < y), the first index in column x is given by

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

在该列偏移简直是Ÿ - X - 1 。这产生了总前pression

The offset in that column is simply y - x - 1. This yields the total expression

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

---

现在，周围走另一条路是棘手。我们有一些值 P 和 N ，并需要找到 X 和是。我们可以让我们的生活更简单，虽然假设我们要找列的第一个单元格，即 Y = X + 1 。如果我们插在这个公式中上面，我们得到

---

Now, going the other way around is tricky. We have some values p and n and need to find x and y. We can make our life simpler though by assuming we're looking for the first cell in the column, i.e. y = x+1. If we plug this in in the formula above, we obtain

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

重写这个公式收益率

Rewriting this formula yields

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

这是一个简单的二次方程和可以解决对于x

which is a simple quadratic equation and can be solved for x:

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

当然，我们可能高估 X ，因为我们承担了 y中的最低值。但是，我们并不那么遥远（仍然在右列），所以舍去的值就足以获得真正的 X 。

Of course, we likely overestimated x, because we assumed the lowest possible value for y. However, we are not that far off (still in the right column), so rounding down the value is enough to get the real x.

封堵 X 值，我们发现到原来的公式得出一个非常简单的公式是：

Plugging the x value we found into the original formula yields a very easy equation for y:

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

---

可以说，服用一个数的平方根是一个缓慢的操作（这是真的），但这种方法会胜过一个循环为更大值 N

这篇关于索引（无序）对一组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！