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