Edited at

C#で数学パズル - ステインハウスの三角形(ビットパターンで0と1の組合せを求める)


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

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

1.この三角形は以下のように0と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である三角形をすべて作成してみて、1と0の数が同じになる三角形の数を数えるという、方法を採用することにします。

なお、速度を上げるために、明らかに条件を満たさないとあらかじめわかるものは、それがわかった時点で除外します。

0と1の合計がn個となるすべてのパターンを求める方法の一つとして、0から2n-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の組合せを別の方法で求めようとすると、もっとたくさんのコードを書かなくてはなりません。これはちょっとした発想の転換ですね。

ビットパターンを生成(2進数表記に変換)したら、これを逆三角形の上辺とし、排他的論理和を行い、三角形を作ります。

この三角形の、0と1の数が等しければ、ステインハウスの三角形と判断できます。これで答えが求まることになります。

求まったステインハウスの三角形は、bool[][]で表します。

bool[][]の配列に0と1からなる三角形のパタンが格納されています。

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

なお、0と1の和が偶数でないと、条件3を満たさないので、辺の長さを 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