Cマガ電脳クラブ(第059回) お散歩仲間

問題

15人の女生徒がいる。彼女たちはお散歩仲間で、毎日3人ずつ5組に分かれて散歩をしている。
1週間(7日間)で、各人がほかのすべての14人と1回ずついっしょに散歩をするようにしたい。
1週間分の組み合わせをどのようにすればよいだろうか。

組み合わせは、1通り求めるだけでかまわない。

ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrP;
        internal int[] HitoHaitiArr;
        internal List<int[]> HitoHaitiArrList;
    }

    const int UB = 14;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        int[] AllHitoArr = Enumerable.Range(1, 15).ToArray();

        WillPush.HitoHaitiArrList = new List<int[]>();
        //最初の組み合わせは1,2,3,4,5,6,7,8,9,10,11,12,13,14,15で固定とする
        WillPush.HitoHaitiArrList.Add(AllHitoArr);

        WillPush.HitoHaitiArr = new int[15];
        WillPush.CurrP = 0;
        Stk.Push(WillPush);

        int PoppedCnt = 0;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (++PoppedCnt % 100000 == 1)
                Console.WriteLine("{0}回目のPop処理を実行中。経過時間={1}", PoppedCnt, sw.Elapsed);

            if (Popped.CurrP > UB) {
                Popped.HitoHaitiArrList = new List<int[]>(Popped.HitoHaitiArrList);

                Popped.HitoHaitiArrList.Add((int[])Popped.HitoHaitiArr.Clone());
                Array.Clear(Popped.HitoHaitiArr, 0, 15);
                Popped.CurrP = 0;
            }

            if (Popped.HitoHaitiArrList.Count == 7) {
                Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
                PrintAnswer(Popped.HitoHaitiArrList);
                return;
            }

            int[] NonUseHitoArr = AllHitoArr.Except(Popped.HitoHaitiArr).ToArray();
            var WillUseHitoList = new List<int>();

            //Push処理
            Action<int, int, int> PushSyori = (pWillUseHito1, pWillUseHito2, pWillUseHito3) =>
            {
                WillPush.CurrP = Popped.CurrP + 3;
                WillPush.HitoHaitiArr = (int[])Popped.HitoHaitiArr.Clone();
                WillPush.HitoHaitiArr[Popped.CurrP] = pWillUseHito1;
                WillPush.HitoHaitiArr[Popped.CurrP + 1] = pWillUseHito2;
                WillPush.HitoHaitiArr[Popped.CurrP + 2] = pWillUseHito3;
                WillPush.HitoHaitiArrList = Popped.HitoHaitiArrList;
                Stk.Push(WillPush);
            };

            int WillUseHito1 = NonUseHitoArr.Min(); //トリオの最初は、未使用の最小番号

            //トリオ内では昇順に配置
            int[] KouhoHitoArr = NonUseHitoArr.Where(X => X > WillUseHito1).ToArray();
            int KouhoHitoMax = KouhoHitoArr.Max();

            foreach (int EachHito2 in KouhoHitoArr) {
                //4は、2日目の1番目のトリオとする
                if (Popped.HitoHaitiArrList.Count == 1 && Popped.CurrP == 0)
                    if (EachHito2 != 4) continue;

                //5は、3日目の1番目のトリオとする
                if (Popped.HitoHaitiArrList.Count == 2 && Popped.CurrP == 0)
                    if (EachHito2 != 5) continue;

                //6は、4日目の1番目のトリオとする
                if (Popped.HitoHaitiArrList.Count == 3 && Popped.CurrP == 0)
                    if (EachHito2 != 6) continue;

                if (EachHito2 <= WillUseHito1) continue; //昇順に配置

                //昇順なので2人目に最大値は配置できない
                if (EachHito2 == KouhoHitoMax) continue;

                //過去に同じトリオでないこと
                if (HasSameTrio(Popped.HitoHaitiArrList, WillUseHito1, EachHito2)) continue;

                foreach (int EachHito3 in KouhoHitoArr.Where(X => X > EachHito2)) {
                    if (HasSameTrio(Popped.HitoHaitiArrList, WillUseHito1, EachHito3)) continue;
                    if (HasSameTrio(Popped.HitoHaitiArrList, EachHito2, EachHito3)) continue;
                    PushSyori(WillUseHito1, EachHito2, EachHito3);
                }
            }
        }
    }

    //過去に同じトリオであったかを返す
    static bool HasSameTrio(List<int[]> pHitoHaitiArrList, int pHito1, int pHito2)
    {
        foreach (int[] AnyHitoHaitiArr in pHitoHaitiArrList) {
            int Ind = Array.IndexOf<int>(AnyHitoHaitiArr, pHito1);
            Ind -= Ind % 3;

            for (int I = Ind; I <= Ind + 2; I++) {
                if (AnyHitoHaitiArr[I] == pHito2) return true;
            }
        }
        return false;
    }

    //解を出力
    static void PrintAnswer(List<int[]> pHitoHaitiArrList)
    {
        int DayCnt = 0;
        foreach (int[] AnyHitoHaitiArr in pHitoHaitiArrList) {
            Console.Write("Day{0} : ", ++DayCnt);
            for (int I = 0; I <= UB; I++) {
                if (I % 3 == 0) Console.Write('[');
                Console.Write("{0,2}", AnyHitoHaitiArr[I]);
                if (I % 3 == 2) Console.Write(']');
                else Console.Write(',');
            }
            Console.WriteLine();
        }
    }
}

実行結果

1回目のPop処理を実行中。経過時間=00:00:00.0076543
100001回目のPop処理を実行中。経過時間=00:00:02.0417907
200001回目のPop処理を実行中。経過時間=00:00:04.0013146
300001回目のPop処理を実行中。経過時間=00:00:05.9640605
解を発見。経過時間=00:00:07.7342137
Day1 : [ 1, 2, 3][ 4, 5, 6][ 7, 8, 9][10,11,12][13,14,15]
Day2 : [ 1, 4,15][ 2,12,14][ 3, 9,13][ 5, 8,11][ 6, 7,10]
Day3 : [ 1, 5,14][ 2, 9,11][ 3, 6,12][ 4, 7,13][ 8,10,15]
Day4 : [ 1, 6, 9][ 2, 8,13][ 3, 5,10][ 4,11,14][ 7,12,15]
Day5 : [ 1,10,13][ 2, 5, 7][ 3,11,15][ 4, 9,12][ 6, 8,14]
Day6 : [ 1, 8,12][ 2, 4,10][ 3, 7,14][ 5, 9,15][ 6,11,13]
Day7 : [ 1, 7,11][ 2, 6,15][ 3, 4, 8][ 5,12,13][ 9,10,14]

解説

組み合わせを、1通り求めるだけの問題なので、
固定可能な条件を列挙して計算量を減らしてます。

1日目は、どう組み合わせても同じことなので1,2,3,4,5,6,7,8,9,10,11,12,13,14,15で固定とし、
各日の最初の人はどれでも同じなので1で固定としてます。

また、4,5,6は
それぞれ1と2日目、3日目、4日目に同じトリオになることで固定してます。

ちなみに本問は、カークマンの女生徒の問題と呼ばれてます。