我有一个不连续的数字N列表(例如{ 1, 2, 3, 6, 8, 10})，我需要逐步创建N中的随机数字对，并将它们存储在一个列表中，其中不能有两次相同的对。
例如，对于一个包含3个不同数字的列表，有6对可能的数字对(不包括相同的数字对):
对于列表{ 4, 8, 9 }，可能的对有:
(4,8) (4,9) (8,4) (8,9) (9,4) (9,8)
例如，当我们到达一个数字列表大小为30时，我们得到870对可能的配对，而用我目前的方法，可能的配对越多，效率就越低。
现在我的策略是一个大小为30的数字列表，例如:
N = { 3, 8, 10, 15, 16, ... } // size = 30
// Lets say I have already a list with 200 different pairs
my_pairs = { (8,16), (23, 32), (16,10), ... }
// Get two random numbers in the list
rn1 = random(N)
rn2 = random(N)
Loop through my_pairs to see if the pair (rn1,rn2) has already been generated
If there is one, we pick two new numbers rn1 & rn2 at random and retry adding them to my_pairs
If not then we add it to the list
问题是my_pairs中有越多的pair，一对不在列表中的可能性就越小。因此，我们必须多次检查多个随机对，并且每次都要遍历列表。
我可以尝试在开始时生成所有可能的配对，洗牌列表并在每次需要向列表中添加随机配对时弹出一个元素。但是，当我的Numbers列表大小增加时(例如100个不同的数字对应9900个可能的对)，存储所有可能的对将占用大量空间。在我的过程中，我在N中添加了数字，所以我不能每次都重新计算所有可能的对。
是否存在生成随机唯一对的算法?
也许使用矩阵或将我的对存储在某种树状图中会更快?
这在很大程度上取决于你想优化什么。
如果你想让事情保持简单和易于维护，拥有一个所有生成的数字的哈希集听起来是合理的。这里的假设是，检查成员关系和添加新元素的平均时间应该是O(1)。
如果您担心空间需求，因为您经常使用多达70%的可能对，那么您可以优化空间。要做到这一点，我首先建立每个可能的对和单个整数之间的映射。我会以一种允许在N中轻松添加更多数字的方式来实现。
+0 +1
0 (0,1) (1,0)
2 (0,2) (2,0)
4 (1,2) (2,1)
6 (0,3) (3,0)
8 (1,3) (3,1)
10 (2,3) (3,2)
这样可以将单个整数i映射到序列N中的一对索引(a,b)，然后您可以在N中查找它们以将它们转换为实际的元素对。虽然从i到(a,b)的转换需要在某个地方使用平方根，但是您可以为这个映射提出公式。
当你有了这个，从一组任意数中选择一对的任务变成了从连续整数范围中选择一个整数的任务。现在您可以使用位映射来非常有效地存储每个索引，您是否已经在过去选择了该索引。对于选择对的百分比较低，位图可能比只选择值的哈希图消耗更多的内存，但当您接近70%的所有对被选中时，它将更加高效。我希望一个典型的哈希映射条目至少消耗3×64=192位的存储空间，所以当所有值的1/192=0.52%被选中时，位图将开始节省内存。增长位图可能仍然是昂贵的，所以估计N的最大大小可能有助于预先分配足够的内存。
如果你有一个昂贵的随机数生成器，或者担心整个事情的最坏情况的时间复杂度，那么你可能想要避免多次尝试，可能会导致已经选择的对。为了实现这一点，您可能会将所有选中的对的集合存储在某种搜索树中，其中每个节点还跟踪其子树包含多少叶节点。这样，你就可以在一个范围内生成一个随机数，这个随机数对应于还没有被选中的对的大小，然后使用树中的信息，将所有已经被选中的小于这个值的下标的数量加到选中的值上。我还没有算出所有的细节，但我相信有了这个，它应该有可能把它变成O(log n)最坏的情况下的时间复杂度，而不是O(1)的平均情况，但O(n)甚至O(∞)最坏的情况，我们之前有过。