席替えスクリプト

sekigae.py

"""
現状一番いけていないこと:
 - 「一度組み合わさった人と２度と同じグループになれない」

今後の展望:
- k回回して候補がなかった場合、ペナルティスコアが最も低い候補を表示する
- 「絶対に組み合わせをしたい」ペアを指定できるようにする

■これはなに？
■前提条件
机が5個あったとします。
既に2回席替えが行われました。
■やりたいこと
ある人を、
- 同じ机に座らないように
- 同じ人と2度と同じにならないように
配置します

入力:
grp1 = []
grp1.append([1,2,3,4])
grp1.append([5,6,7,8])
１回目, 1,2,3,4さんがグループ１、　5,6,7,8さんがグループ2でした。

出力例:
 [[12, 17, 20, 22], [1, 15, 21, 28], [4, 13, 19, 23], [2, 11, 14, 26], [3, 5, 16, 18]]

実装方針:
2回しか席替えしていないので力づくです。
DFS等で正しく枝刈りして実現不可かどうかの判別をすべきですね。
"""
from random import randrange

# 1回目にすでに組まれたグループ
grp1 = []
grp1.append([1,2,3,4])
grp1.append([5,11,12,13])
grp1.append([14,15,16,17])
grp1.append([18,19,20,21])
grp1.append([22,23,26,28])

# 2回目にすでに組まれたグループ
grp2 = []
grp2.append([18,11,15,19])
grp2.append([22,3,23,14])
grp2.append([26,20,1,5])
grp2.append([4,12,16,28])
grp2.append([2,13,17,21])

# これまでに組まれたグループ
groups = []
groups.append(grp1)
groups.append(grp2)

# 1回目のグループのメンバーの列挙
allmember = []
for a in grp1:
    allmember.extend(a)

# 手抜きをするためのloopcount(この回数トライに失敗したらやり直す)
trycount = 10**3

# 出来るまで繰り返す
while True:
    didGroup = True
    cnt = 0

    # 新しいグループリスト
    newgroup = []
    for i in range(len(groups[0])):
        newgroup.append([])

    for personnum in allmember:
        # その人が過去に所属したことのあるグループを列挙
        groupHistory = []
        for group in groups:
            for gnum in range(len(group)):
                if personnum in group[gnum]:
                    groupHistory.append(gnum)

        # その人が所属できるチームがあるかを繰り返す
        while True:

            # 今まで所属したことないグループであるかを調べる
            groupCantidate = randrange(len(grp1))
            if groupCantidate in groupHistory:
                continue

            # n 回やってもダメなら
            cnt += 1
            if cnt > trycount:
                didGroup = False
                break

            duplicate = False

            # 今参加しようとするグループの人と過去にかぶったことがあるか？
            membersCandidate = set(newgroup[groupCantidate])
            for i in range(len(groupHistory)):
                memberOld = set(groups[i][groupHistory[i]])
                if len(membersCandidate & memberOld) != 0:
                    duplicate = True
                    break
            # もし被ったことがあるなら別のグループを選ぶ
            if duplicate:
                continue
            # もし、過去に被ったことがないならそのグループを選ぶ
            newgroup[groupCantidate].append(personnum)
            break
    if didGroup:
        break

if didGroup:
    print(newgroup)
else:
    print("---")