[R] A category reduction problem

[Thomas Lumley]

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