Howto to get all pairs from a vector

[Niels Henrik Bruun]

Hi
I had the problem of getting all combinations of elements in a vector.
Here is a simple solution to the problem using recursive calls of a function:

mata:
    function do_pairs(colvector v)
    {
        if ((R = rows(v)) > 2) {
            return(J(R-1, 1, v[1]), (rest=v[2::R]) \ do_pairs(rest))
        } else if (R == 2) {
            return(v')
        }
    }
end

And som demos:

:         do_pairs( ("a", "b", "c", "d")' )
       1   2
    +---------+
  1 |  a   b  |
  2 |  a   c  |
  3 |  a   d  |
  4 |  b   c  |
  5 |  b   d  |
  6 |  c   d  |
    +---------+

:         do_pairs( ("a", "b", "c")' )
       1   2
    +---------+
  1 |  a   b  |
  2 |  a   c  |
  3 |  b   c  |
    +---------+

:         do_pairs( ("a", "b")' )
       1   2
    +---------+
  1 |  a   b  |
    +---------+

:         do_pairs( ("a")' )

:         do_pairs( (1::6) )
        1   2
     +---------+
   1 |  1   2  |
   2 |  1   3  |
   3 |  1   4  |
   4 |  1   5  |
   5 |  1   6  |
   6 |  2   3  |
   7 |  2   4  |
   8 |  2   5  |
   9 |  2   6  |
  10 |  3   4  |
  11 |  3   5  |
  12 |  3   6  |
  13 |  4   5  |
  14 |  4   6  |
  15 |  5   6  |
     +---------+

I hope you find it usefull

[Matthew J. Baker]

Niels --

That's a nice piece of programming. I could be wrong, but it seems like it is easily generalizable to triples, quartets, etc. It also reminds me of the old adage "In order to understand recursion, you must first understand recursion."

Matt

[Rafal Raciborski (StataCorp)]

Here is a faster alternative to Niels' program that does not involve recursion. Instead, I preallocate the space for the result matrix and fill in the matrix in a loop.

cscript
 
mata:
 
transmorphic matrix do_pairs(colvector v) {
    if ((R = rows(v)) > 2) {
        return(J(R-1, 1, v[1]), (rest=v[2::R]) \ do_pairs(rest))
    } else if (R == 2) {
        return(v')
    }
}
 
transmorphic matrix do_pairs2(transmorphic colvector v) {
    real scalar n, i, c1, c2
    transmorphic matrix res
    n = rows(v)
    res = J(n*(n-1)/2,2,missingof(v))
    if (n>1) {
        c1 = 1
        c2 = n -1
        for (i=1; i<n; i++) {
            res[|c1,1\c2,2|] = ( J(n-i,1,v[i]) , v[i+1..n] )
            c1 = c2 +1
            c2 = c2 +n -i -1
        }
    }
    return(res)
}
 
end

And here are some timings I ran on my machine. Replace n with different values to compare times.

mata:
    n = 1000
    X = 1::n
    
    timer_clear()
    
    timer_on(1)
    res1 = do_pairs(X)
    timer_off(1)
    
    timer_on(2)
    res2 = do_pairs2(X)
    timer_off(2)
    
    timer()
    
    asserteq(res1,res2)
end

n    do_pairs    do_pairs2
---------------------------------
100        .001     .000
500        .139     .004
1000       1.039     .032
2500      15.590     .100
5000     125.826     .351    
7500     452.565     .763
10000    3209.983    2.238
---------------------------------

[Niels Henrik Bruun]

Hi
Thank you both.
This is interesting.

I felt inspired to create a 3. function which did not use recursion:

transmorphic matrix do_pairs3(colvector v) {
    if ((R = rows(v)) > 1) {
        out = J(0,2,missingof(v))
        for(r=1;r<R;r++) out = out \ (J(R-r, 1, v[r]), v[r+1::R])
        return(out)
    }
}

And the race showed:

---------------------------------------------------------------------------------------------------
timer report
  1.       1.29 /        1 =      1.29
  2.       .012 /        1 =      .012
  3.       1.75 /        1 =     1.752
---------------------------------------------------------------------------------------------------

It seems like it not recursion but more reservation of space upfront by

res = J(n*(n-1)/2,2,missingof(v))

that makes the speed