Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

以下の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 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした