エンジェル隊組み合わせ
今日もドラマCDを聞きながら考えた。
「エンジェル隊の組み合わせは何通りあるのだろうか？」
４期になってからは全員で出ることが多かったけど、昔は２〜３人での絡みが多かったはず。ということで、エンジェル隊のそれぞれが絡んだらどういうシチュエーションになるか想像してみることにした。が、一体どのくらいのパターンがあるのだろうか？というプログラムを書くことにした。まあ５人くらいなら樹形図書けばいいんだけどね・・・
アルゴリズムは超簡単。
1 ┬ 2 ┬ 3 │ ├ 4 │ └ 5 ├ 3 ┬ 4 │ └ 5 └ 4 ─ 5 2 ┬ 3 ┬ 4 │ └ 5 └ 4 ─ 5 3 ─ 4 ─ 5
こんな樹形図を書くのと全く同じアルゴリズム。
// combi.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// enumeration (recursive)
void enum_combi_rec(vector<int> &this_combi,
vector< vector < int > > &all_combi,
const int n, const int depth, const int k, const int N)
{
this_combi[depth] = n;
if(depth == k-1){
all_combi.push_back(this_combi);
return;
}
else{
for(int i=n+1; i<N; i++){
enum_combi_rec(this_combi, all_combi, i, depth+1, k, N);
}
}
}
// enumeration
void enum_combi(vector< vector < int > > &all_combi, const int k, const int N)
{
vector<int> c(k);
for(int i=0; i<N; i++){
enum_combi_rec(c, all_combi, i, 0, k, N);
}
}
// main
int main(const int argc, const char ** const argv)
{
const int N = argc-1;
vector<string> elem;
for(int i=1; i<argc; i++){
elem.push_back(argv[i]);
}
for(int i=1; i<=N; i++){
vector< vector < int > > all;
enum_combi(all, i, N);
cout << "-------- " << N << "_C_" << i
<< " (" << all.size() << " combinations) --------" << endl;
for(int j=0; (unsigned)j<all.size(); j++){
for(int k=0; (unsigned)k<all[j].size(); k++){
cout << all[j][k] << " ";
}
cout << endl;
}
}
return 0;
}% ./combi ミルフィー ランファ ミント フォルテ ヴァニラ -------- 5_C_1 (5 combinations) -------- ミルフィー ランファ ミント フォルテ ヴァニラ -------- 5_C_2 (10 combinations) -------- ミルフィー ランファ ミルフィー ミント ミルフィー フォルテ ミルフィー ヴァニラ ランファ ミント ランファ フォルテ ランファ ヴァニラ ミント フォルテ ミント ヴァニラ フォルテ ヴァニラ -------- 5_C_3 (10 combinations) -------- ミルフィー ランファ ミント ミルフィー ランファ フォルテ ミルフィー ランファ ヴァニラ ミルフィー ミント フォルテ ミルフィー ミント ヴァニラ ミルフィー フォルテ ヴァニラ ランファ ミント フォルテ ランファ ミント ヴァニラ ランファ フォルテ ヴァニラ ミント フォルテ ヴァニラ -------- 5_C_4 (5 combinations) -------- ミルフィー ランファ ミント フォルテ ミルフィー ランファ ミント ヴァニラ ミルフィー ランファ フォルテ ヴァニラ ミルフィー ミント フォルテ ヴァニラ ランファ ミント フォルテ ヴァニラ -------- 5_C_5 (1 combinations) -------- ミルフィー ランファ ミント フォルテ ヴァニラ
合計31通りの組み合わせかあ・・・なんか一日一ネタやれって言ってるようだなあ・・・。
