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

以下の３つの条件を満たしたものをステインハウスの三角形と言います。

1．この三角形は以下のように０と１から成っている。
2. m行目はm-1行目の隣同士の数字の排他的論理和となっている。
3. 三角形内の 0 の数と1の数が同じである。

下の三角形は、1,2は満たしていますが、3を満たしていないため、ステインハウスの三角形ではありません。


  0 0 1 0 1 0 1 
   0 1 1 1 1 1 
    1 0 0 0 0 
     1 0 0 0 
      1 0 0 
       1 0 
        1

問題

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

どうやって解くか

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

0と1の合計がn個となるすべてのパターンを求める方法の一つとして、0から2ⁿ-1までの整数をビットパターンに変換する方法があります。
この方法だと、nの上限に制限ができてしまいますが、簡単に0と1の組み合わせパターンを見つけることができまうす。

つまり、

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

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

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

というコードにしています。

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

ビットパターンを生成（２進数表記に変換）したら、これを逆三角形の上辺とし、排他的論理和を行い、三角形を作ります。
この三角形の、0と1の数が等しければ、ステインハウスの三角形と判断できます。これで答えが求まることになります。

求まったステインハウスの三角形は、bool[][]で表します。
bool[][]の配列に0と1からなる三角形のパタンが格納されています。

掲載したコードのSteinhausTriangleクラスのTriangles()メソッドの戻り値をIEnumerable<bool[][]>としているのはそのためです。

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

n * (n + 1) / 2

が偶数のときだけ、計算すればよいことになります。この計算式は、三角形の面積（1と0の総数）を示しています。

また、鏡像を2重にカウントしないようにするために工夫していますが、それは実際にコードを見てください。

C#のコード

using System;
using System.Linq;
using System.Collections.Generic;

namespace SteinhausTriangleApp {
    public class SteinhausTriangle {
        private int _width;

        public SteinhausTriangle(int n) {
            this._width = n;
        }

        public IEnumerable<bool[][]> Triangles() {
            int maxcount = (int)Math.Pow(2, _width);
            foreach (var baseline in Enumerable.Range(0, maxcount)) {
                if (IsSteinhausTriangle(baseline, _width))
                    yield return MakeTriangle(baseline, _width);
            }
        }

        // 三角形を作る
        private bool[][] MakeTriangle(int baseline, int width) {
            // int型のまま処理するのは、面倒なので、bool[]に変換して処理をする。
            bool[] line = ToArray(baseline, width);
            var triangle = new List<bool[]>();
            while (line.Length >= 1) {
                triangle.Add(line);
                line = NextLine(line);
            }
            return triangle.ToArray();
        }

        // ステインハウスの三角形かどうかを調べる
        private bool IsSteinhausTriangle(int baseline, int width) {
            // int型のまま処理するのは、面倒なので、bool[]に変換して処理をする。
            bool[] line = ToArray(baseline, width);
            if (!NeedCount(line))   // 鏡像を考慮する。
                return false;
            int tcount = 0;   // 1の数
            int fcount = 0;   // 0の数
            while (line.Length >= 1) {
                tcount += line.Where(b => b == true).Count();
                fcount += line.Where(b => b == false).Count();
                line = NextLine(line);
            }
            return tcount == fcount;
        }


        // 鏡像をカウントしないようにするための判定メソッド
        private bool NeedCount(bool[] line) {
            if (IsRound(line))
                // 左右対称ならば、他に鏡像となるパターンはないので、これは調べる必要がある。
                return true;
            // 左右対称でないならば、鏡像のパターンが他にもうひとつあるので、
            // 片方だけを調べるようにする。
            return ToInt(line.Reverse().ToArray()) > ToInt(line);
        }

        // ビットパターンが左右対称かどうかを調べる
        private bool IsRound(bool[] line) {
            int j = line.Length - 1;
            int i = 0;
            while (i < j) {
                if (line[i++] != line[j--]) {
                    return false;
                }
            }
            return true;
        }

        // bool[]をビットパターンとみなし、intに変換する
        private int ToInt(bool[] line) {
            return line.Aggregate(0, (r, b) => r * 2 + (b ? 1 : 0));
        }

        // 整数nを width個からなるbool配列に変換する
        public bool[] ToArray(int n, int width) {
            var array = new bool[width];
            int mask = 1;
            width.Times(i => {
                array[i] = (n & mask) != 0;
                mask <<= 1;
            });
            return array;
        }

        // 1段下のラインを排他的論理和を使い求める
        private bool[] NextLine(bool[] line) {
            var next = new bool[line.Length - 1];
            int i = 0;
            // ここで、Aggregateを使うのは邪道かな？
            line.Aggregate((a, b) => {
                next[i++] = a ^ b;
                return b;
            });
            return next;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Text;

namespace SteinhausTriangleApp {
    static class EnumerableExtensions {
        // 要素の数だけ、actionを呼び出す
        public static void ForEach<T>(this IEnumerable<T> source, Action<T> action) {
            foreach (var x in source) {
                action(x);
            }
        }

        // n回、actionを呼び出す
        public static void Times(this int count, Action<int> action) {
            for (int i = 0; i < count; i++)
                action(i);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SteinhausTriangleApp {
    class Program {
        static void Main(string[] args) {
            var str = Console.ReadLine();
            if (int.TryParse(str, out var width) == false)
                return;
            var sol = new SteinhausTriangle(width);
            var r = sol.Triangles();
            PrintResult(r);

        }

        private static void PrintResult(IEnumerable<bool[][]> result) {
            var sb = new StringBuilder();
            int n = 0;
            foreach (var tr in result) {
                var s = string.Format("({0})\n", ++n);
                int spacecnt = 2;
                foreach (var line in tr) {
                    s += new string(' ', spacecnt) +
                        line.Aggregate("", (t, c) => t + (c ? "1" : "0") + " ") +
                        "\n";
                    spacecnt++;
                }
                sb.AppendLine(s);
            }
            if (sb.Length == 0)
                Console.WriteLine("ステインハウスの三角形はありません");
            else
                Console.WriteLine(sb.ToString());
        }
    }
}

結果

以下、底辺の長さが7の三角形での結果です。


7
(1)
  0 0 1 0 1 0 0 
   0 1 1 1 1 0 
    1 0 0 0 1 
     1 0 0 1 
      1 0 1 
       1 1 
        0 

(2)
  0 0 1 1 1 1 0 
   0 1 0 0 0 1 
    1 1 0 0 1 
     0 1 0 1 
      1 1 1 
       0 0 
        0 

(3)
  0 1 0 0 0 0 1 
   1 1 0 0 0 1 
    0 1 0 0 1 
     1 1 0 1 
      0 1 1 
       1 0 
        1 

(4)
  0 0 0 1 0 0 1 
   0 0 1 1 0 1 
    0 1 0 1 1 
     1 1 1 0 
      0 0 1 
       0 1 
        1 

(5)
  0 1 0 1 0 1 1 
   1 1 1 1 1 0 
    0 0 0 0 1 
     0 0 0 1 
      0 0 1 
       0 1 
        1 

(6)
  1 1 1 0 1 1 1 
   0 0 1 1 0 0 
    0 1 0 1 0 
     1 1 1 1 
      0 0 0 
       0 0 
        0 

(7)
  1 0 1 1 1 1 1 
   1 1 0 0 0 0 
    0 1 0 0 0 
     1 1 0 0 
      0 1 0 
       1 1 
        0