[R] A category reduction problem

[Kathy Gerber]

Many thanks to Bill and Thomas for both insight and this nice solution.

Kathy Gerber

William Dunlap wrote:
> If you diff the desired series you get all 2^n
> possible n-long sequences of 0's and 1's.  Hence
> another solution is to convert the numbers in
> 0:(2^n-1) to their binary representations, putting
> the j'th bit into the j'column and run
> cumsum over the resulting rows.
>
> For efficiency in R do this a column at a time
> (n iterations), not a row at a time (2^n iterations).
> E.g.,
>
> f <- function (n=10)
> {
>     ret <- matrix(0, nrow=2^n, ncol=1+n)
>     x <- 0:(2^n-1)
>     for(j in (n+1):2) {
>        ret[,j] <- x%%2
>        x <- x %/% 2
>     }
>     if (n>=2) for(j in 2:(n+1)) {
>        ret[,j] <- ret[,j-1] + ret[,j]
>     }
>     ret
> }
>
> Bill Dunlap
> TIBCO Software Inc - Spotfire Division
> wdunlap tibco.com 
>
> ------------------------------------------------------------------------
> --------
>
> [R] A category reduction problem
>
> Thomas Lumley tlumley at u.washington.edu 
> Fri Mar 20 18:12:26 CET 2009
> Previous message: [R] A category reduction problem
> Next message: [R] struggling with pairlists
> Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
> I'd do this with recursion, I think
>
> * A valid (n+1) number sequence is a valid n-number sequence followed
> either by the last number of the sequence or the last number plus one.
>
> * A valid 1-number sequence is 0
>
>
>        -thomas
>
>
> On Fri, 20 Mar 2009, Kathy Gerber wrote:
>
>   
>> I am trying to print out a list of strings of length 11 based on
>>     
> integers 0 
>   
>> through 10.  The rules as given to me for the ordering are:
>> The first digit must be 0.
>> The 2nd digit must be 0 or 1.
>> The 3rd digit must equal the 2nd digit or the 2nd digit +1.
>> ...
>> Given the final digit, n, all digits 0 through n must appear in a
>>     
> given 
>   
>> sequence.
>>
>> So the final 1024 item list should look like 0 1 2 3 4 5 6 7 8 9 10
>> 0 1 2 3 4 5 6 7 8 9 9
>> 0 1 2 3 4 5 6 7 8 8 9
>> 0 1 2 3 4 5 6 7 7 8 9
>> ...
>> 0 1 2 3 4 5 6 7 8 8 8
>> 0 1 2 3 4 5 6 7 7 8 8
>> ...
>> 0 1 2 3 3 3 3 3 3 3 3
>> 0 1 2 2 3 3 3 3 3 3 3
>> ...
>> 0 0 0 0 0 0 0 0 0 0 0
>>
>> This is easy to do for a small integer, e.g., to see what's going on I
>>     
> drew the 
>   
>> tree for 5, getting 16 rows including the two trivial rows, 0 0 0 0 0
>>     
> and 0 1 2 
>   
>> 3 4.  Offsetting from 0-10 to 1-11, I have tried two basic approaches
>>     
> with only 
>   
>> partial success:  using nested loops (gets messy quickly), and using
>>     
> the 
>   
>> partitions package to construct rows by generating combinations based
>>     
> on the 
>   
>> partitions.
>>
>> Here's my very flawed code for completeness, but I'm guessing there is
>>     
> a better 
>   
>> approach entirely.  There are actually 56 partitions (here hardcoded
>>     
> 2:19). 
>   
>> require(partitions)
>> b <- as.matrix(parts(11))
>> u <- b[-1,]
>> for (ptn in 2:19) {
>> s <- as.matrix(u[, ptn])
>> dss <- as.vector(s[which(s>0)])
>> if (length(dss) <= b[1, ptn]) {
>> comb <- combn(b[1, ptn], length(dss))
>> ccnt <- dim(comb)[2]
>> for (i in ccnt:1) {
>> a <- c(1:b[1,ptn])
>> for (k in 1:length(dss)) {
>>   a <- c(a,rep(comb[k, i], u[k, ptn]))
>> }
>>  cat(sort(a-1,"\n")
>> }
>> }
>> }
>>
>> I appreciate any insight or direction.
>>
>> "Counting is hard."  -- Alan Lee Schwartz
>> -----------------------------------------------------
>> Kathy Gerber
>> University of Virginia
>> Research Computing Lab
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>>     
> http://www.R-project.org/posting-guide.html
>   
>> and provide commented, minimal, self-contained, reproducible code.
>>
>>     
>
> Thomas Lumley			Assoc. Professor, Biostatistics
> tlumley at u.washington.edu	University of Washington, Seattle
>
>