![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
Aがn個，Bがm個存在するとき，それで構成されうる文字列を全て出力せよ．
例えばAが2個，Bが2個で構成される文字列は
AABB ABAB ABBA BAAB BABA BBAA
の6通り．これらを出力するプログラムを考えろ．
普通に考えれば再帰的に出力するのが妥当だと思う．
#geshi(c++,number){{
#include <iostream>
#include <vector>
using namespace std;
ostream& operator << (ostream& outputStream, vector<char> output){
vector<char>::iterator it;
it = output.begin();
while(it != output.end()){
outputStream << *it;
it++;
}
outputStream << endl;
return outputStream;
}
void recursivePermutation(vector<char> output, unsigned int nAlength, unsigned int nBlength){
if(!(nAlength + nBlength)){
// 残った文字数がゼロならば
// 現状をdumpして返る
cout << output;
}else{
if(nAlength > 0){
// Aを当てはめてみる
output.push_back('A');
// 再帰呼び出し
recursivePermutation(output, (--nAlength)++, nBlength);
output.pop_back();
}
if(nBlength > 0){
// Bを当てはめてみる
output.push_back('B');
// 再帰呼び出し
recursivePermutation(output, nAlength, (--nBlength)++);
output.pop_back();
}
}
}
int main(int argc, char **argv){
unsigned int nALength, nBLength;
// コマンドラインの引数をnAlength，nBlengthに代入する
if(argc <= 2){
//cerr << "Use as " << argv[0] << " A B " << endl;
//return -1;
// 引数ゼロの場合，デバッグ用にそれぞれ4を代入する
nALength = 4;
nBLength = 4;
}else{
nALength = (unsigned int)atoi(argv[1]);
nBLength = (unsigned int)atoi(argv[2]);
}
vector<char> output;
// 再帰関数呼び出し recursivePermutation(output, nALength, nBLength);
return 0;
} }}
$ ./a.out 2 2 AABB ABAB ABBA BAAB BABA BBAA
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
using namespace std;
ostream& operator << (ostream& outputStream, vector<char> output){
vector<char>::iterator it;
it = output.begin();
while(it != output.end()){
outputStream << *it;
it++;
}
outputStream << endl;
return outputStream;
}
void recursivePermutation(vector<char> output, vector<unsigned int> lengths, int nTypeNumber){
if(!accumulate(lengths.begin(),lengths.end(), 0)){
// 残った文字数がゼロならば
// 現状をdumpして返る
cout << output;
}else{
for(int i = 0;i < nTypeNumber;i++){
if(lengths[i] > 0){
// アルファベット順に当てはめ
output.push_back('A' + i);
lengths[i]--;
// 再帰呼び出し
recursivePermutation(output, lengths, nTypeNumber);
lengths[i]++;
output.pop_back();
}
}
}
}
int main(int argc, char **argv){
vector <unsigned int> lengths;
int nTypeNumber;
if(argc <= 2){
// 引数ゼロの場合，デフォルトオプションとして4と
// 文字種類＝2種類を設定
lengths.push_back(4);
lengths.push_back(4);
nTypeNumber = 2;
}else{
for(int i = 0;i < argc-1;i++){
lengths.push_back(atoi(argv[i+1]));
}
nTypeNumber = argc - 1;
}
vector<char> output;
// 再帰関数呼び出し recursivePermutation(output, lengths, nTypeNumber);
return 0;
} }}
$ ./a.out 2 2 2 AABBCC AABCBC AABCCB AACBBC AACBCB AACCBB ABABCC ABACBC ABACCB ABBACC ABBCAC ABBCCA ABCABC ABCACB ABCBAC ABCBCA ABCCAB ABCCBA ACABBC ACABCB ACACBB ACBABC ACBACB ACBBAC ACBBCA ACBCAB ACBCBA ACCABB ACCBAB ACCBBA BAABCC BAACBC BAACCB BABACC BABCAC BABCCA BACABC BACACB BACBAC BACBCA BACCAB BACCBA BBAACC BBACAC BBACCA BBCAAC BBCACA BBCCAA BCAABC BCAACB BCABAC BCABCA BCACAB BCACBA BCBAAC BCBACA BCBCAA BCCAAB BCCABA BCCBAA CAABBC CAABCB CAACBB CABABC CABACB CABBAC CABBCA CABCAB CABCBA CACABB CACBAB CACBBA CBAABC CBAACB CBABAC CBABCA CBACAB CBACBA CBBAAC CBBACA CBBCAA CBCAAB CBCABA CBCBAA CCAABB CCABAB CCABBA CCBAAB CCBABA CCBBAA
2種類の文字で順列数え上げの場合，できた文字列は2進数でユニークな数として表せる
| 文字列 | 2進数 | 10進数 |
| AABB | 0011 | 3 |
| BABA | 1010 | 10 |
ということは，文字列の長さＬの配列を作り，２のＬ乗までカウントアップして行けば全部余すことなく調べられる
