n個の異なった要素の中から m個を選ぶ順列

重複を許す順列と、重複を許さない順列を求められるようにしています。


Permutationクラスはジェネリックにしていますので、整数以外の要素にも対応しています。

簡単にPermutationクラスのでGetElementsメソッドで何をやっているかを説明します。
たとえば、(1,2,3,4)の4つの要素から3つの要素を取り出す(重複を許さない)順列を考えます。
求める順列は、1が先頭に来るもの、2が先頭に来るもの、3が先頭に来るもの、4が先頭に来るものの4種類があります。
(1,x,y)
(2,x,y)
(3,x,y)
(4,x,y)
という4種類です。
具体的には、

foreach (var atom in items) {

}
というループ処理で、atomが先頭に来る要素の処理をしています。
(1,x,y)の場合は、1を除いた(2,3,4)から、2つを取り出す順列が、x,yに当たるわけですから、
atom + 「(2,3,4)から2つを取り出す順列」
を求めればよいことになります。ここで再帰処理が使われます。

var elements = GetElements(templist, m - 1, withRedandant);

が「(2,3,4)から2つを求める順列」にあたる部分です。GetElementsは当然のことながら、複数の結果を返しますので、

foreach (var elem in elements) {
    var newelem = (new T[] { atom }).Concat(elem).ToArray();
    yield return newelem;
}

で、先頭の要素を加える処理をしています。具体的には、

(2,3)
(2,4)
(3,2)
(3,4)
(4,2)
(4,3)

が求まるので、それぞれに 1を加えたものが (1,x,y) となり、yield return で結果を返しています。

再帰処理をすることで、mの数が1ずつ減ってゆくわけですが、m が 1になった時は、「nから1つを取り出す処理」となりますから、ここだけは特別扱いをしています。それが、

if (m == 1) {
    foreach (var n in items) {
        yield return new T[] { n };
    }
    yield break;
}

の箇所です。

なお、重複ありの場合は、「(2,3,4)から2つを求める順列」の部分が、「(1,2,3,4)から2つを求める順列」となるだけですので、
 templist.Remove(atom);
をやらなければ、重複を許す順列を求めることができます。
 


■MainPage.xaml.cs

■MainPage.xaml