MGreen
@MGreen (M Green)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

【組み合わせ】19組 (1-4人) を、組ごとはバラバラにせず8テーブルに分ける、ラクな早い方法

背景:あるイベント企画で以下のグループ分けタスクが発生しました。
(本当にこのようなタスクが発生したのですが、実名をランダムに変えて表現しています)

↓このように「19組の、名前と家族の人数」のリストがあります。

■リスト
連番,お名前(Name),家族の人数(本人含) (以下はChatGPTで生成した適当な名前です)
1,佐藤太郎,4
2,高橋みつこ,3
3,田中花子,4
4,鈴木一郎,3
5,松本久美子,2
6,藤井太郎,2
7,井上春子,1
8,渡辺美智子,1
9,斉藤健一,4
10,山本花子,3
11,吉田由美,3
12,中村次郎,1
13,加藤まさし,3
14,林優子,2
15,清水直子,2
16,篠田和夫,4
17,山田恵子,2
18,大野太郎,1
19,小林雅子,1

■やりたいこと
あるイベントで、上記リストの人およびその家族を、8テーブルに分けたい。
1テーブルを5または6人としたい。(できれば)
各家族はバラバラにならないように組み合わせたい。

■結果、↓のように分けることができました。
image.png
image.png

■私が行った方法
ChatGPT4oに何回も上記「リスト」と「やりたいこと」を教えましたが、例えば勝手にリストの名前を二回使われたり、7人のグループと3人のグループができたりしてしまいました。
「7人のテーブルや3-4人のテーブルがあるので、ダメだ。全テーブルを5人または6人にするようにしてほしい」など何回も訂正を教えましたが改善しませんでした。
これはもうだめだと思い、結局ChatGPT4oが提案してきたグループ分けを自分の手で微調整して全グループを5または6にしました。
(たまたま、7人のグループに2人家族がいたので3人のグループに移す、など明らかに簡単な作業のみで改善できる状態でした)


質問
・このような、各組がバラバラにならないようにするグループ分けについて、今世の中にあるツールで一番賢い、早いツールや方法ってなんでしょうか。
(Chat GPTにログインしたうえで、ChatGPT 4oを使ってみても、ダメでした。明らかに改善可能なのに, 4人とか7人のテーブルを提案し続けてくる。)
海外のもっと賢いAI製品とかで何かないですかね?あとは巷の無料ツールとか・・。
・普通に組み合わせ計算式とかを用いてもいいです。
・この種のグループ分けって意外と難しいと思っていて、今回はたまたま全テーブルを5-6人に均一に分けれましたが、家族の人数によってはどこかが4、どこかが7になることを避けられない「解なし」パターンもあるかと思います。まず全部を均一に分けれる可否だけでも知りたいです。

最近イベント企画などをやることも多く、ツールや方法について知っておきたいなと思い投稿してみました。

何かアイディアがある方がいましたら、なにとぞご教示よろしくお願いいたします。

0

4Answer

プログラムの方法ではなくて割り当て方法だけど

家族の人数でソートしておいて家族が多い方から処理
1テーブルに1家族ずつ割り当てる
割り当てる時は現状の各テーブルのうち人数が少ないテーブルにする

これでバランス良く配席されるんじゃないかな?
※実際の配席なら他のことにも気を利かせないとだめだからこうはいかないでしょうけど

2Like

Comments

  1. @MGreen

    Questioner

    大変役立つご回答ありがとうございます!!
    (今回私がやったときは全くマニュアル作業やる気がなくてえい!とAIに投げてしまったのですが)
    確かに、
    家族の人数順にソートして たとえば今回の場合だと:
    一番多 x 一番少の組合せ、
    二番目に多 x 二番目に少の組合せ  
    半端になるところは1人の組を入れる
    とかでざっくり組み分けできましたし、そのあと微調整もしやすかったです!

    あと、同じ人数の家族は同じ機能なので、どういうやり方をやるにしても、ソートしないと考える量が増えちゃいますよね。

    ご教示まことにありがとうございます!!

このような、各組がバラバラにならないようにするグループ分けについて、今世の中にあるツールで一番賢い、早いツールや方法ってなんでしょうか。

このボリュームなら手作業が一番早いです。
コード書いたりツールいじってる時間が無駄です。

この種のグループ分けって意外と難しいと思っていて、今回はたまたま全テーブルを5-6人に均一に分けれましたが、家族の人数によってはどこかが4、どこかが7になることを避けられない「解なし」パターンもあるかと思います。

制限事項を明確にしないと解はでません。
テーブルの数が制限なのか、家族の人数が制限なのか、平均値からの差異が制限なのか?等全然記述が足りません。

まず全部を均一に分けれる可否だけでも知りたいです。

本当に均一に分けられるかどうかだけが知りたいのであれば以下で良いかと。
・合計人数がテーブル数で割り切れるか?
・その際、平均値になる組み合わせで分割できるかどうかを検証
後者は探索空間を効率的に削減しながら総当たりするアルゴリズムで良いかと思います。

ただ、ホントに均一に分けれるかが知りたいのですか?
平均値から大きく外れないという条件だとまた話は変わります。

2Like

Comments

  1. @MGreen

    Questioner

    制限事項について今回は
    ・8つのテーブルをすべて使う
    ・なるべく均等に分ける
    くらいしか制限がないという認識だったのですが、例えば自分が当たり前と思っていた
    「1家族およびそれぞれの人は一回しか使えない」とかも条件の一つであり
    そういう細かいことも明記しないとAIにこたえさせたり計算するのは難しいのかもしれないということがわかりました。

    平均値になる組合せで分割できるか・・について総当たりアルゴリズムというのを使うのですね。やったことがないので、勉強してみます

    ご教示まことにありがとうございます!!

  2. 制限事項はプログラマとそれ以外の人で感覚が違うので、洗い出すのは難しいと思います。
    手作業の方が圧倒的に早いですが、excelのソルバーでもできたので添付しておきます。
    excelならある程度細かい暗黙の制限を気にせず表現できます。
    スクリーンショット 2024-11-20 191458.jpg

  3. @MGreen

    Questioner

    まことにありがとうございますm(__)m なんとソルバーも使ったことがなく、教えてくださり感謝です。まだまだエクセルでことを進めることが多く、大変助かります!ありがとうございました。

数理最適化の中の割り当て問題です。
特にテーブル割当て問題と呼ばれる問題ですね。
(披露宴の席決めやパーティ席ぎめなど呼び名は色々あるらしいです)

数理計画というはAIなどとはちょっと違って
ある制約がある中で最適なものを得るにはどうしたら良いか
を解くような問題です。
Pythonなどにもソルバーと呼ばれる解法の無料ライブラリがあります。
複雑な制約条件がある場合は有償のツールもあります。

このような問題が日常業務であるならばそれらの導入を検討するとよろしいかと。
それほどでもないが、まぁまぁあるので安直に回答を得たい
ということであれば

ChatGPT o1-preview, o1-mini

などが良いと思います。上記問題も綺麗に回答が得られました(私も4oで試したら2家族が捨て置かれました、、、)。
4oはこういう論理的に考える問題が弱いです。o1はこういう論理的な問題に強いと言われています。

ChatGPT Proに契約していればすぐ使えます。いや契約していないよということであれば

GMOさんの天秤AI https://tenbin.ai/workspace/welcome
がユーザー登録だけで無料でo1-preview, o1-mini(やGemini Pro 1.5なども)が使え、上記問題もすぐ解けると思います。

1Like

Comments

  1. @MGreen

    Questioner

    aokikenichi様、まさにほしかったご回答をありがとうございます!culage様も似た形で回答くださいましたが、数理最適化のテーブル割り当て問題というジャンル?がわかってまずうれしいです。

    具体的なツールも、、たしかに、ChatGPT o1-previewでやってみたら一発で正解で驚きました。。(一応ChatGPTは課金しています) 大変助かります!

    GMOさんのツールも無料ということでありがとうございます!契約していない人に勧めることができそうです。

    数理最適化は興味が強い分野なのですが実務であまり使えておらず (やらせてもらえるのはインフラばっかりでして・・)
    このようなちょっとした実務のチャンスをきっかけに少しでもかじれたらなと思っています!

    大変学び多いご回答ありがとうございました!!

これは一般に「ビンパッキング問題」という呼び名で知られている問題です。
https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E5%95%8F%E9%A1%8C

『あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない(NP困難問題)。』……とのことなので、人類はこの問題に対して完全な答えを持っていません。

しかし最高効率でなくてよいならば問題を解くアルゴリズムは存在します。
上記wikipediaにも、2つほどアルゴリズム例が掲載されています。
今回提示している問題程度であれば、このアルゴリズムを使ってテーブルを作り、最後のテーブルに人数が不足した場合は他のテーブルから許される範囲で人を移動させてくる方法で十分に対応可能かと思います。

1Like

Comments

  1. @MGreen

    Questioner

    ・まさにほしかったご回答です、まことにありがとうございます!!まず問題のカテゴリが瓶パッキング問題ということがわかり助かります。

    ・aoki様から席決め問題というコメントももらいました。多分瓶パッキングのほうがよりアルゴリズムも多く、テーブルにつける椅子の位置を考えなくてよいという点で今回は瓶パッキング問題のほうがさらに近かったのかと思いました.

    ・2つのアルゴリズムについてありがとうございました!「こんな簡単そうな組み分けなのに、なぜか自分が最速の分け方を知らないのは、自分がアホなのだろうか・・」と思っていましたが、コンピューターをもってしてもNP困難問題だったということで安心いたしました。

    ひとつ賢くなれました。ご教示まことにありがとうございました!

Your answer might help someone💌