人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【解決時500ポイント】以前http://q.hatena.ne.jp/1167565750でほぼ同じ質問をしましたが、整数の分割(partitions of a number, integer partitions)に関する次のプログラム[1],[2]を作成してください。

言語はCが望ましいですが、XP上で実行できれば特に問いません。出力はEXCELに取り込みます。実行速度も考慮するかもしれません。質問があればコメント欄にお願いします。

[1]任意の正整数の分割を、分割中の最大の数や数の個数に従い出力するプログラム。
1.入力は分割したい正整数の値(value)、分割中の最大の数(max)、分割中の数字の個数(number)の3つ。
2.例えば整数5の分割は、5\4,1\3,2\3,1,1\2,2,1\2,1,1,1\1,1,1,1,1の7個あり、valueに5,maxに3,nubmerに3を入力したら3,1,1が出力される。valueに5,maxに4,nubmerに3を入力したら何も出力されない。
(コメント欄に続く)

[2] [1]の分割のうち、次の(a),(b)2つの条件を満たす分割を出力するプログラム。
(a)1から最大数(例えば3,1の場合3)までの全ての数を含む(つまり5,3,2,1等は出力しない)
(b)1の個数≧2の個数≧・・・≧最大数の個数(つまり3,2,2,1等は出力しない)
(コメント欄に続く)

●質問者: kokudou
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Excel Max Number XP コメント欄
○ 状態 :終了
└ 回答数 : 1/2件

▽最新の回答へ

1 ● indiannotlies
●60ポイント

[1]について、個人的に興味が湧いたのでちょっとプログラムを書いて見ます。

[1]は単純に{整数Nの分割の集合}を求める漸化式ではなく、

{整数Nを上限MのL個の整数に分割した集合}= {整数N-Mを上限MのL-1個の整数に分割した集合} + {整数N-M+1を上限MのL-1個の整数に分割した集合} ... + {整数N-1を上限MのL-1個の整数に分割した集合}

という漸化式で表現できそうですので、こちらで解いてみました。

以下、プログラム(ファイル名div_int.vbs)です。

言語はVBSで、XPならコマンドプロンプト上で

cscript div_int.vbs [value] [max] [number]

とすることで使用可能です。

'------------------------------------
'div_int.vbs
'------------------------------------
gVal=int(wscript.arguments(0))
gMax=int(wscript.arguments(1))
gNumber=int(wscript.arguments(2))

 part_array= split(div_int(gVal - gMax,gMax,gNumber-1),vbNewLine)
 for gi=0 to ubound(part_array) 
 if part_array(gi) <> "" then wscript.echo gMax &amp; "," &amp; part_array(gi)
 next

function div_int(n,m,l)
 array_str=""
 if m*l < n or n < l then
 arrays_str=""
 else
 if l=1 then
 arrays_str = n &amp; vbNewLine
 else 
 for i= m to 1 step -1
 items = split(div_int(n-i,i,l-1),vbNewLine)
 for j=0 to ubound(items) -1
 arrays_str= arrays_str &amp; i &amp; "," &amp; items(j) &amp; vbNewLine
 next
 next
 end if
 end if 
 div_int=arrays_str
end function

'----------------------------------------------

ちなみに組み合わせ数のオーダーについてですが、

?{整数Nの分割の集合} = {整数Nを1個の整数に分割した集合} + ... + {整数NをN個の整数に分割した集合}

?{整数NをL'個の整数に分割した集合} = {整数Nを最大数1のL'個の整数に分割した集合} + ... +{整数Nを最大数NのL'個の整数に分割した集合}

?{整数Nを最大数M'のL'個の整数に分割した集合} = {整数N-Mを上限MのL'-1個の整数に分割した部分集合に、各々要素M'を追加した集合}

という線形の関係があるので、?{整数Nの分割の集合}の組み合わせの数に対して、?{整数Nを最大数M'のL'個の整数に分割した集合}の組み合わせ数は高々N*N分の1にしかならないことが予想されます。最大で(かなり贔屓目に見て)Nの2乗の分のオーダーが減りますが、{整数Nの分割の集合} はおそらく指数関数的な増加なので、Nが大きくなればたちまち組み合わせ爆発を起こす(計算時間も膨大になる)でしょう。

[2]以降及びコメントへの対応については、ちょっと時間的に厳しいため、この辺で。

◎質問者からの返答

indiannotlies さん

新たにプログラムを考えていただきありがとうございます。

{整数Nを上限MのL個の整数に分割した集合}= {整数N-Mを上限MのL-1個の整数に分割した集合} + {整数N-M+1を上限MのL-1個の整数に分割した集合} ... + {整数N-1を上限MのL-1個の整数に分割した集合}

に関してはまだ理解してませんが。。。

ただ、プログラムを(そのままだとエラーが出たので&amp;を&に変え)実行したところ、入力(value,max,number)が複数の場合や、maxやnumberに入力がない場合等には対応していない点は要求を満たしていないので残念です。


ちなみに整数nの分割の集合の数p(n)は近似的に

p(n)\approx\frac{1}{4\sqrt{3}n}exp{\pi\sqrt{\frac{2n}{3}} Hardy-Ramanujan (1918)

となるようなので(参照 http://www.geocities.jp/ikuro_kotaro/koramu/bunkatsu.htm)

ほぼ指数関数的に増加します。


私が関心があるのは[2]の形の分割で、これは

私にとっては興味があるものですが話せば少し長くなるのでとりあえずやめておきます。

とりあえずn=50程度までの[2]の形の分割を見てみたいと考えています。

その周辺の分割を知りたいときに補足で[1]の分割をmax,numberを指定して見てみたいと考えています。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ