A category reduction problem

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