ｎ個の要素で出来る順列組み合わせを全て出力するアルゴリズム

質問

次のようなプログラムをC++で書こうと思っているのですが、
どうも方法が思い浮かびません。
よいやり方、定番のやり方などがありましたら教えてください。

---------------------------------
ｎ個の要素があるとき、
そのｎ個で出来る順列組み合わせ（計（ｎ！）通り）を全て出力する。

例えばa[4] = {'A', 'B', 'C', 'D'}なら
順列組み合わせは
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A
・
・
・
D C A B
D C B A
の、計24通り

回答No.2

ballville · ベストアンサー

「順列組合せ」ではなく「順列の生成」ですね。

アルゴリズムの原理を知りたければ次のWlframのサイトでわかりやすく説明しています。下のほうのところで、再帰を使ったものが例示されています。
http://mathworld.wolfram.com/Permutation.html

ソースを見たいなら、
http://www.merriampark.com/perm.htm
あたりで。

ただし、C++では、順列生成は標準ライブラリに入っています。
next_permutation,prev_permutation
を使って下さい。
http://www005.upp.so-net.ne.jp/episteme/html/stlprog/_05.html

回答No.1

floor101

おはようございます。

#include <algorithm>
をした上で、

std::next_permutation(a, a + 4);
がfalseを返すまで繰り返し呼び出せば良いでしょう。

配列が降順にソートされていれば、代わりに
std::prev_permutation(a, a + 4);
を使います。