[R] avoiding loops, gaining generality

[Bill Venables]

Matthew Wiener asks:

> Hi, all.
> 
> Given an array, I'd like to add elements whose location vectors are
> permutations of one another.  For example, in a 3-dimensional array, I'd
> add the elements in positions (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2)
> and (3,2,1); those in positions (1,2,4), (1,4,2), (2,1,4), (2,4,1),
> (4,1,2), and (4,2,1); and so on.  Elements with repeated positions
> -- (1,1,2) or (1,4,4), for example -- can be ignored.
> 
> In two dimensions, what I want can be done with (x + t(x))[lower.tri(x)]. 

One idea is to use a matrix index, of course.  The following is
not optimal by any means, but if you don't push it too far it
should work well enough.  First a couple of helper functions
whose purpose is self-evident (and the first now pretty
well-known):

subsets <- function(r, n, v = 1:n)
  if(r <= 0) NULL else
if(r >= n) v[1:n] else
rbind(cbind(v[1], Recall(r - 1, n - 1, v[-1])),
      Recall(r, n - 1, v[-1]))

permutations <- function(n, v = 1:n) {
  if(n == 1)
    return(v[1])
  X <- NULL
  for(i in 1:n)
    X <- rbind(X,
               cbind(v[i], permutations(n - 1, v[-i])))
  X
}

The following example uses a 3-dimensional array but the
generalization to any number of dimensions is no more
complicated.  It does assume that you are dealing with an array
with all dimensions having the same ranges.  If this is not the
case you will need to do some additional pruning, but that too
can be vectorized.

> A <- array(1:(4^3), dim = c(4,4,4))  # let's say

First generate the non-repeated index vectors as the rows of a
matrix:

> ind <- subsets(3, 4)
> ind
     [,1] [,2] [,3] 
[1,]    1    2    3
[2,]    1    2    4
[3,]    1    3    4
[4,]    2    3    4

Now generate the sums (this next step is the nub):

> sums <- apply(ind, 1, function(x) sum(A[permutations(3, x)]))

Finally give the vector names that identify which sum it is:

> names(sums) <- do.call("paste", c(data.frame(ind), sep = ","))

and here is what we have:

> sums
 1,2,3 1,2,4 1,3,4 2,3,4 
   132   174   216   258

Disclaimer: this was actually done in S, but you should never know!

> I'll summarize to the list.

Yes, please do, but I thought I would post this one anyway as my
puzzle of the month...

Bill Venables.

-- 
-----------------------------------------------------------------
Bill Venables, Statistician, CMIS Environmetrics Project.

Physical address:                            Postal address:
CSIRO Marine Laboratories,                   PO Box 120,       
233 Middle St, Cleveland, Queensland         Cleveland, Qld, 4163
AUSTRALIA                                    AUSTRALIA

Telephone: +61 7 3826 7251     Email: Bill.Venables at cmis.csiro.au     
      Fax: +61 7 3826 7304
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._