Excel-DNA で XLL をつくる(その11)

 ネット上で、たまたま「組合せ」の問題を見つけて・・・ピクピクっと反応してしまい・・・
「メンバーが極力重複しないランダムなグループをExcelで作成する方法。」って質問を、考えてみました。

 質問にある、「班内のメンバーの重複が出来るだけ発生しない」 というところは、「同じ人とは出来るだけ一緒にならないように」と解釈して記述してみます。参加するたびに違うメンバーになっていて、同じ人にはなかなか会わないような組合せにします。・・・かえって、わかりにくいでしょうか?(笑)

 それと、「5人構成の班が発生する場合、一日につき極少数を認める」 というところは無視して、必ず指定された人数で班を構成するようにします。なぜかというと、例えば10人を3人のグループに分けていった場合、最後に1人残ります。1人では班が構成できないので、すでに班に所属した事のある人(残りの9人)の中から2人を選んで班を構成します。次に班を構成する時には、この2以外で構成すれば、いずれかの班に所属する回数に不均衡は生じません。

 「出来る限り重複しないように」という条件についてですが、班を共にした相手を記録するようにすれば、同じ班になる確率を均等にすることができますが、ここでは偶然に任せていますのでランダムにムラが発生します。「あれ?またお前かぁ~!」ということもあり得ます♪ これも味でしょう(笑)

 Excel-DNA を利用する上でのキモは前回同様 Excel4.0 Macro の利用になります。今回は、多くのセルを利用する上、多数のセルを参照する関数も多用しますので、「シート再計算の制御」と「再描画の制御」を行っています。

 プログラムの動作は・・・

  1. 総人数をセルから読み込む
  2. グループの構成人数をセルから読み込む
  3. 一日に必要なグループの数をセルから読み込む
  4. 作成する日数をセルから込みこむ
  5. 再計算・再描画を停止して計算する
  6. 計算結果をシートに反映し、再計算・再描画する

となります。

 シートのどの行から書込むか?どの列から書込むか?何列おきに書込むか?などは、コード上に定数で設定しました。必要があれば変更することが出来ます♪ 

(こんな感じ↓)

<DnaLibrary RuntimeVersion="v4.0" Language="CS">
<!&#91;CDATA&#91;
using System;
using System.Collections.Generic;
using ExcelDna.Integration;

public static class RndGroupMethod
{
    const int START_ROW = 2; // データ挿入開始行定数
    const int START_COL = 0; // データ挿入開始列定数
    const int ROW_MAX = 100; // 最大利用行数定数
    const int COL_SPAN = 2;  // 列間定数
    const int COL_MAX = 30 * COL_SPAN; // 最大利用列数定数

    &#91;ExcelCommand(MenuName = "グループ作成", 
                  MenuText = "A1名をB1名のC1個のグループにD1回均等に振り分ける")&#93;
    public static void MakeRandomGroup()
    {
        FixExcel();  // 手動再計算・ScreenUpdating = False
        RndComparer rcmp = new RndComparer();
        ExpComparer excmp = new ExpComparer();
        int row = START_ROW; int col = START_COL;
        int _try = 0; 

        // Reference読込
        ExcelReference total_ref = new ExcelReference(0, 0);
        int total_count = int.Parse(total_ref.GetValue().ToString());
        ExcelReference member_ref = new ExcelReference(0, 1);
        int member_count = int.Parse(member_ref.GetValue().ToString());
        ExcelReference team_ref = new ExcelReference(0, 2);
        int group_count = int.Parse(team_ref.GetValue().ToString());
        ExcelReference lap_ref = new ExcelReference(0, 3);
        int date_count = int.Parse(lap_ref.GetValue().ToString());

        // 不能な問題なら終了
        if (total_count < member_count * group_count) { return; }
        if (ROW_MAX < (member_count + 1) * group_count) { return; }

        // 解を保持するリスト生成
        List<List<Group>> DateList = new List<List<Group>>();

        // Personオブジェクト生成・登録
        Group PersonList = new Group(total_count);

        while (DateList.Count < date_count)
        {
            List<Group> g_date = Make(member_count, group_count, PersonList);
            if (g_date != null)
            {
                DateList.Add(g_date);
            }
            else
            {
                _try++;

                if (PersonList.IsFinished(member_count))
                {
                    PersonList.InitIsMember();
                    PersonList.Randomize(total_count);
                }
                else if (total_count < _try)
                {
                    PersonList.InitIsMember();
                    PersonList.TabooClear();
                    PersonList.Randomize(total_count);
                    _try = 0;
                }
                else
                {
                    PersonList.Randomize(total_count);
                }       
                PersonList.Sort(rcmp);
                PersonList.Sort(excmp);
            }
        }

        RefrectSheet( row, col, DateList);
        UpDateExcel();  // 自動再計算・ScreenUpdateing = True
    }

    &#91;ExcelCommand(MenuName = "グループ作成", MenuText = "データ削除")&#93;
    public static void Clean()
    {
        FixExcel();  // 手動再計算・ScreenUpdating = False
        int row = START_ROW;
        int col = START_COL;
        for (int r = row; r < row + ROW_MAX; r++)
        {
            for (int c = col; c < col + COL_MAX; c += COL_SPAN)
            {
                ExcelReference trg_cell = new ExcelReference(r, c);
                trg_cell.SetValue("");
            }
        }
        UpDateExcel();  // 自動再計算・ScreenUpdateing = True
    }

    private static void RefrectSheet(int row, int col, List<List<Group>> DateList)
    {
        // 表示処理
        foreach (List<Group> g_list in DateList)
        {
            foreach (Group g in g_list)
            {
                foreach (Person p in g)
                {
                    ExcelReference trg = new ExcelReference(row, col);
                    trg.SetValue(p.Index);
                    row++;
                }
                row++;
            }
            row = START_ROW;
            col += COL_SPAN;
        }
    }

    private static void UpDateExcel()
    {
        XlCall.Excel(XlCall.xlcEcho, true);
        XlCall.Excel(XlCall.xlcOptionsCalculation, 1);
    }

    private static void FixExcel()
    {
        XlCall.Excel(XlCall.xlcEcho, false);
        XlCall.Excel(XlCall.xlcOptionsCalculation, 3);
    }

    private static List<Group> Make(int m_count, int g_count,
                                    List<Person> PersonList)
    {
        List<Group> g_list = new List<Group>();
        for (int g_num = 0; g_num < g_count; g_num++)
        {
            Group g = new Group();
            foreach (Person p in PersonList)
            {
                // m_countで指定されたメンバー数を満たせば加える
                g.TryAddMember(p);

                // m_countで指定されたメンバー数になったらループを抜ける
                if (g.Count == m_count)
                {
                    break;
                }
            }
            g_list.Add(g);

            // グループ生成に失敗したらメンバーを解放する
            if (g.Count != m_count)
            {
                foreach (Group _g in g_list)
                {
                    _g.InitIsMember();
                    _g.DecExpNum();
                }
                return null;
            }
        }
        return g_list;
    }
}

public class RndComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.RndIndex - y.RndIndex;
    }
}

public class ExpComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.ExpNum - y.ExpNum;
    }
}

public class Person
{
    public List<Person> Taboo = new List<Person>();
    public int Index;
    public bool IsMember;
    public int RndIndex;
    public int ExpNum;

    // コンストラクタ
    public Person(int index, int rnd)
    {
        this.Index = index;
        this.RndIndex = rnd;
        this.IsMember = false;
        this.ExpNum = 0;
    }
}

public class Group : List<Person>
{
    public Group(int total_count)
    {
        Random rnd = new Random();
        for (int i = 0; i < total_count; i++)
        {
            this.Add(new Person(i + 1, rnd.Next(0, total_count * 10)));
        }
    }

    public Group()
    { }

    public bool TryAddMember(Person p)
    {
        if (p.IsMember)
        {
            return false;
        }
        foreach (Person m in this)
        {
            // member_p とp がタブー なら戻る
            if (m.Taboo.Contains(p) || p.Taboo.Contains(m))
            {
                return false;
            }
        }

        this.Add(p);
        p.IsMember = true;
        p.ExpNum++;

        foreach (Person m in this)
        {
            m.Taboo.Add(p);
            p.Taboo.Add(m);
        }
        return true;
    }

    public void InitIsMember()
    {
        foreach (Person p in this)
        {
            p.IsMember = false;
        }
    }

    public void DecExpNum()
    {
        foreach (Person p in this)
        {
            p.ExpNum--;
        }
    }

    public void Randomize(int total_count)
    {
        Random rnd = new Random();
        foreach (Person p in this)
        {
            p.RndIndex = rnd.Next(0, total_count * 10);
        }
    }

    public void TabooClear()
    {
        foreach (Person p in this)
        {
            p.Taboo.Clear();
        }
    }

    public bool IsFinished(int member_count)
    {
        int yet = 0;
        foreach (Person p in this)
        {
            if (!p.IsMember)
            {
                yet++;
            }
            if (member_count <= yet)
            {
                return false;
            }
        }
        return true;
    }
}

&#93;&#93;>
</DnaLibrary>
 

 コードの記述は以上です。テキストファイルにコピペして、ファイルを RndGroup.dna と名前変更しましょう。

次に、Excel を開き「名簿」という名前のシートを作って、そこに名簿を作成し、C列のC2セル以降に参加回数をカウントする関数を設定しておきます。

(こんな感じ↓)

つづいて、Group という名前のシートをつくり、左のセルの数値を名簿から探して名前を表示するように関数を設定しておきます。例えば”A3″ が “7” という数値の場合、名簿の”7″ 番の”大村敦志” が表示されます。

(こんな感じ↓)

 さて、これで準備が出来ました。「A1 セルに全体の人数、B1 セルにグループの構成人数、C1 セルに一日に必要なグループ数、D1 セルに作成する日数」 を入力して、コマンドを実行します。

(こんな感じ↓)

冒頭の質問にあった「80人で6人グループ13個を21日分」作成すると、実行結果は・・・

(こんな感じ↓)

 定数 COL_SPAN = 2 に設定しているので、A列 C列 E列 ・・・ と一行置きに生成した数値が出力され、
名簿から該当する氏名が関数によって代入されています。
 「名簿」シートを見ると各人の班構成回数は20回、もしくは21回 となっています。

(こんな感じ↓)

最後に・・・。

 「アドイン」⇒「グループ作成」タブにある、もう一つのボタン「データ削除」 を押すと、作成したデータを削除します。
この時、もし FxExcel() 関数の記述がないと、膨大な処理時間がかかります。「名簿」シートの「回数」列の関数が、「Group」シートのデータ範囲を参照しており、データが1つ変化するたびに全てを再計算するからです。

 参照セルの多いシートで多くのデータを変更する場合は、再計算モードを一旦「手動」にしておき、データの変更が終わってから「自動」に戻すと良いでしょう。描画の更新も同じ事ですね♪

 まとめ:
 Personクラスと、Personクラスのリストを継承したGroupクラスを定義し、それぞれのインスタンスをつかって組み合わせを生成しました。手軽にオブジェクト指向の記述ができるのも .NetFramework を利用する利点の一つですね^^

 Excel-DNA コードからの Excel4.0 MacroFunction の呼び出しとして、
「再描画制御」

        XlCall.Excel(XlCall.xlcEcho, true);   //ScreenUpdateする
        XlCall.Excel(XlCall.xlcEcho, false);  //ScreenUpdateしない


「再計算制御」

        XlCall.Excel(XlCall.xlcOptionsCalculation, 1);  //自動再計算
        XlCall.Excel(XlCall.xlcOptionsCalculation, 3);  //手動再計算


を利用してみました♪

 しかし・・・思ったよりもコードが長くなってしまいました(笑) 
アルゴリズムに工夫の余地がありそうですね^^
エレガントな解法を求めます♪

では、また(笑)

ダウンロードはこちら ⇒ RndGroup.zip


カテゴリー: Excel, 組合せ最適化, .NetFramework タグ: パーマリンク

Excel-DNA で XLL をつくる(その11) への8件のフィードバック

  1. y sakuda のコメント:

    しかし・・・・・
    今更Macro4ってのも・・・・・

  2. y sakuda のコメント:

    個人的には全く使ってないから、関係なしw
    (使ってないと言うより殆ど知らないw・・・・Excelの経歴割と浅いんです・・・・年も若いw・・・本格的に使ったのは97以降)

    • supermab のコメント:

      >個人的には全く使ってない
      わたしも Excel-DNA 使い始めてから、macro4fun とにらめっこの状態です♪
      pagesetup のような関数がVBAで記述するよりもかなり処理が早いらしいことも最近知りました。
      >Excelの経歴割と浅いんです・・・・
      同じく^^ Excel をUI の一つとしてとらえてしまうために、Excel 自体の機能にちっとも精通できません。だから・・・関数で出来ないのかも(汗) 「Excel Maniacs」 も・・・ギブアップばっかりです(笑)
      >年も若いw・・・
      も・・・もちろんお若いです♪

  3. manju のコメント:

    一度作動させたらデータ削除しても次から作動しなくなるのですが、なぜですか?
    あと作動させようとする度に手動計算に勝手に切り替わります。

    • supermab のコメント:

      manju さん
       
       A1,B1,C1 セルの数値を変更される場合、組合せの生成不能な数値にすると、
      計算を試みますが、途中で終了するためにおっしゃる結果となりますね。

      例えば、A1(総人数)に30と入力したとします。
      その状態で、
      B1(グループの数)に 5 。C1(組の人数)に 8 。
      と入れた場合、 5 x 8 = 40 となって、30人では組合せの生成が出来ません。

      処理を中断して戻るので、UpDateExcel()が実行されずに再計算が手動になったままとなりますね^^

      コード中の「// 不能な問題なら終了」の return 文の前に、UpdateExcel()を挿入すると、
      不能な問題で処理を中断しても再計算モードを「自動」に戻してくれます。

      • manju のコメント:

        supermabさん

         返信が早く、とても助かりました。正直返信もらえないかなと思っていたので、とてもうれしいです。ありがとうございます。

        割り切れる数字にすると使えるようになりました。こんなことで質問してしまい、申し訳ありませんでした。

        ゼミの発表の班分けで使わせてもらいます。

        丁寧な解説、ありがとうございました。m(__)m

        • supermab のコメント:

          お役に立てたら嬉しいです^^

          ちなみに、B1 x C1 ∝ A1 でなくても

          B1(グループの数) x C1(グループの人数) <= A1(総人数)

          であれば、実行可能です。
          初日に全員が割り振られるのは無理ですが、何日か経つとやがて
          機会均等に割り振られます。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です