# [R] A category reduction problem

Thomas Lumley tlumley at u.washington.edu
Fri Mar 20 18:12:26 CET 2009

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