matlab - 有效地生成唯一的整数对

Question

在 MATLAB 中，我想生成 n [1, m] 范围内的随机整数对，其中每一对都是独一无二的。为了唯一性，我认为这对数字的顺序是无关紧要的，因此 [3, 10]等于[10, 3] . 此外，每对应由两个不同的整数组成；即 [3, 4]没关系，但是 [3, 3]会被拒绝。 编辑:应该以相同的可能性选择每个可能的对。

(显然对参数的约束是 n <= m(m-1)/2 。)

当 m 时，我已经能够成功地做到这一点很小，像这样:

m = 500; n = 10;                   % setting parameters

A = ((1:m)'*ones(1, m));           % each column has the numbers 1 -> m
idxs1 = squareform(tril(A', -1))'; 
idxs2 = squareform(tril(A, -1))';   
all_pairs = [idxs1, idxs2];        % this contains all possible pairs

idx_to_use = randperm( size(all_pairs, 1), n );  % choosing random n pairs
pairs = all_pairs(idx_to_use, :)       

pairs =

   254   414
   247   334
   111   146
   207   297
    45   390
   229   411
     9    16
    75   395
    12   338
    25   442

然而，矩阵A尺寸为 m x m ，意思是当m变大(例如超过 10,000)，MATLAB 内存不足。

我考虑过生成大量随机数 randi(m, [n, 2]) ，并反复拒绝重复的行，但我担心在 n 时陷入循环接近m(m-1)/2 .

是否有更简单、更清晰的方法来生成独特的不同整数对？

Answer 1

以正确的方式来看，简单、轻松。

你希望生成 n 对整数 [p,q]，使得 p 和 q 位于区间 [1,m] 内，并且 p

有多少可能的对？对的总数仅为 m*(m-1)/2。 (即从 1 到 m-1 的数字之和。)

因此我们可以在 [1,m*(m-1)/2] 范围内生成 n 个随机整数。 Randperm 做得很好。 (较旧的 matlab 版本不允许 randperm 的第二个参数。)

k = randperm(m/2*(m-1),n);

(请注意，我以一种有趣的方式用 m 编写了这个表达式，在一个可能很奇怪的地方除以 2。这避免了一些接近上限的 m 值的精度问题。)

现在，如果我们将每个可能的对 [p,q] 与 k 中的一个整数相关联，我们可以逆向工作，从 k 中生成的整数到一对 [p,q]。因此，该列表中的前几对是:

{[1,2], [1,3], [2,3], [1,4], [2,4], [3,4], ..., [m-1,m]}

我们可以将它们视为大小为 m × m 的严格上三角数组中的元素，也就是主对角线以上的元素。

q = floor(sqrt(8*(k-1) + 1)/2 + 1/2);
p = k - q.*(q-1)/2;

看到这些公式从 k 中展开的元素中恢复 p 和 q。我们可以说服自己这确实有效，但也许这里的一个简单方法就是这个测试:

k = 1:21;
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;
[k;p;q]'

ans =
     1     1     2
     2     1     3
     3     2     3
     4     1     4
     5     2     4
     6     3     4
     7     1     5
     8     2     5
     9     3     5
    10     4     5
    11     1     6
    12     2     6
    13     3     6
    14     4     6
    15     5     6
    16     1     7
    17     2     7
    18     3     7
    19     4     7
    20     5     7
    21     6     7

测试它的另一种方法是显示所有对都是为一个小案例生成的。

m = 5;
n = 10;
k = randperm(m/2*(m-1),n);
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;

sortrows([p;q]',[2 1])
ans =
     1     2
     1     3
     2     3
     1     4
     2     4
     3     4
     1     5
     2     5
     3     5
     4     5

是的，看起来一切正常。现在尝试使用 m 和 n 的一些大数字来测试使用的时间。

tic
m = 1e6;
n = 100000;
k = randperm(m/2*(m-1),n);
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;
toc

Elapsed time is 0.014689 seconds.

在由于 double 的精度错误而失败之前，该方案适用于大到大约 1e8 的 m。在 m/2*(m-1) 超过 2^53 之前，确切的限制应该是 m 不大于 134217728。一个很好的特性是不需要拒绝重复对。