2015年03月15日

C#で総当たり戦の日程を作成する

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その77

■問題 (出題者:ryugate さん)
任意の偶数Nのチームの総当たり戦を最短日数(N-1日)で行う場合の日程表を1つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、4チームであれば、
1-2 3-4
1-3 2-4
1-4 2-3

6チームであれば

1-2 3-4 5-6
1-3 2-5 4-6
1-4 2-6 3-5
1-5 2-4 3-6
1-6 2-3 4-5

が解のひとつです。
参考: カークマンの組分け

すべての可能性は求めていません。日程表を一つ作成しています。

以下、はじめに書いたコードです。結構複雑になってしまいました。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            LeaguegameScheduling k = new LeaguegameScheduling();
            var sche = k.DoPlan(8);
            Console.WriteLine(sche);
            Console.ReadLine();
        }
    }

    class LeaguegameScheduling {
        public gameList DoPlan(int teams) {
            var nums = Enumerable.Range(1,teams);
            int days = teams - 1;

            // すべての試合を列挙する
            var q = (from a in nums
                     from b in nums
                     where a != b
                     select Game.Create(a, b))
                    .Distinct();
           
            // 1日の試合数
            int count = q.Count() / days;

            var games = new gameList(days, count);
            games = InnnerPlan(q.ToList(), games, 0, -1);
            return games;
        }

        // DoPlanの下請けメソッド (再帰処理をしている)
        private static gameList InnnerPlan(IEnumerable<Game> rest, gameList games, int day, int nth) {
            if (++nth >= games.NumberInOneDay) {
                day++;
                nth = 0;
            }
            if (rest.Count() == 0) {
                return games;
            }
            foreach (var g in rest) {
                if (games[day].Any(x => x.Contains(g.A) || x.Contains(g.B)))
                    // すでに試合 g のどちらかのチームが、その日、別のチームと試合することに
                    // なっているので、次の g を調べる。
                    continue;
                games[day][nth] = g;
                var result = InnnerPlan(rest.Except(new Game[] { g }), games, day, nth);
                if (result != null)
                    return result;
                games[day][nth] = new Game();
            }
            return null;
        }
    }

    public class gameList  {
        private Game[][] games;

        // 日数
        public int Days {get; set; }

        // 一日の試合数
        public int NumberInOneDay{get; set; }

         // インデクサーの定義
        public Game[] this[int day] {
            get { return games[day]; }
        }

        // コンストラクター
        public gameList(int days, int count) {
            games = new Game[days][];
            for (int i = 0; i < games.Length; i++ )
                games[i] = new Game[count];
            this.Days = days;
            this.NumberInOneDay = count;
        }

        // 文字列化
        public override string ToString() {
            StringBuilder sb = new StringBuilder();
            foreach (var oneday in games) {
                sb.AppendLine(oneday.Aggregate("", (r,x) => r + x + " "));
            }
            return sb.ToString();
        }
    }

    // 一致かどうかを簡単にするために、構造体にしている。
    public struct Game {
        public int A { get; private set; }
        public int B { get; private set; }

        // コンストラクタの代わりにこれを呼ぶ。
        public static Game Create(int a, int b) {
            var game = new Game();
            if (a < b) {
                game.A = a;
                game.B = b;
            } else {
                game.B = a;
                game.A = b;
            }
            return game;
        }

        public override string ToString() {
            return string.Format("{0}-{1}", A, B);
        }

        public bool Contains(int team) {
            return (this.A == team || this.B == team);
        }
    }
}

なんか複雑だなーということで、Webを調べていたら、すばらしい方法がありました。
参考URL 「リーグ戦の組み合わせ」http://www.geocities.co.jp/Berkeley-Labo/6317/league_01.htm

いやー、このアルゴリズムを考えた人は、すごいなー。これを自力で考え出せ!といわれても、たぶんできないと思います。
以下、そのアルゴリズムをC#で実装したコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var s = new Scheduling();
            var ans = s.DoPlan(8).ToList();
            ans.ForEach(x => Console.WriteLine(string.Join(" ", x.Select(y => y.ToString()))));
            Console.ReadLine();
        }
    }

    public class Pair {
        public int A { get; private set; }
        public int B { get; private set; }

        public Pair(int a, int b) {
            A = a;
            B = b;
        }

        public override string ToString() {
            return string.Format("{0}-{1}", A, B);
        }
    }

     class Scheduling {
        private List<int> Rotate(IEnumerable<int> ring) {
            var first = ring.Take(1);
            return ring.Skip(1).Concat(first).ToList();
        }

        public IEnumerable<IEnumerable<Pair>> DoPlan(int n) {
            List<int> ring = Enumerable.Range(2, n - 1).ToList();
            for (int i = 0; i < n - 1; i++) {
                List<Pair> games = new List<Pair>();
                games.Add(new Pair(1, ring[0]));
                int ix = 1;
                for (int diff = n - 3; diff > 0; diff -= 2) {
                    games.Add(new Pair(ring[ix], ring[ix + diff]));
                    ix++;
                }
                yield return games;
                ring = Rotate(ring);
            }
        }
    }

}

実行結果も示しておきます。
2つ目のプログラムでは、結果を縦方向に眺めると、上手い具合に循環しているのが見て取れます。

■最初のプログラムの実行結果
1-2 3-4 5-6 7-8
1-3 2-4 5-7 6-8
1-4 2-3 5-8 6-7
1-5 2-6 3-7 4-8
1-6 2-5 3-8 4-7
1-7 2-8 3-5 4-6
1-8 2-7 3-6 4-5

■2つめのプログラムの実行結果
1-2 3-8 4-7 5-6
1-3 4-2 5-8 6-7
1-4 5-3 6-2 7-8
1-5 6-4 7-3 8-2
1-6 7-5 8-4 2-3
1-7 8-6 2-5 3-4
1-8 2-7 3-6 4-5



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52409779