C++で順列を生成する

C++で順列の一覧を作成する方法を考えた。（本当に正しいかどうかの保証はない）

junretu.cpp

#include <iostream>
#include <vector>
using namespace std;

int N, cnt = 0;

int func(vector<char>list, int len, int index) { //列を格納するvector、列の長さ、インデックス番号
// インデックス番号の文字をインデックス番号から右側の文字だけを交換してゆく

// indexが末尾から2番目になったら末尾の二つだけを交換してそれぞれを表示する 
	if (index >= len - 2){
		for (int i = 0; i < len; i++) cout << list[i]; // 交換する前の列を表示する
		cout << endl;

		swap(list[len - 1], list[len - 2]); //末尾の二つを交換する

		for (int i = 0; i < len; i++) cout << list[i]; // 交換した後の列を表示する
		cout << endl;

		cnt += 2; // cntで組み合わせ数をカウントする
		return 0;
	}

	vector<char>list2 = list;
	func(list, len, index + 1);  // index番号の文字がindex番目（つまり移動していな状態）にある列を
//次の再帰関数に渡す

	for (int i = index + 1; i < len; i++) {
		swap(list[index], list[i]); // index番目とi番目を交換する
		func(list, len, index + 1); // 交換処理した列を次の再帰関数に渡す。index値は＋１しておく
		list = list2;
	}

	return 0;
}

signed main() {
	vector<char>list;

	cout << "順列の長さを入力してください(2以上26以下)：";
	cin >> N;
	cout << endl;

	for (int i = 0; i < N; i++) list.push_back(i + 'A');

	func(list, list.size(), 0);
	cout << "組み合わせ数は" << cnt << "です" << endl;

	return 0;
}

実行結果

順列の長さを入力してください：4

ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC
組み合わせ数は24です

シンプルなモノが出来ないか考えたが数行で済むようなものは思いつかない。多少プログラム文が長くても
ロジックがシンプルで理解しやすければ、それはシンプルなプログラムだと思う。

例としてABCの順列を生成する場合を考えてみる。ABCの順列は
ABC
ACB
BAC
BCA
CBA
CAB
の6通りだ。
これを次のように整理して考える。
ABC ←元の文字列の左から1番目が左から1番目にあり、残り二つを入れ替えている
ACB ←元の文字列の左から1番目が左から1番目にあり、残り二つを入れ替えている

BAC ←元の文字列の左から2番目が左から1番目にあり、残り二つを入れ替えている
BCA ←元の文字列の左から2番目が左から1番目にあり、残り二つを入れ替えている

CBA ←元の文字列の左から3番目が左から1番目にあり、残り二つを入れ替えている
CAB ←元の文字列の左から3番目が左から1番目にあり、残り二つを入れ替えている

これをプログラム文で実装するのは特に難しくなくC++ならswap(変数1,変数2)を利用して元の配列の0番目と
0 + i 番目を交換して、i を1ずつ加算してゆくだけだ。

次にABCDの順列を考えてみる。
ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
　.
　.
続く

ABCDの右側の三つBCDだけを考えると先ほどのABCと同じ考え方で6通りの順序があると考えられる。つまり
BCD
BDC
CBD
CDB
DCB
DBC
の六つである。つまりABCDの右側三つの順列を生成する処理は先ほどの簡単に実装できるプログラムに任せて、
自分は一番左にあるAを他の文字と交換する事だけを考えれば良いわけだ。そしてその交換処理を行うプログラムも
簡単に実装できる。つまり0番目のAと1番目のBを交換して次に、元の配列の0番目のAと2番目のCを交換するという
具合だ。

for (int i = index + 1; i < len; i++) {
		swap(list[index], list[i]);   // index番目とi 番目を交換する
		func(list, len, index + 1);   // 後の処理は次の関数に渡して任せる
		list = list2;    // 変更を加えた配列を元の配列に戻す
}

この考え方は順列の長さが5個でも10個でも同じである。indexが末尾から2番目を指す状態になった時、末尾の二つ
を交換してそれぞれの列を表示させて、他はindexが指す文字を残りの文字列と順に交換してゆく。次の再帰関数に
渡すときにindexの値を１だけ増やしていけば最初の再帰関数では左から0番目と残りの全てを交換処理し、次の関数では
indexが+1 されてるから左から1番目と残りの全てを交換処理するといった具合に繰り返してゆくだけである。