整数の分割(integer partitions)を列挙するプログラムを書いてみた。ここでは再帰を用いた比較的単純な実装を示すが、より効率的なアルゴリズムを考えるとなると奥が深い。
整数の分割とは、ある整数を自然数の和で表したものだ。例えば分割する整数を5とすると求める自然数は以下のようになる。
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
今回のC++で書いたコードは単純で理解しやすいと思うが、高速化などは考えていない。もしよりよいアルゴリズムに興味があるのならAntoine Zoghbiu and Ivan Stojmenovic. Fast Algorithms for Generating Integer Partitions. Intern. J. Computer Math., 70, 319-332 (1998) (PDF)あたりが参考になるかも。
使い方は以下の通り。
partitions 分割したい整数 [分割した要素の最大値]
分割したい整数が5であれば、
partitions 5
とする。出力は次のようになる。
5 (max 5): 7 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
また、分割したい整数が5で、分割した要素の最大値を3とする場合は、
partitions 5 3
で、以下のような出力を得る。
5 (max 3): 5 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
partitions.cpp
#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; void partitions(int n, int max_n, vector<int>& v, vector<vector<int> >& vv) { if (n == 0) { vv.push_back(v); return; } for (int i = min(n, max_n); i > 0; i--) { v.push_back(i); partitions(n - i, i, v, vv); v.pop_back(); } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " number [max_number_in_partitions]" << endl; exit(1); } int n = atoi(argv[1]); int max_n = argc > 2 ? atoi(argv[2]) : n; vector<vector<int> > vv; partitions(n, max_n, vector<int>(), vv); cout << n << " (max " << max_n << "): " << vv.size() << endl; for (vector<vector<int> >::const_iterator p = vv.begin(); p != vv.end(); ++p) { for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q) cout << " " << *q; cout << endl; } return 0; }
余談だが、ActiveState CodeでPythonのジェネレータを使った以下のようなコードを見つけた。さらに同じ作者がその2年後に書いた記事から、別アルゴリズムのソースコード(tarball)を読むことができる。
def partitions(n): # base case of recursion: zero is the sum of the empty list if n == 0: yield [] return # modify partitions of n-1 to form partitions of n for p in partitions(n-1): yield [1] + p if p and (len(p) < 2 or p[1] > p[0]): yield [p[0] + 1] + p[1:]
整数の分割とは、ある整数を自然数の和で表したものだ。例えば分割する整数を5とすると求める自然数は以下のようになる。
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
今回のC++で書いたコードは単純で理解しやすいと思うが、高速化などは考えていない。もしよりよいアルゴリズムに興味があるのならAntoine Zoghbiu and Ivan Stojmenovic. Fast Algorithms for Generating Integer Partitions. Intern. J. Computer Math., 70, 319-332 (1998) (PDF)あたりが参考になるかも。
使い方は以下の通り。
partitions 分割したい整数 [分割した要素の最大値]
分割したい整数が5であれば、
partitions 5
とする。出力は次のようになる。
5 (max 5): 7 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
また、分割したい整数が5で、分割した要素の最大値を3とする場合は、
partitions 5 3
で、以下のような出力を得る。
5 (max 3): 5 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
partitions.cpp
#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; void partitions(int n, int max_n, vector<int>& v, vector<vector<int> >& vv) { if (n == 0) { vv.push_back(v); return; } for (int i = min(n, max_n); i > 0; i--) { v.push_back(i); partitions(n - i, i, v, vv); v.pop_back(); } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " number [max_number_in_partitions]" << endl; exit(1); } int n = atoi(argv[1]); int max_n = argc > 2 ? atoi(argv[2]) : n; vector<vector<int> > vv; partitions(n, max_n, vector<int>(), vv); cout << n << " (max " << max_n << "): " << vv.size() << endl; for (vector<vector<int> >::const_iterator p = vv.begin(); p != vv.end(); ++p) { for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q) cout << " " << *q; cout << endl; } return 0; }
余談だが、ActiveState CodeでPythonのジェネレータを使った以下のようなコードを見つけた。さらに同じ作者がその2年後に書いた記事から、別アルゴリズムのソースコード(tarball)を読むことができる。
def partitions(n): # base case of recursion: zero is the sum of the empty list if n == 0: yield [] return # modify partitions of n-1 to form partitions of n for p in partitions(n-1): yield [1] + p if p and (len(p) < 2 or p[1] > p[0]): yield [p[0] + 1] + p[1:]
コメント