original page : http://ja.doukaku.org/96/
正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
0 を除いて降順に並べたものを指すことも多いのではないかと思います．
たとえば，
partitions 1 ⇒ 1
partitions 2 ⇒ [[2],[1,1]]
partitions 3 ⇒ [[3],[2,1],[1,1,1]]
partitions 4 ⇒ [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
partitions 5 ⇒ [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
partitions 6 ⇒ [[6],[5,1],[4,2],[3,3],[4,1,1],[3,2,1],[2,2,2],[3,1,1,1]
,[2,2,1,1],[2,1,1,1,1],[1,1,1,1,1,1]]
すなわち，
- 1つの分割は非増加列
- 分割は長さが短いものが先
- 同じ長さの分割では辞書順で大きいものが先
という規則でならべたものです．一つの分割に一つのヤング図形が対応します．
たとえば、5 の分割に対応するヤング図形を列挙すると以下 7 つのようになります．
□□□□□
□□□□
□
□□□
□□
□□□
□
□
□□
□□
□
□□
□
□
□
□
□
□
□
□
お題：
正整数を与えられたとき上の意味での分割に対応するヤング図形をすべて
標準出力に印字する関数 young を定義してください．ヤング図形の出力は
上の例のように文字'□'を並べてください．
young 50 の出力をファイルにリダイレクトしたときの処理時間はどの程度
かかったかもCPUスペックとあわせt教えてください．
#4525
original page : http://ja.doukaku.org/comment/4525/
Pentium4 2.4GHzで656秒ｗ
お題のうち「分割」だけならparts()という関数で、0.66秒なのですが・・・。
stdoutへのcatとループ(apply)が泣きそうなほど遅いです。
> sink("young50.dat")
> Rprof(); young(50); Rprof(NULL)
> summaryRprof()
$by.self
self.time self.pct total.time total.pct
cat 471.62 71.9 533.42 81.3
lapply 41.74 6.4 622.78 94.9
FUN 39.52 6.0 649.92 99.1
stdout 29.98 4.6 29.98 4.6
(中略)
parts 0.20 0.0 0.66 0.1
(中略)
young 0.00 0.0 656.10 100.0
library("partitions") young <- function(n){ invisible(apply(parts(n), 2, function(v)(sapply(v, function(x)(cat(rep("□", x), "\n", sep="")))))) }
