Pythonならitertools.permutationsで、
C++ならalgorithmヘッダのnext_permutationで
利用できる置換ですが、標準ライブラリに用意されていない言語や、
何らかの理由で利用できない場合などがもしかしたらあるかもしれません。
そんな時は、再帰しないからスタックサイズを気にする事もなく、
速いらしい、Heap's algorithmの再帰無し版を実装してみてはいかがでしょうか。
ポイントは二点、
- N個の置換はN-1個の置換から帰納的に拡張できる（右に一個要素を追加した場合の組み合わせを考えてみる）
- スワップする要素をA, B(Aが左側)とした時、Bの位置が奇数の場合と偶数の場合でAの位置の決め方が違う
です。要素数が奇数の置換は必ず最初の要素と、偶数の置換は置換するタイミングによって最初の要素、２番目の要素、３番目の要素...と順にずれます。
例として、2要素[A, B]、3要素[A, B, C]、4要素[A, B, C, D]の場合を順に考えます。
まず２要素の場合、置換は２通りしかありません。つまり、[A, B]と[B, A]です。
３要素[A, B, C]の場合は、まず2要素[A, B]の置換をします。つまり、
[A, B, C] # はじめの状態は特別
[B, A, C]
次に、Cを置換します。この時、Cは奇数番目の要素なので、常に最初の要素と置換します。
[C, A, B]
この後はまた左の２要素の置換をします。
[A, C, B]
２要素の置換が終わったので、また最後の要素Bを最初の要素と置換します。
[B, C, A]
また２要素の置換をします。
[C, B, A]
これで終了です。まとめると、
[A, B, C]
[B, A, C]
[C, A, B]
[A, C, B]
[B, C, A]
[C, B, A]
なって、ちゃんと全ての置換が網羅できています。
4要素[A, B, C, D]の場合も、左側３要素の置換後一番右の要素を置換して以下繰り返し、で行っていきます。
まず[A, B, C]の置換を行います。
[A, B, C, D]
[B, A, C, D]
[C, A, B, D]
[A, C, B, D]
[B, C, A, D]
[C, B, A, D]
その後、Dとどれか一つを置換します。この時、置換するのが偶数番目の場合は、最初の置換は最初の要素と、次の置換は２番めの要素というように、１つずつずらしていきます。まずは最初の要素と置換して、また左側３要素の置換をします。
[D, B, A, C]
[B, D, A, C]
[A, D, B, C]
[D, A, B, C]
[B, A, D, C]
[A, B, D, C]
次は、CとB（２番めの要素）を置換します。
[A, C, D, B]
[C, A, D, B]
[D, A, C, B]
[A, D, C, B]
[C, D, A, B]
[D, C, A, B]
次は、BとA(３番めの要素)を置換します。
[D, C, B, A]
[C, D, B, A]
[B, D, C, A]
[D, B, C, A]
[C, B, D, A]
[B, C, D, A]
これで終わりです。任意のN要素はこれを帰納的に行えばOKです。
以下に、Pythonでこれを実装したものを載せておきます。すごいシンプルです。こっちを見たほうがわかりやすいかも。
なお、この実装は再帰をしないバージョンで、特殊な配列qを用いています。
qは現在の置換がどこまで進んでいるかを記憶していくものです。はじめは全て0の状態から始まって、カウントを足したりリセットしたりして、状態を管理しています。どんな仕組みかはコードを目で追ってみるといいでしょう。
def permutation(l):
# 次に入れ替える場所を記憶する為の配列を用意する
q = [0 for _ in l]
l = list(l) # copyしているだけ
yield l # 初期状態
while True:
for n in range(len(l)):
if q[n] < n:
if (n + 1) % 2 == 1:
l[0], l[n] = l[n], l[0]
else:
l[q[n]], l[n] = l[n], l[q[n]]
q[n] += 1
# 参考：qの配列
# print('q:', q)
yield list(l) # yield copy
break
else:
q[n] = 0
else:
return
if __name__ == '__main__':
l = ['A', 'B', 'C', 'D']
for a in permutation(l):
print(a)
Rust1.0のstd::slice::permutationsはまだunstableなので、Rust用のiterator（但しコピーを多用するのであまりイケてない）実装も最後に載せておきます。まあ、素直にunstableにされているコードをコピペしてきたほうがいいと思いますが。
RustでIterator書くのが苦痛すぎる…コルーチン欲しいよお…
struct Permutation<T: Clone> {
v: Vec<T>,
l: Vec<usize>,
not_start: bool,
}
impl<T: Clone> Permutation<T> {
fn new(v: &Vec<T>) -> Permutation<T> {
Permutation{ l: vec![0; v.len()] , v: v.clone(), not_start: true }
}
}
impl<T: Clone> Iterator for Permutation<T> {
type Item = Vec<T>;
fn next(&mut self) -> Option<Vec<T>> {
// non-permutated vector
if self.not_start {
self.not_start = false;
return Some(self.v.clone());
}
for n in 0..self.v.len() {
if self.l[n] < n {
if (n + 1) % 2 == 1 {
self.v.swap(0, n);
self.l[n] += 1;
} else {
self.v.swap(self.l[n], n);
self.l[n] += 1;
}
return Some(self.v.clone());
} else {
self.l[n] = 0
}
}
return None
}
}