【解決時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等は出力しない)
(コメント欄に続く)

回答の条件
  • 1人10回まで
  • 登録:2007/01/03 11:54:09
  • 終了:2007/01/10 11:55:02

回答(2件)

id:indiannotlies No.1

indiannotlies回答回数3ベストアンサー獲得回数12007/01/05 18:02:51

ポイント60pt

[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]以降及びコメントへの対応については、ちょっと時間的に厳しいため、この辺で。

id:kokudou

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を指定して見てみたいと考えています。

2007/01/05 23:55:32

質問者が未読の回答一覧

 回答者回答受取ベストアンサー回答時間
1 koutaro_yuzuki 580 388 1 2007-01-03 21:30:50
  • id:kokudou
    [1]の続き
    ・value,max,numberで入力可能な値は1つまたは複数の正整数。
    ・複数の場合はコンマかハイフンで区切る。"3-5"は"3,4,5"と同義。
    ・maxとnumberは入力を省略することもできる。省略した場合はvalueで入力した値に対して取りうる全ての数を入力したとみなす。
    ・出力はvalueが小さいものから並べ、同じvalue値では分割中の最大の数が大きい順(最大の数が同じ場合は2番目に大きい数が大きい順、以下同様に考える)に並べる。
    ・入力、出力はできる限り以下の形式に沿うようにしてください。

    (例1.1)
    -入力- value:7\ max:3-5\ number:3\\
    -出力- 5,1,1\4,2,1\3,3,1\3,2,2\\
    (\ 1個が改行1個に対応、以下同じ)

    (例1.2)
    -入力- value:5-7\ max:\ number:1,2\\
    -出力- 5\4,1\3,2\\6\5,1\4,2\3,3\\7\6,1\5,2\4,3\\

    (例1.3)
    -入力- value:5,6\ max:3,5\ number:\\
    -出力- 5\3,2\3,1,1\\5,1\3,3\3,2,1\3,1,1,1\\


    [2]の続き
    (例2.1)
    -入力- value:5-7\ max:3-6\ number:\\
    -出力- \\3,2,1\\3,2,1,1\\

    (例2.2)
    -入力- value:10,11\ max:3,4\ number:\\
    -出力- 4,3,2,1\3,2,2,1,1,1\3,2,1,1,1,1,1\\4,3,2,1,1\3,2,2,1,1,1,1\3,2,1,1,1,1,1,1\\
  • id:tamtam3
    前回、b-windさんが解いてもらった問題をちょっと弄れば
    すぐ答えがでると思いますけど

    弄る部分は、とりたててプログラムとは関係ない 数式部分なんですが?
    b-windなら、1分ぐらいで解いてくれそうなので遠慮しておきます
    (あれだけ苦労されたb-windさんが150ポイントで、ちょろっと直して500ポイントゲットじゃ、さすがにb-windさんが泣くと思われます)
  • id:kokudou
    tamtam3さん

    確かにそうかもしれません。

    ただ、こちらのプログラムの方がよくよく考えると私にとってより役に立つのでポイントを上げることにしました。

    b-windさんにはこちらの要望に答えて頂いたことを感謝しております。
  • id:hamster009
    http://q.hatena.ne.jp/1167565750

    これ、ひどいなあ。
    こういうのに答えたらあかんな。これでええんやと思いけつかる。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません