列出所有成对的n个整数的最快解决方案? [英] Fastest solution to list all pairs of n integers?

问题描述

我想列出所有具有大n的整数[1, n]的所有可能对.我发现自己正在寻找最快的选择.到目前为止，这是我想出的.

I want to list all possible pairs of the integers [1, n] with a large n. I find myself looking for the fastest option. This is what I've come up with so far.

Matlab的 nchoosek 和

Matlab's nchoosek and combnk methods recommend n<15 for listing all possible combinations because of the explosive number of combinations. So how fast this is depends on the n.

pair = nchoosek(1:n, 2);

另一种选择是使用嵌套的for循环

Another option would be to use a nested for loop

kk =1;
pair = zeros(nchoosek(n, 2), 2);
for ii = 1:n
    for jj = ii+1:n
        pair(kk, :) = [ii, jj];
        kk = kk + 1;
    end
end  

这将相对较慢.

我还考虑过直接使用ind2sub函数

I also thought of using the ind2sub function directly

pair_adjacency = tril(ones(n),  -1);
[x, y] = ind2sub(size(pair_adjacency), find(pair_adjacency==1)); 
pair = [x, y];

以循环方式对这些方法进行计时，每次使用n=1000进行10次，我会变得最快到最慢

Timing these methods in a loop, 10 times each with n=1000, I get fastest to slowest

1. ind2sub(0.15秒)
2. for循环(16.3秒)
3. nchoosek(16.8秒)

看来ind2sub是远距离拍摄的最快方法.出于好奇，还有哪些其他选择可能会更快或更可能不会更快?

It seems like ind2sub is the fastest way to go by a long shot. Just out of curiosity, what are other options that may or may not be faster?

推荐答案

替换nchoosek(1:N,2)

To replace nchoosek(1:N,2)

使用bsxfun-

[Y,X] = find(bsxfun(@gt,[1:N]',[1:N]))
pair = [X, Y];

仅具有tril和find(不具有ind2sub)-

[y,x] = find(tril(true(N),-1))
pair = [X, Y];

这篇关于列出所有成对的n个整数的最快解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！