R help - Sep 1999 - avoiding loops, gaining generality

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)]. 

My idea for duplicating this in more than two dimensions involve loops
and if statements, and require me to write a separate function for each
number of dimensions.  Something like:

for(i1 in 1:dim(x)[1]){
  for(i2 in 1:dim(x)[2]){
	...
    for(in in 1:dim(x)[n]){
      	temp.vec <- c(i1, i2, ..., in)
	ans[sort(temp.vec)] <- ans[sort(temp.vec)] + x[temp.vec]
    }
   ...
  }
}

This seems like a very clunky approach, but so far I haven't come up with
anything better.

I'm wondering whether any of the R aficionados out there can recommend a
way that works for any dimension, and is reasonably efficient. In fact,
even a reasonably efficient way to do it for a fixed number of dimensions
(with a separate function for each number of dimensions) would be helpful. 

I'll summarize to the list.

Thanks,

Matt

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

Hi, all.

Dr. Venables's reply to my question about avoiding loops (using the
subsets and permutations functions) was the first and only one, presumably
because it solves the problem so well.  I'm posting this to let anyone who
may have been waiting know that there haven't been any other solutions to
consider. 

Many thanks to Dr. Venables, and to everyone else who has helped with
questions. 

Matt Wiener


-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._