Aがn個，Bがm個存在するとき，それで構成されうる文字列を全て出力せよ．
#contents
*具体例 [#e7628a8a]
例えばAが2個，Bが2個で構成される文字列は
AABB
ABAB
ABBA
BAAB
BABA
BBAA
の6通り．これらを出力するプログラムを考えろ．
*出力アルゴリズム [#t430026f]
普通に考えれば再帰的に出力するのが妥当だと思う．
#geshi(c++,number){{
#include <iostream>
#include <vector>
using namespace std;
// 出力用オペレータ
// 出力する文字列をvector<char>に代入することにする
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;
}
// 再帰的に順列を出力する関数
// nAlength, nBlengthはそれぞれA，Bの文字数を意味する
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;
}
}}
**実行結果 [#f6ed948f]
$ ./a.out 2 2
AABB
ABAB
ABBA
BAAB
BABA
BBAA
*改良版 [#pc711e14]
-文字列をハードエンコーディングしてるのがちょっと気に食わなかったので，改良．
-メモリアクセスの境界とかあまりチェックしてないが，そこはご愛嬌
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
using namespace std;
// 出力用オペレータ
// 出力する文字列をvector<char>に代入することにする
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;
}
// 再帰的に順列を出力する関数
// 各文字の数はint型のvector，lengthsとその長さnTypeNumberで渡す
// for文で回すよりiteratorで回した方が良いか
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;
}
}}
**実行結果 [#m89d2ad0]
$ ./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
*改悪版？再帰的呼び出しを使わない方法 [#td93f8e7]
2種類の文字で順列数え上げの場合，できた文字列は2進数でユニークな数として表せる
|文字列|2進数|10進数|
|AABB|0011|3|
|BABA|1010|10|
ということは，文字列の長さＬの配列を作り，２のＬ乗までカウントアップして行けば全部余すことなく調べられる
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
