連続する数字で作る回文数

連続する数字で作る回文数

締め切りが 2016/12/13 10:00 AM なので，その 1 分後に投稿されるように予約

設問

与えられた整数に対して、最上位の桁から最下位の桁に向けて一桁ずつ読んでいき、同じ数字が続いている場合、「その数字」と「連続する個数」を並べるという変換を考えます。
例えば、「332111」の場合、3が2個、2が1個、1が3個連続するため、「322113」を出力します。

a 以上 b 未満の整数に対し、この変換を行って「回文数」になるものを探します。
回文数とは逆から数字を並べても同じ数になる数です。(Wikipedia：回文数)
例えば、a = 100, b = 1000 のとき、112, 211, 333はそれぞれ1221, 2112, 33となり、条件を満たします。
他にはありませんのでこの範囲には3個存在します。

標準入力から整数 n が与えられたとき、10^(n-1) 以上 10^n 未満の整数の中から、上記の変換により回文数になるものがいくつあるかを求め、
標準出力に出力してください。
なお、n は 0 < n ≦ 9 を満たすものとします。

【入出力サンプル】
標準入力
3

標準出力
3

========================================

どのレベルのプログラムを書くかというのが，落としどころ。

ブルートフォースならば，以下のように，しらみつぶしすればよいが，当然ながら，計算時間はバカにならない。。

f = function(n) {
    g = function(x) {
        y = c(t(matrix(unlist(rle(as.numeric(unlist(strsplit(as.character(x), ""))))), ncol=2)))
        all(y == rev(y))
    }
    h = function(x) {
        y = rle(strsplit(as.character(x), "")[[1]])
        v = y$values
        l = y$lengths
        n = seq_along(l)
        y = c(rbind(v, l))
        all(y[n] == rev(y)[n])
    }
    cat(sum(sapply((10^(n-1)):(10^n-1), h)))
}

この問題は，整数を複数の整数に分解することに関係しているということがわかる。
たとえば，整数 5 は  (5), (1,1,1,1,1), (4, 1), (3,1,1), (3,2), (2,2,1), (2,1,1,1) の 5 通りに分割できる。
それぞれは，(3,1,1) はその他に(1,3,1), (1,1,1) など，何通りかの配置がある。それぞれに対応して，どの数字（0-9）が繰り返されるかが決まる。そして，(数字，繰り返し）の列が，左右対称であるものを求めよというのが，題意である。

そこで，以下のようなプログラミングになる。

permutations = function(n) { # 順列組み合わせの行列を生成
    z = matrix(1)
    if (n > 1) {
        for (i in 2:n) {
            x = cbind(z, i)
            a = c(1:i, 1:(i - 1))
            z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
            z[1:nrow(x), ] = x
            for (j in 2:i - 1) {
                z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
            }
        }
    }
    z
}

partition = function(n) { # 整数 n を，いくつかの整数の和で表す方法を求める
        part.int.sub = function(n, k, a) {
        if (n == 0) {
            writeLines(paste(a, collapse=" "), f)
        } else if (n == 1) {
            writeLines(paste(c(a, 1), collapse =" "), f)
        } else if (k == 1) {
            writeLines(paste(c(a, rep(1, n)), collapse =" "), f)
        } else {
            if (n >= k) {
                part.int.sub(n - k, k, c(a, k))
            }
            part.int.sub(n, k - 1, a)
        }
    }
    f = textConnection("ans", "w")
    part.int.sub(n, n, NULL)
    close(f)
    ans # 各行に，解を格納する
}

g = function(p) { # 解の候補を精査する。合格なら 1，不合格なら 0 を返す
    num = NULL
    rev.p = rev(p)
    for (i in seq_along(p)) {
        num = c(num, rep(p[i], rev.p[i]))
    }
    ans = rle(num)
    ans = c(rbind(ans$values, ans$length))
    if (all(ans == rev(ans))) {
#            cat("num = ", paste(num, collapse=""), "\n") # 詳細表示が必要ならコメントアウト
#            cat("rle = ", ans, "\n")                     # 詳細表示が必要ならコメントアウト
        return(1)
    } else {
        return(0)
    }
}

f = function(n) { # 主関数
    perm = lapply(1:n, permutations) # 解の組み合わせを求める基礎
    part = partition(n) # 分割法法を得る
    m = length(part)
    count = 0
    for (i in seq.int(m)) { # それぞれの分割法法の組み合わせを検討
        p = as.integer(strsplit(part[i], " ")[[1]])
        k = length(p)
        if (n != 1 && k == n) { # すべての数字を 1 回ずつ繰り返すのは解になり得ない
            next
        }
        p = as.matrix(unique(as.data.frame(t(apply(perm[[k]], 1, function(x) p[x]))))) # チェックすべきパターンの生成
        for (i in 1:nrow(p)) {
            count = count+g(unname(p[i,])) # 左右対称の条件を満たせばカウントアップ
        }
    }
    cat(count)
}

f(1) # 1
f(2) # 1
f(3) # 3
f(4) # 4
f(5) # 7
f(6) # 14
f(7) # 23
f(8) # 39
f(9) # 71

なお，この数列は既知のものであり，個数だけを求めるならば，もっと簡単になる。