# [R] A category reduction problem

Kathy Gerber kmg5b at virginia.edu
Fri Mar 20 16:06:41 CET 2009

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

```