是否存在可生成数字集合随机不重复有序对的高效算法？

解决方案 #

一、首先解决查重效率低的问题

你当前遍历列表查重的方式时间复杂度是O(n)，完全可以替换成O(1)复杂度的查重方案，两种可选：

• 哈希集合：直接把有序对转成可哈希的结构（比如Python里的元组，其他语言可以转成num1,num2格式的字符串，或者拼接成一个大整数），存入Set结构，查询和插入都是O(1)，不需要遍历。
• 邻接矩阵：先给你的不连续数字集合映射成连续的整数索引，比如{3:0, 8:1, 10:2 ...}，再维护一个二维布尔矩阵used[m][m]（m是集合当前大小），used[a][b] = True表示索引a对应数字和索引b对应数字的配对已经用过，查询和插入都是O(1)，m在1000以内的时候，矩阵只需要不到1MB的存储空间，开销极低。

树形结构对于这个场景没有优势，查询和更新复杂度都高于哈希和矩阵，不需要考虑。

二、解决后期随机重试次数过多的问题

可以用有序对编号映射法，完全避免重试，也不需要预先生成所有配对：

1. 首先给集合N的所有元素映射连续索引，总共有m个元素时，所有合法的非自有序对总共有m*(m-1)个，每个对都可以和0到m*(m-1)-1区间的整数一一对应：
   给定任意整数k，转换为有序对的规则：

   a = k // (m-1)
   b = k % (m-1)
   if b >= a:
       b += 1
   最终有序对为 (num_list[a], num_list[b])
   

   这个规则可以保证a≠b，且每个k对应唯一的合法有序对。
2. 要生成不重复的随机有序对，只需要生成这个区间内不重复的随机整数即可，两种实现方式：
   • 如果你需要生成的配对数远小于总配对数：可以用哈希集合存已经用过的k值，每次随机生成一个k，不在已用集合里就用，用完把k加进集合，比直接随机两个数查重的命中率高很多。
   • 如果你需要生成大部分甚至全部配对：可以用线性同余生成器（LCG）生成覆盖整个区间的不重复伪随机序列，完全不需要维护已用集合，每次生成的k天然不重复，直到整个区间遍历完为止，全程无重试。

三、动态新增元素的处理

这个方案完美支持动态往N里加元素：
当新增一个元素时，给它分配新的索引m（原有集合大小为m），总配对数变成(m+1)*m，新增的配对是所有原有元素和新元素的双向配对，刚好对应区间[m*(m-1), (m+1)*m - 1]，原有已经生成的配对和已用k值完全不需要修改，直接扩大随机数生成的区间即可。
如果用矩阵存储的话，只需要给矩阵加一行、给每一行加一列，默认值全为False即可，不需要修改原有矩阵的内容。

内容的提问来源于stack exchange，提问作者subski