すべての順列を求める

ここでは、与えられた要素をすべてつかった順列を求めています。
たとえば、{ 1, 2, 3 } が与えられた場合は、
{ 1, 2, 3 }
{ 1, 3, 2 }
{ 2, 1, 3 }
{ 2, 3, 1 }
{ 3, 1, 2 }
{ 3, 2, 1 }
の6通りが求められます。

再帰処理を使い、順列を求めています。順列は、見方を変えると、Tree構造と同じ構造になっていますので、基本的にTreeを辿るのと同じ構造でプログラムが書けます。
なお、IEnumerable<T>型を返す(つまり yield return する)ために、若干コードが冗長になっています。

メインとなるのは、Enumerateメソッドの下請けだる _GetPermutationsメソッドです。このメソッドで再帰処理をしています。
第1引数には、現在注目している順列がわたります。再帰するたびに、この順列に、ひとつ要素が加わります。
第2引数には、まだ使われていない数のリストが渡ります。こちらは、再帰呼び出しされるたびに、ひとつずつ要素が減っていきます。
こちらの要素が 0になったら、ひとつの順列が求まったので、yield return で結果を返しています。

なお、この順列を求めるコードを応用することで、様々なパズルを解くプログラムを書くことができます。
当「プログラム小品集」にも、このコードを応用したパズルプログラムを掲載したいと考えています。(2010/1/23)