[R] combinatorial programming problem

[Charles C. Berry]

On Mon, 29 May 2006, Martin Maechler wrote:

>>>>>> "SpG" == Spencer Graves <spencer.graves at pdf.com>
>>>>>>     on Sun, 28 May 2006 16:21:53 -0700 writes:
>
>    SpG> 	  I'm not sure I understand your question, but
>    SpG> are you asking how to index choose(k, r) objects?
>    SpG> Almost 3 years ago, I asked a question like this.  Andy
>    SpG> Liaw referred me to nchoosek(vsn)
>    SpG> (http://finzi.psych.upenn.edu/R/Rhelp02a/archive/12518.html).
>    SpG> This produces a matrix of dimension (r, choose(k, r)).
>    SpG> With this matrix, you could convert an integer between
>    SpG> 1 and choose(k, r) into an r-vector by table look-up.
>    SpG> Reading the code for nchoosek might help you further if
>    SpG> this does not seem appropriate for you.
>
> Note that *if* the above is the answer,
> I'd rather recommend to use  combn() from package "combinat",
> since a (slightly improved) version of combn() has been part of R-devel
> (to become R 2.4.0 in October) for a while.  Also, combn() from
> "combinat" precedes nchoosek() historically and is also faster.

And if the problem is large enough to bog down combn() (e.g. choose(25,12) 
combinations) look at this approach:

 	http://article.gmane.org/gmane.comp.lang.r.general/62065

>
> Martin Maechler, ETH Zurich
>
>    SpG> 	  I found this just now using 'RSiteSearch("all
>    SpG> subsets of a size")', which produced 102 hits.  Another
>    SpG> one that looked like it might help you is
>    SpG> "http://finzi.psych.upenn.edu/R/Rhelp02a/archive/1717.html".
>
>    SpG> 	  Hope this helps, Spencer Graves
>
>    SpG> Kjetil Brinchmann Halvorsen wrote:
>    >> Hola!
>    >>
>    >> I am programming a class (S3) "symarray" for storing the
>    >> results of functions symmetric in its k
>    >> arguments. Intended use is for association indices for
>    >> more than two variables, for instance coresistivity
>    >> against antibiotics.
>    >>
>    >> There is one programming problem I haven't solved, making
>    >> an inverse of the index function indx() --- se code
>    >> below. It could for instance return the original k
>    >> indexes in strictly increasing order, to make indx()
>    >> formally invertible.
>    >>
>    >> Any ideas?
>    >>
>    >> Kjetil
>    >>
>    >>
>    >> Code:
>    >>
>    >>
>    >> # Implementing an S3 class for symarrays with array rank
>    >> r for dimension # [k, k, ..., k] with k>=r repeated r
>    >> times. We do not store the diagonal.
>    >>
>    >> # Storage requirement is given by {r, k}= choose(k, r) #
>    >> where r=array rank, k=maximum index
>    >>
>    >> symarray <- function(data=NA, dims=c(1,1)){ r <- dims[1]
>    >> k <- dims[2] if(r > k) stop("symarray needs dimension
>    >> larger than array rank") len <- choose(k, r) out <-
>    >> data[1:len] attr(out, "dims") <- dims class(out) <-
>    >> "symarray" out }
>    >>
>    >> # Index calculation:
>    >>
>    >> indx <- function(inds, k){ r <- length(inds) if(r==1)
>    >> return(inds) else { if(inds[1]==1) { return(
>    >> indx(inds[-1]-1, k-1 ) ) } else { return(
>    >> indx(c(inds[1]-1, seq(from=k-r+2, by=1, to=k)), k) +
>    >> indx( inds[-1]-inds[1], k-inds[1] )) } } } # end indx
>    >>
>    >> # Methods for assignment and indexing:
>    >>
>    >> "[.symarray" <- function(x, inds, drop=FALSE){ dims <-
>    >> attr(x, "dims") k <- dims[2] inds <- indx(inds, k) res <-
>    >> NextMethod("[", x) res }
>    >>
>    >> "[<-.symarray" <- function(x, inds, value){ dims <-
>    >> attr(x, "dims") k <- dims[2] inds <- indx(inds, k) res <-
>    >> NextMethod("[<-", x) res }
>    >>
>    >> ______________________________________________
>    >> R-help at stat.math.ethz.ch mailing list
>    >> https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do
>    >> read the posting guide!
>    >> http://www.R-project.org/posting-guide.html
>
>    SpG> ______________________________________________
>    SpG> R-help at stat.math.ethz.ch mailing list
>    SpG> https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do
>    SpG> read the posting guide!
>    SpG> http://www.R-project.org/posting-guide.html
>
>
>
>
>    [ Part 3.15: "Included Message" ]
>

Charles C. Berry                        (858) 534-2098
                                          Dept of Family/Preventive Medicine
E mailto:cberry at tajo.ucsd.edu	         UC San Diego
http://biostat.ucsd.edu/~cberry/         La Jolla, San Diego 92093-0717