正数分割の個数

質問

最近、組み分けの問題を考える機会があって、
アルゴリズム辞典を見てみると、「正数分割の個数」（同じ問題と言える）を求めるプログラム（元はPascal）があったのですが、正直言ってなぜこれで求めることができるのか理解できませんでした。
どうしてこのプログラムで、件数を求めることができるのか教えてください。
プログラムは、以下のようなもの（Ｃ言語で書き直したもの）
/*
ある正数ｎを分割する（正数の和で表す表し方の）数を求める
例
4:4,1+3,2+2,1+1+2,1+1+1の５通り
partition(4,4)→5
*/
int partition(int n, int k){
　int p,i;
　if(n<0) return 0;
　if(n<2 || k==1) return 1;
　for(p=0,i=1;i<=k;i++){
　　p+=partition(n-i,i);
　}
　return p;
}

回答No.8

graphaffine · ベストアンサー

失礼しました。
#3で紹介した式を証明します。

・p(n,k)=q(n,1)+q(n,2)+・・・+q(n,k)
pの定義から左辺は項数がｋ以下のnの分割、従って、
項数が1の分割の個数+・・・+項数がkの分割の個数
であり、これはqの定義から右辺に等しい。

・q(n,k)=p(n-k,k)　
αを項数kのnの分割とする。各項から、1を引くと
項数がk以下のn-kの分割βが得られる。（αが1の項を含めば、βの項数はαより少なくなることに注意）
逆に、項数がk以下のn-kの分割βに対し各項に1を加える
（但し、βの項数がkに満たなければ、足りない分だけ1の項を追加する）と、項数kのnの分割が得られる。
従って、項数kのnの分割と項数がk以下のn-kの分割とは
一対一に対応する。

お礼

回答ありがとうございます。お手数をおかけして申し訳ありません。
＞各項から、１を引くと
というところ、ああっ！（AHA!)って思いました。
こういう発想ってでてこないんですよね。歳をとってすっかり頭が固くなっていると思います。

＃５の系統の回答では、ｋは、構成する最大の数とみなすのに対して、
こちらの回答では、項数になるというのが（結局結果は一致する？）というのが面白いですね。
当初、このプログラムを眺めた時、ｎとｋは、何を表している？？
と考えたとき、両方の考えがごっちゃになっているところがありました。それが、１つの混乱の元だったような気がします。
回答としては、数学的な回答は抽象的でちょっとわかりにくいですけれども、ｋがよりすっきりと説明されていると思います。

回答No.7

bender

すでに簡潔な回答や、詳しい説明が寄せられていたことに気づいたのですが、もう一度説明に挑戦してみたので、すでに寄せられた回答と同じようにも思うのですが、いずれにしても投稿してみます。

はじめに、うまくいかない方法を書いて、それを通して質問欄にある賢いアルゴリズムについて書きたいと思います。

5を分割するということは、5個の要素 OOOOO をいくつかのグループにわけることなので、そこで、要素を一列に並べて左端から何個かづつ順にとりわけて、5個全部分割し終わったものを数え上げるような場合を考えます。

例、
[O]OOOO（左から一個とりわける）
[O][O]OOO　（左からさらにもう一個とりわける）
…
[O][O][O][O][O]　分割方法1 (1+1+1+1+1)
--------------------------------------
[O]OOOO
[O][O]OOO
…
[O][O][O][OO]　分割方法2 (1+1+1+2)
--------------------------------------
…
…（分割方法3 ～ j-1）
…
--------------------------------------
[OO]OOO
[OO][O]OO
…
[OO][O][O][O]　分割方法 j (2+1+1+1)
etc.

以上で、分割方法2と分割方法 j は同じ分け方とみなされるので、このようにすべての分割方法を求めて結果を数え上げていくのでは、分割方法を全種類導出できるものの、数え上げに重複があってうまくありません。
そこで、質問欄にある賢い関数では、（左から）要素とりわける際に、次に取り分けるグループを、直前にとりわけたグループと同じ大きさか、あるいはだんだん小さくなるようなものだけを考えています。なぜならば、そうすることで、ひとつの分割の仕方につき、ひとつだけ表現が対応するからです。例えば、{1,1,1,2} については、分割方法 jの [OO][O][O][O]のみが対応して、分割方法2は導出されません。

そこで、このようなアルゴリズムを実現する再帰関数の引数としては、分割する要素の個数 n 、さらに、次にグループを取り分ける際に最大何個の要素のグループをつくってよいか（つまり、直前にとりわけたグループの大きさ）k を指定することが必要です。
具体的に5の分割を求めるときには、はじめに、partition(5,5) （5個の要素を、最大のグループが5以下からなるものに分割して、それらの分割方法を数え上げたものを返す関数）を呼び出します。
このとき、（左端からの）要素のとりわけの一回目の方法としては、明らかに以下の５通りで、また、明らかにこの５通りしかありません。
[O]OOOO (n-i=4, i=1)
[OO]OOO (n-i=3, i=2)
[OOO]OO (n-i=2, i=3)
[OOOO]O (n-i=1, i=4)
[OOOOO] (n-i=0, i=5)
それぞれの場合、さらなる分割をするために関数を再帰的に呼びだすのですが、ここで重要なのは、先に書いた分割方法に従う限り、以上の５通りのいずれからも重複する分割結果が導出されない、かつ、すべての分割方法が導出されることです。例えば、

[O]OOOO　のときには、残りの（右の）４個（n-i=4）をさらに分割する方法で、ただし、その各要素数が最大１個(i=1)であるようなものの個数、を求める関数を呼びます、すなわち、partition(4,1) 。この場合について言えば、残りの4要素を分割する際に作れるグループの数が1個以下と指定されているので、これは([O])[O][O][O][O] とするしかありません。そこで、この場合1を返してよいことが関数に指定されています(k==1)。

[OO]OOO　のときには、残りの（右の）3個をさらに分割する方法を数で、ただし、その各要素数は最大で2個であるようなもの、を求める関数の呼び出します、すなわち、partition(3,2) 。これはさらなる再帰の結果、最終的には、([OO])[OO][O] と([OO])[O][O][O] の２通りに帰結することがわかります。

残りの３つの場合についても、それぞれ、
partition(2,3)（([OOO])[OO]と、([OOO])[O][O]の２通りに帰結）
partition(1,4)（残りの要素が1個なので、分割するまでもなく[OOOO][O]）
partition(0,5)（すでに分割が完了している [OOOOO]）

実際に導出されたように、このように求められた分割には重複がなく、かつ、数え漏らしがありません（これ以外に取り分ける方法がないので）。そこで、この5通りから帰結した分割の個数の和 7 = 1 + 2 + 2 + 1 + 1 が、5 を分割する方法の個数であるとわかります。

お礼

ありがとうございます。
＃５で言われたことを非常に丁寧に説明されていて、
物わかりの悪い私にもよくわかりました。

回答No.6

kacchann

「数え上げ」の仕方のポイントに絞って
書いてみます。
再帰については触れません。
---

5個のボールを分ける分け方を
実際に(樹形図みたいなのを)紙に書いたりして
「数え上げて」みてください。

※「樹形図みたいなの」というのは、
こんなようなやつ↓
●●●●－●

●●●－●●
　　　－●－●

●●－●●●
　　－●●－●
　　－●－●●
　　　　－●－●

（※ちょっと絵がズレてごめんなさい）
---

でも、どうやって数え上げます？ 書き出します？
5個じゃなくて、100個だったら？
普通に樹形図を書いても、「同じモノ」を数えてしまいそうで
怖いですよね(※上の樹形図は、すでに重複を含んでいる)。
「同じモノ」を数えない(※二重カウントしない)方法を
考え出さなくてはなりませんが…。どうします？
---

ポイント1:場合分け。
　ここでは「最大値」に目をつけて場合分け。
ポイント2:切り出し順序(ルール)。
　ここでは「ボールを、"一番大きなグループ"から切り出していく」。

これらのポイント、「数え上げ」の際の常套手段かも。
---

[ポイント1]場合分け
●|●|●●|●
や
●|●●|●|●
という「分け方」は、共に「最大値2」の世界に属します。
このように、どんな分け方も、必ず、「属する世界」が1つに定まりますし、
2つの世界に同時に属することもありません。
したがって、
最大値1の世界、2の世界、…、5の世界は、
互いに「排他的」(※「排反」って言うんだっけ？)なので、
このそれぞれの世界(=それぞれの「場合」)について「数え上げ」、
最後にそれらを合計すれば
それが求める答。

(また、このように
「最大値に着目」とか「最小値に着目」とかいう「着目の仕方」のは、
「互いに排反な「場合」に『場合わけ』」するときの常套手段だったような…。)
---

[ポイント2]切り出し順序
上で挙げた
●|●|●●|●
と
●|●●|●|●
は、"同じ分け方"です。
同じ分け方をしないように「数え上げ」なくてはなりませんが、
そのためには、この両者の記法を、どちらも
●●|●|●|●
というように「一意に定めて」しまえばいいわけです。
(※大きさ順に"ソート"している)

この「大きさ順に"ソート"された記法」、
言いかえれば、
「(ボールを)"一番大きなグループ"から切り出していけ」
ということです。
(※たとえば「●●と●と●と●」という「分け方」は
左から●●－●－●－●の順に切り出すのであって、
●－●●－●－●の順とか
●－●－●－●●の順とかに切り出してはならない、
というルール)

このようなルールを適用して切り出していけば、
結果、「数え上げの重複」が発生しませんし(※しませんよね？
　しないように切り出したんですから)、
同時にもちろん、このようなルールを適用したところで、
「数え上げ『もれ』」も、生じそうにありません(※生じないですよね？)。
※このへん、"樹形図"を書いて確認するとナットクするかも。

要するにこのように考えれば、
「二重カウント」も「数え上げもれ」も生じないということです。

お礼

回答ありがとうございます。
なんか、思いもよらず、色々な回答がついて嬉しいです。
前に、自分で考えたプログラムは、小さいほうから順に考えていました。
＃５の方の回答にあるように、大きい方から決めるということに気がつけば良かったのかもしれません。
考えてみれば、再帰を繰り返す度に問題を小さくするのは、再帰の常套手段なワケで、
逆に、小さい方からの、自分の考えたプログラムは実はおかしいんじゃないかとか思えてきました・・

補足

＞でも、どうやって数え上げます？ 書き出します？
＞5個じゃなくて、100個だったら？
ちなみに、私の考えた方法は、
http://okwave.jp/kotaeru.php3?q=1999665
の＃５です。
自分では合っていると思うんですが・

回答No.5

UKY

例えば n = 4 の場合、全ての分割の組み合わせは

4
3+1
2+2
2+1+1
1+1+1+1

の 5 通りですね。
右側の数が左側の数より大きくなることがないようになっているのがポイントです。例えば 2+1+1 は (2 >= 1 && 1 >= 1) なので OK ですが 1+2+1 は (1 >= 2 && 2 >= 1) ではないのでだめです。

数え上げは「一番左側の数」と「二つ目以降の数」で分けて行います。「二つ目以降」は再帰処理です。n = 4 なら、
4 + ???
3 + ???
2 + ???
1 + ???
において、四つの ??? をそれぞれ再帰処理します。
例えば、「1 + ???」について考えます。この場合、 ??? が満たすべき条件は、
1. ??? の部分の合計が 3
2. ??? に含まれる数字はどれも 1 以下
であり、この二つの条件はそれぞれ関数の引数に対応しています。(つまりこのとき、再帰で呼ばれる関数の引数は 3 と 1 になります)

お礼

回答ありがとうございました。
なるほど！
わかったような気がします。

締め切るのはもうちょっと待とうと思います。

回答No.4

graphaffine

訂正です。

誤　q(n-k,k)=p(n,k)　
正　q(n,k)=p(n-k,k)

回答No.3

graphaffine

数学のカテゴリーのほうが良かったですね。

自然数n,kに対し
p(n,k):nのk個以下の自然数への分割の仕方の数
q(n,k):nの丁度k個の自然数への分割の仕方の数
で、関数p,qを定めると次の関係が成り立ちます。（成り立つ理由は直ぐわかると思います）

p(n,k)=q(n,1)+q(n,2)+・・・+q(n,k)
q(n-k,k)=p(n,k)

お礼

回答ありがとうございました。
数学カテゴリにしようかとも思ったんですが、元がプログラムなモンで
プログラムその他にしました。
重複して、数学カテゴリにも質問しようかとも思いましたが、重複投稿になるので・
数学の良く判る人にとっては自明なのかもしれませんね。
自分でももう少し考えてみます。

補足

＞成り立つ理由は直ぐわかると思います
ごめんなさい、
この関係が成り立つというのは、プログラムから（推測できるので）わかっています。
成り立つ理由が知りたいので質問しているわけで・・
物わかりの悪い頭でごめんなさい。

回答No.2

bender

partition(n,k) の読み替えとしては、おおよそ、「正の数 n を分割してできる分割の個数、ただし各部分の数は k 以下とする」だと思います。

直感的なアルゴリズムの理解としてはおおよそ、分割の個数を数え上げる際に、数え上げる種類に重複が無いように、与えられた数を、部分の数が徐々に小さくなる（か同じになる）ように分割して、それらを数えあげる、ということかと思います。
例、8を{1,2,5}に分割する場合、5+2+1の並びだけを数えることで、1+5+2、2+5+1、他、との数え上げの重複を避ける。

プログラムの終了条件で、(A) n==0 のときはそれ以上分割できないので 個数1を返すのですが、(B) n==1 のときも、次回の再帰呼び出しの結果がすでに決まっているので、同様に1を返して終了するのだと思います。
また、(C) k==1 の場合については、「各部分の数が1以下」である場合なので、そのような分割の仕方は、1+1+1+…+1しかないので、再帰呼び出しをするまでもなく個数1を返してよいことがわかります。

例、partition(5,5)=7 の場合：
partition(5,5)
　partition(4,1) … 1+1+1+1+1 (C)
　partition(3,2) … 2+
　　partition(2,1) … 2+1+1+1 (C)
　　partition(1,2) … 2+2+1 (B)
　partition(2,3) … 3+
　　partition(1,1) … 3+1+1 (B)/(C)
　　partition(0,2) … 3+2 (A)
　　partition(-1,3)
　partition(1,4) … 4+1 (B)
　partition(0,5) … 5 (A)

お礼

回答ありがとうございました。
おっしゃることは、だいたい判るのですが、
もう一つ、よく納得ができません。
物わかりの悪い頭ですみません。

回答No.1

chie65536

最初に
partition(4,4)
で呼ぶと
for(p=0,i=1;i<=k;i++){
の行でpが0に初期化された後
iが1から4(k)まで繰り返され
partition(3,1)　…（１）
partition(2,2)　…（２）
partition(1,3)　…（３）
partition(0,4)　…（４）
が順に呼ばれ、この４つの答えがpに順に足され、pに答えが作られます。

（１）
partition(3,1)
の答えは
　if(n<2 || k==1) return 1;
により、1です。

（２）
partition(2,2)
で呼ぶと
for(p=0,i=1;i<=k;i++){
の行でp(このpは最初のpとは別のp)が0に初期化された後
iが1から2(k)まで繰り返され
partition(1,1)
partition(0,2)
が順に呼ばれ、この２つの答えがpに順に足され、p(このpは最初のpとは別のp)に答えが作られます。

partition(1,1)
partition(0,2)
の２つは
　if(n<2 || k==1) return 1;
により、1です。

ここでp(このpは最初のpとは別のp)は1+1になるので
　return p;
により2が返されます。

つまり
partition(2,2)
の答えは2です。

（３）（４）
partition(1,3)
partition(0,4)
の答えは
　if(n<2 || k==1) return 1;
により、どちらも1です。

つまり最初の４回の繰り返しでは
partition(3,1) = 1
partition(2,2) = 2
partition(1,3) = 1
partition(0,4) = 1
で、pには1+2+1+1が、つまり5が作られます。

そして、最終的な答え5(p)が返されます。

このような「自分自身を呼ぶ」のを「再帰呼び出し」と言います。

「再帰呼び出し」の最も単純な例として、1からnまでの総和を求める関数を例示しておきます。どういう動きをするか参考にして下さい。

int souwa(int n)
{
　if (n < 1) return 0;
　if (n == 1) return 1;
　return (n + souwa(n - 1);
}

お礼

丁寧な回答ありがとうございました。
質問の仕方が悪くて余計なお手間を取らせて申し訳ありませんでした。

自分でも考えてみたのですが、
partition(3,1) = 1
partition(2,2) = 2
partition(1,3) = 1
partition(0,4) = 1
が、
partition(n-i,i) として、 nをi分割する件数を表すというのは判ります。
よくわからないのは、
nをi分割する件数が
partition(n,i)
とかでなくて、（もちろん呼び出す側は、そういうふうに呼出できますが）
partition(n-i,i)
という形に帰着（？）するのかということです。
partition(n-i,i)こういう形で見てるとそれらしい感じですが、
partition(1,3)が４を３分割する件数を表す関数だと言われても、えっえ～って感じです。
判る人には、当たり前のことなのかもしれませんが、
私は、頭が固いのかもしれません、さっぱりわかりません。

補足

すみません、もちろん、動作としてはわかっております。
わからないのは、アルゴリズムとして、なぜこれで求まるのかということです。