possible combinations without zeros

So I am looking for a way to get possible combinations of two integers from an array, say I have

v = [0, 1, 2, 0, 4]

I would like at the end, conceptually a matrix like this, C = v^T v where v^T is the Transpose of the vector so 开发者_开发百科you get a matrix with some nonzeros and the entries will be the combinations of two integers. For row 1 for instance,

(0,0) (1,1) (1,2) (0,0) (0,4)

but I only need (1,1) (1,2) also similar reasoning holds for the other rows in my conceptual matrix visualisation. I can do this by two nested loops by checking if they include 0 or not. Question is: are there some algorithms for these kinds of combinatorial tasks that would do that better than nested loops?

---

There is no way to generate this output "matrix" without a 2D nested loop (or something directly equivalent). So given you'll have the loops anyway, it's trivial to add the conditional checking.

I suppose you could pre-sort the array, and then start your loop counters at the first non-zero value...

---

Depending on how many zeroes you have, you could use a sparse matrix data structure and that may reduce the problem from O(n^2) to something slightly smaller (depending on how many zeroes you have).

If you ignore the zeroes for a second, N choose 2 combinations is equal to n^2/2-n/2 combinations. Similarly there are n*(n-1) 2-permutations of n. So no matter whether you are doing combinations or permutations, you still need an algorithm that is worst case O(n^2). Note your matrix would possibly be symmetric depending on certain assumptions, but that would not be enough to change it from O(n^2) because it would essentially be O((n/2)^2) which is still O(n^2).