蟻本「分割数」考察 その2
概要
「蟻本「分割数」考察」では
「n個の互いに区別できない品物を、m個以下に分割する方法の総数」
でなくて
「n個の互いに区別できない品物を、m個に分割する方法の総数」
に意識が行って時間を費やしてしまった。「n個の互いに区別できない品物を、m個に分割する方法の総数」を動的計画法でもとめてみたのでメモしておく。
漸化式
「n個の互いに区別できない品物を、m個に分割する方法の総数」をdp(n,m)とする。
「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を含まないものの総数をdpA(n,m)、「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を一つでも含むものの総数をdpB(n,m)とする。
例えば、n=10,m=3で考えるとdpA(10,3)は
{2,2,6},{2,3,5},{2,4,4},{3,3,4}
があるのでdpA(10,3)=4となる。dpB(10,3)は
{1,1,8},{1,2,7},{1,3,6},{1,4,5}
があるのでdpB(10,3)=4となる。
ところで「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を含まないものの総数はは、「n-m個の互いに区別できない品物を、m個に分割する方法」の総数と同じである。一方「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を一つでも含むものの総数は「n-1個の互いに区別できない品物を、m-1個に分割する方法」の総通と等しい。
上の例で言うと
dpA(10,3)はdp(7,3)=4に等しく
{1,1,5},{1,2,4},{1,3,3},{2,2,3}
と対応する。
dpB(10,3)はp(9,2)=4に等しく
{1,8},{2,7},{3,6},{4,5}
と対応する。
したがってdp(n,m)には漸化式dp(n,m)=dp(n-m,m)+dp(n-1,m-1)が成り立つ（n>2,m>2,n-m=>m）。
実装1 「n個の互いに区別できない品物を、m個以下に分割する方法」
蟻本を参照して実装
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4
5 const int MAX_N=100;
6 const int MAX_M=100;
7
8 int n,m;
9 ll dp[MAX_M + 1][MAX_N + 1];
10
11 int main(){
12 cin >> n >> m;
13 cout << "n:" << n << " m:" << m << endl ;
14 dp[0][0] = 1;
15 for ( int i = 1; i<= m ; i++){
16 for(int j = 0; j<= n; j++){
17 if( j - i >= 0){
18 dp[i][j] = dp[i-1][j] + dp[i][j-i];
19 } else {
20 dp[i][j] = dp[i-1][j];
21 }
22 }
23 cout << "i:" << i << " j:" << n << " " << dp[i][n] << endl ;
24 }
25 }
実装2 「n個の互いに区別できない品物を、m個に分割する方法」
自分で作成した漸化式で実装
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 typedef long long ll;
5
6 const int MAX_N=100;
7 const int MAX_M=100;
8
9 int n,m;
10
11 ll dp[MAX_M + 1][MAX_N + 1];
12
13 int main(){
14 int ans=0;
15 cin >> n >> m;
16 cout << "n:" << n << " m:" << m << endl ;
17
18 for (int j = 1; j <= n; j++){
19 dp[1][j]=1;
20 }
21
22 for ( int i = 2; i<= m ; i++){
23 for(int j = 1; j<= n; j++){
24 if( j < i ){
25 dp[i][j] = 0;
26 } else if ( j- i >= 1){
27 dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
28 } else {
29 dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
30 }
31 // cout << "i:" << i << " j:" << j << " " << dp[i][j] << endl ;
32 }
33 }
34 for(int i=1;i<=m;i++){
35 ans += dp[i][n];
36 cout << "i: " << i << " j: " << n << " " << dp[i][n] << " " << ans << endl ;
37 }
38 }
実行例
蟻本と自作漸化式で結果が一致するのを確認
myoden@ubuntu002:~/AntBook/P066$ cat input.2
6 6
myoden@ubuntu002:~/AntBook/P066$ ./book < input.2
n:6 m:6
i:1 j:6 1
i:2 j:6 4
i:3 j:6 7
i:4 j:6 9
i:5 j:6 10
i:6 j:6 11
myoden@ubuntu002:~/AntBook/P066$ ./myoden < input.2
n:6 m:6
i: 1 j: 6 1 1
i: 2 j: 6 3 4
i: 3 j: 6 3 7
i: 4 j: 6 2 9
i: 5 j: 6 1 10
i: 6 j: 6 1 11
myoden@ubuntu002:~/AntBook/P066$
確認のため組み合わせを書き出してみた。
N=6
| M | 分割数Mの組み合わせ数 | 分割数M以下の組み合わせ数 | 組み合わせ |
|---|---|---|---|
| 1 | 1 | 1 | ｛6｝ |
| 2 | 3 | 4 | ｛1,5｝｛2,4｝｛3,3｝ |
| 3 | 3 | 7 | ｛1,1,4｝｛1,2,3｝｛2,2,2｝ |
| 4 | 2 | 9 | ｛1,1,1,3｝ ｛1,1,2,2｝ |
| 5 | 1 | 10 | ｛1,1,1,1,2｝ |
| 6 | 1 | 11 | ｛1,1,1,1,1,1｝ |