[パズル]ステインハウスの三角形

■ステインハウスの三角形とは

以下の3つの条件を満たしたものをステインハウスの三角形と言います。
1.この三角形は以下のように0と1から成っている。
2. m行目はm-1行目の隣同士の数字の排他的論理和となっている。
3. 三角形内の 0 の数と1の数が同じである。



■問題
三角形の辺の長さ n を与えられた時、すべてのステインハウスの三角形を描くプログラムを書け。
ただし、左右対象となる鏡像は同一の三角形とみなすこと。

-----



一辺の長さが n である三角形をすべて作成し、1と0の数が同じになる三角形の数を数えるという、方法を採用することにします。
なお、速度を上げるために、明らかに条件を満たさないとあらかじめわかるものは、除外します。

n個からなる0と1からなるすべてのパターンを求める方法の一つとして、0から2^n-1までの整数をビットパターンに変換すれ方法があります。
これだと、nの上限に制限ができてしまいますが、そこまで大きな三角形は必要ないだろいと、勝手に対象外ということにしました。

つまり、

int maxcount = (int)Math.Pow(2, n);
for (int i = 0; i < maxcount; i++) {
    ...
}

というループで、すべてのパターンを処理できることになります。
実際のコードは、LINQを使って

Enumerable.Range(0, maxcount).Aggregate(...);

というコードにしています。
これを別の方法で、0 と 1 の組合せとして求めようとすると、もっとたくさんのコードを書かなくてはなりません。

この整数からビットパターンを生成(2進数表記に変換)して、これを逆三角形の上辺とし、排他的論理和を行い、三角形を作ります。
この三角形の、0と1の数が等しければ、ステインハウスの三角形ということで、カウントアップしていけば、答えが求まることになります。
単にカウントするだけではなく、条件を満たしたステインハウスの三角形を画面上で確認できるようにしています。
SteinhausTriangle クラスのTriangles()メソッドの戻り値をIEnumerable<bool[][]>としているのはそのためです。
bool[][]の配列に0 と 1からなる三角形のパタンが格納されています。 

なお、0と1の和が偶数でないと、条件3を満たさないので、辺の長さを nとすれば、

n * (n + 1) / 2

が偶数のときだけ、計算すればよいことになります。
上記計算式は、三角形の面積(1と0の総数)を示しています。
また、鏡像を2重にカウントしないようにするために工夫していますが、それは実際にコードを見てください。

これをC#で書いたのが以下のコードです。

ToInt()メソッドやNeedCount()メソッド内ではLINQを使っています。LINQのパワーが生かされていると思います。



■SteinhausTriangle.cs
■page.xaml.cs

■page.xaml
  

※『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。