No.02048 Re: 正の整数の和 【スカーレット】 2006/12/28(Thu) 13:10
こんにちは
プログラミングによる手法でも良いでしょうか？
巧い算法とは言えず，総当りに近いことを，多少手数を減らす手法なら思いつきました。
第1段階
N=5を求める際に，N=4の結果を用います。
N=4の時の集合5種それぞれに，要素1を加えた
{4,1},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1}は，『N=5の全てのうち，1を最低一つ含むもの』の全てになります。
あとは，『N=5の全てのうち，1を一つも含まないもの』を探していくことになります。
第2段階
N=4の全て＝{4},{3,1},{2,2},{2,1,1},{1,1,1,1}に出てくる数(1〜4)に1を加えた要素を求める
{4+1},
{3+1,1 },
{3 ,1+1},
{2+1,2 },
{2 ,2+1},
{2+1,1 ,1 },
{2 ,1+1,1 },
{2 ,1 ,1+1},
{1+1,1 ,1 ,1 },
{1 ,1+1,1 ,1 },
{1 ,1 ,1+1,1 },
{1 ,1 ,1 ,1+1}
で，ここから，『1を一つでも含むもの』と，『重複しているもの』を消していくとALLになります。
機械的にいける方法なので，プログラミングは出来ると思いますが，手でやるのと大差ない計算量になってしまうのが難点です。すみません。
No.02049 Re: 正の整数の和 【通りすがり】 2006/12/28(Thu) 17:14
これと似たようなことを北大の久保拓弥さんが「ぎょーむ日誌」のなかで書いておられました。
http://hosho.ees.hokudai.ac.jp/~kubo/log/2004/0101.html#05
perlのコードも公開しておられます。
http://hosho.ees.hokudai.ac.jp/~kubo/log/2004/img01/enum_partitions.pl
ご参考になればと思います。
No.02050 Re: 正の整数の和 【OTZ】 2006/12/28(Thu) 17:51
スカーレットさん，通りすがりさん，コメントありがとうございます．私のほうでも，mathworldの下記ページに，参考になりそうなものを見つけました．取り急ぎお礼まで．
http://mathworld.wolfram.com/PartitionFunctionP.html
No.02064 Re: 正の整数の和 【青木繁伸】 2006/12/30(Sat) 10:46
ちょっと遠くへ行っていたので，帰りの新幹線で考想数10分。(^_^;)
以下に示すのはとっても効率が悪いので，使い物にならない。prog <- function(x)
{
len <- length(x)
if (len > 2) {
comb2 <- combn(len, 2) # R2.5.0 が必要
nc <- ncol(comb2)
i <- 1
for (i in 1:nc) {
y <- x
y[comb2[1, i]] <- sum(y[comb2[, i]])
y <- y[-comb2[2, i]]
cat(sort(y), "\n")
prog(y)
}
}
}
partition <- function(n)
{
x <- rep(1, n)
unique(sort(capture.output(prog(x))))
}
#
n <- 6 # 7 以上だと死ぬほど時間が掛かる
partition(n)
> partition(3)
[1] "1 2 " # 2つの自明の解は出力しない
> partition(4)
[1] "1 1 2 " "1 3 " "2 2 "
> partition(5)
[1] "1 1 1 2 " "1 1 3 " "1 2 2 " "1 4 " "2 3 "
> partition(6)
[1] "1 1 1 1 2 " "1 1 1 3 " "1 1 2 2 " "1 1 4 " "1 2 3 "
[6] "1 5 " "2 2 2 " "2 4 " "3 3 "
No.02085 Re: 正の整数の和 【青木繁伸】 2006/12/30(Sat) 17:26
ずっと前に作っていたプログラムを転用すれば，もう少し無駄のない速いアルゴリズムになることに気づいた。> gft <- function(n)これでも，n=9 だと死ぬほどの時間を経験できる。。。
+ {
+ gen_tab <- function(y)
+ {
+ if (y == 1) {
+ r <- o[o>0]
+ cat(sort(r), "\n")
+ }
+ else {
+ gen_tab(y-1)
+ while (o[1]) {
+ o[y] <<- o[y]+1
+ o[1] <<- o[1]-1
+ gen_tab(y-1)
+ }
+ o[1] <<- o[1]+o[y]
+ o[y] <<- 0
+ }
+ }
+ o <- numeric(n)
+ o[1] <- n
+ print(unique(sort(capture.output(gen_tab(n)))), quote=FALSE)
+ }
> gft(8)
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 2 2
[5] 1 1 1 1 4 1 1 1 2 3 1 1 1 5 1 1 2 2 2
[9] 1 1 2 4 1 1 3 3 1 1 6 1 2 2 3
[13] 1 2 5 1 3 4 1 7 2 2 2 2
[17] 2 2 4 2 3 3 2 6 3 5
[21] 4 4 8
n=9では，まだ死ねなかった（PowerBookG4)> system.time(gft(9))
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
[3] 1 1 1 1 1 1 3 1 1 1 1 1 2 2
[5] 1 1 1 1 1 4 1 1 1 1 2 3
[7] 1 1 1 1 5 1 1 1 2 2 2
[9] 1 1 1 2 4 1 1 1 3 3
[11] 1 1 1 6 1 1 2 2 3
[13] 1 1 2 5 1 1 3 4
[15] 1 1 7 1 2 2 2 2
[17] 1 2 2 4 1 2 3 3
[19] 1 2 6 1 3 5
[21] 1 4 4 1 8
[23] 2 2 2 3 2 2 5
[25] 2 3 4 2 7
[27] 3 3 3 3 6
[29] 4 5 9
user system elapsed
65.343 9.784 82.766
No.02086 Re: 正の整数の和 【青木繁伸】 2006/12/30(Sat) 20:32
ヴ〜ン。
perl は，わからない。。。
魔法の呪文にしか見えない。
No.02090 Re: 正の整数の和 【OTZ】 2006/12/31(Sun) 06:52
青木先生，サンプルコードを示していただき，ありがとうございます．
combn関数はchoose関数とは，異なるのですね．R2.5.0がインストールされていないので，動作確認できていませんが．
gft 関数の中で使われている演算子「<<-」は，どういう意味でしょうか．代入を意味する「<-」とは異なるものと承知していますが， help.searchで調べても，「<<-」の説明が見つかりませんでした．五月雨式の質問で申し訳ございません．
No.02092 Re: 正の整数の和 【青木繁伸】 2006/12/31(Sun) 08:42
? "<<-" はやってみましたか?
大域変数への代入を意味します。以下の例で，a, b の値に注意> sub2 <- function()
+ {
+ a <<- 10
+ b <- 20
+ }
> a <- 1
> b <- 2
> cat("a=", a, " b=", b, "\n", sep="")
a=1 b=2
> sub2()
> cat("a=", a, " b=", b, "\n", sep="")
a=10 b=2
No.02102 Re: 正の整数の和 【OTZ】 2006/12/31(Sun) 17:39
青木先生，早速のご教示，ありがとうございます．
「<<-」は試しましたが，大域変数には気が付きませんでした．すっきりしました．重ねて感謝申し上げます．
No.02111 Re: 正の整数の和 【青木繁伸】 2007/01/01(Mon) 09:49
年が明けて，寝ながら考想数時間。朝起きて，書いてみたら，あっさり動いた。
自画自賛ながら，これは，速い。所要時間は，結果を書くためのものがほとんどすべて。partition <- function(n)
{
ans <- n # 初期状態（長さ1のベクトル。これは解でもある）
repeat { # このプログラムは再帰プログラムではない
cat(ans, sep="+") # ここに来るときには ans は解ベクトル
cat("\n") # 改行
if (ans[1] == 1) { # 解のベクトル要素は常に ans[i] >= ans[i+1]
break # になるように作るので，ans[1] == 1 なら，最後の解
}
ans <- ans[ans > 1] # 新たな解を求める準備。ans[*] == 1 の要素を取り除く
no <- length(ans) # 要素数
ans[no] <- ans[no]-1 # 最後の要素から 1 を引く
residuals <- n-sum(ans) # 合計が n になるために必要な残り
height <- ans[no] # residuals を配分するときに今の要素の一番右の要素より大きくてはいけない
for (i in height:1) { # 配分する要素を決定していく
ans2 <- residuals%/%i # 取りうる最も大きい要素の値が何個とれるか
if (ans2) { # 値 i の要素を ans2 個，追加できる
ans <- c(ans, rep(i, ans2)) # 要素を追加
residuals <- residuals-i*ans2 # 残りの数を更新
if (residuals == 0) { # 残りが0（要素の合計数がちょうど n）なら追加は終了
break
}
}
}
}
}
実行例
> system.time(partition(15))
15
14+1
13+2
13+1+1
:
2+1+1+1+1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
user system elapsed
0.040 0.002 0.291
画面に出していると表示時間ばかりなので，ファイルに出すと，
> sink("dummy")
> system.time(partition(50))
> sink()
で，
user system elapsed
55.649 23.996 89.378
が得られますが，4226行，5.6MBもの大量出力になるので，これくらいでやめておく方が無難。
No.02112 Re: 正の整数の和 【OTZ】 2007/01/01(Mon) 12:47
青木先生，ありがとうございます．
今回質問させていただいた理由は，n個（n=200〜250）の個体を その属性に基づいてkクラス（k=1,2,...,n）に分類するとき，果たして何通り（f(n)）の分類が可能で，各クラスのメンバは具体的にどういう 構成になるのかを，知りたかったからです．nの増加とともに，f(n)が爆発的に増えるため，効率的な算法を求めていました．教えていただいたスクリプト で解決しそうです．ありがとうございました．
No.02115 Re: 正の整数の和 【ひの】 2007/01/02(Tue) 02:23
>n個（n=200〜250）の個体をその属性に基づいてkクラス（k=1,2,...,n）に分類するとき，果たして何通り（f(n)）の分類が可能で，
これが目的だとすると，「正の整数の和」という形に定式化するのは不適切ではないでしょうか？たとえば，[a,b,c]を分類するとき[a,b][c]と するか[a][b,c]とするかを区別して数える必要があるのではないでしょうか。こういう数（ことごとく相異なるn個の対象を空でない組に分ける分け方 の総数）のことはBell数という名がついており，定式化されていますので簡単に計算できます（式は検索すればすぐ見つかるでしょう）。ただしシグマ記号 を含む式ですからプログラミングは簡単ですが手計算は大変です。なお，その組み合わせを列挙するのはまた別のお話。
No.02121 Re: 正の整数の和 【OTZ】 2007/01/02(Tue) 16:04
ひの様，
ご指摘ありがとうございます．ごもっともです．
要素数nの集合を，k個の部分集合に分割するとき，各部分集合の要素数さえわかれば，何通りの分割方法がありえるのか計算できると考えていました．が，間違っていたようです．
正整数の分割に関してさんざん助けていただきながら，それを活かすことが出来ず，申し訳ない気持ちでいっぱいです．．．良い勉強になりました．
No.02122 Re: 正の整数の和 【青木繁伸】 2007/01/02(Tue) 19:02
最初は，統計学と何の関係があるんだろうと思いましたが，そういうことだったのかと納得はしたものの，結局は「n =200〜250」にもなると，当初の目的を満たす解であろうと，ひのさんの指摘したBell数であろうと，いずれにしても，解を得てもそれを全部見るこ とさえできないわけで。
n=200〜250 の解を得るにはどれくらいの時間が必要かという予測式を作るのもよろしいかも。
No.02125 Re: 正の整数の和 【ひの】 2007/01/03(Wed) 22:31
>n=200〜250 の解を得るにはどれくらいの時間が必要かという予測式を作るのもよろしいかも。
皮算用ってやつですね。Bell数はn=200だと数百桁にはなりますから，全部列挙しようとすると地球上の資源を全部ハードディスクにつぎ込んでも容量が足りないんじゃないかと思います(^^;)。紙にプリントするには地球上の木材を全部伐採しても…。
● 「統計学関連なんでもあり」の過去ログ--- 039 の目次へジャンプ
● 「統計学関連なんでもあり」の目次へジャンプ
● 直前のページへ戻る