performance - sirven - propiedades de los numeros enteros

La solución más rápida para enumerar todos los pares de n enteros?

Question

Quiero enumerar todos los pares posibles de los enteros [1, n] con una gran n . Me encuentro buscando la opción más rápida. Esto es lo que he propuesto hasta ahora.

Los métodos nchoosek y combnk Matlab recomiendan n<15 para enumerar todas las combinaciones posibles debido a la cantidad explosiva de combinaciones. Entonces, ¿qué tan rápido es esto depende de la n.

pair = nchoosek(1:n, 2);

Otra opción sería usar un bucle for anidado

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 

Esto sería relativamente lento.

También pensé en usar la función ind2sub directamente

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

Sincronizando estos métodos en un bucle, 10 veces cada uno con n=1000 , obtengo el más rápido al más lento

1. ind2sub (0.15 seg)
2. para loop (16.3 seg)
3. nchoosek (16.8 sec)

Parece que ind2sub es la forma más rápida de conseguirlo. Solo por curiosidad, ¿qué otras opciones pueden ser más rápidas o no?

Answer 1

Para reemplazar nchoosek(1:N,2)

Con bsxfun -

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

Con tril y find solo (sin ind2sub ) -

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