■

昔作った乱数発生クラスに、今は以下のようなメンバ関数が存在する。

//vectorや配列の範囲をあらわすイテレータやポインタを入れてください。
template< typename RanIter > void Shuffle( RanIter pFirst, RanIter pLast ){
	int size = static_cast< int >( pLast - pFirst );
	for( RanIter it = pFirst; it != pLast; it++ ){
		size--;
		swap( *it, *( it + Rand( size, 0 ) ) );
	}
}

ここで、Rand( size, 0 ) という関数は、０〜sizeまでの任意の整数をランダムで返す関数である。
この関数テンプレート、何をやっているかはちょっとたどればわかると思うが、配列やコンテナの中身をシャッフルする関数である*1。引数はポインタとイテレータのどちらでも取れるようにテンプレートを利用している。
で、今、とある事情により、これの逆変換関数が欲しくなった。つまり、一度シャッフルしたコンテナを元に戻す関数である。そんなものが一体何に必要かという大疑問を別にしてもこれ結構面倒な作業だったりする。まず正変換関数(つまりは上のShuffle関数のこと)のアルゴリズムは、前から順番に後ろの適当な奴と交換していくわけだが、これと全く逆の操作をすれば元に戻る。Rand()に関しては同じ種を撒いてやれば同じ乱数が帰ってくるが、今回それを逆に使うので、一旦適当なコンテナに積んでおく必要がある。で、イテレータを逆に回して適切なスワップを施す。口で言うのはさほど難しいことではないが、実装は結構ハードだったりする。そもそもイテレータを逆に回すのは思った以上に大変だったりする。

for( RanIter it = pLast; it != pFirst; it-- ){
	//itを使ってあんなことやこんなことをしちゃう。
}

これ、一見いいように見えますが、全然ダメですよ。まあ、ちょっと考えればわかると思うので説明は省きます。まあ、なんにしてもいろいろと面倒だったりするわけなんですヨ。なまじ出来ても可読性が激烈に落っこちる可能性が高いのですヨ。
で、だ。
ものすごい画期的な解決方法を先日見つけちゃいました(大げさ)。全く逆転の発想だとおもっちゃてます。「イテレータで前から任意の後ろと交換しているからその逆は・・・」とかは全く考えずに実装することが出来るアルゴリズムを見つけちゃいました。つまりはShuffle関数の中身を知る必要がないのですよ。さて、その方法ですが・・・・それはまた後日。よかったら皆さんも考えてみてくださいな。

*1:参考文献：Windowsプロフェッショナルゲームプログラミング2 やねうらお著