質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • Python

    6803questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5275questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Pythonで出来るだけ公平なランダム当番表(重複なし)を作ってみましたが重複が出てしまいます

受付中

回答 7

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 723

studying_now

score 2

 前提・実現したいこと

Pythonに興味を持ち、先月からwebで調べたりしながら勉強しています。
全くの初心者です。
勉強用に出来るだけ公平な当番表を作ってみました。
(練習用なので無駄な部分が多いかと思います)

実現したいことは、
・人名を連続入力する (例:山田、田中、佐藤...)
・1回の当番あたりの人数を入力する (例:2人)
・53週分の当番表が出力される
・多少の誤差はあるものの、人名ごとに担当回数がほぼ同じになるような
(=出来るだけ公平な)当番表の完成
です。

公平性を保つ為、53週で必要な当番人数の数を上回るように
リストを複製し、複製したリストから人数分ランダムに人名を選び、
選んだ名前はリストから消す、を53回繰り返しています。

しかし、当番数を複数にすると(2人以上)、
どうしても重複してしまいます(例:山田、山田 ← 2人選ばれていない)

重複無しの当番が人数分出力されるように改善したく思っています。

 発生している問題・エラーメッセージ

発生している問題
(1)1番大きな問題
重複無しで指定の当番人数分の人名を抽出したいが、重複してしまう。

(2)2番目以降の問題
・もっとスマートに記述できるなら勉強までに教えていただきたく思っています。
・Excelに出力する部分の記述がいけないのか['']がついた状態で、セルに入ってしまい、
 エクセルの加工がしにくいので、出力時に人名だけがセルに入るように改善したいです。
・もし可能なら最初に「当番表の年」を聞いて、現在「第--週」と出力されている部分を
 その週の「月曜日の日付」で出力したいと思っています。

 該当のソースコード

#! python3
# Rota.py

# 当番表生成
print('たぶん公平な当番表作成')
print('●やっていること●')
print('1.当番人数×53週 = 1年に必要な当番人数を算出')
print('2.「必要な当番人数」を上回るように「メンバーリスト」を複製')
print('3.メンバーリストからランダムにメンバーを選び、選ばれたメンバーはリストから消す')
print('4.ランダムで、かつ回数に偏りが生まれにくい当番表の完成(たぶん)')
print('5.さらに出来上がったリストをエクセルで出力(適当なのでなおしたい)')
print('')

#当番表の名前
print('当番表の名前は何にしますか? (例)掃除当番表')
print('※ 出力されるエクセルファイルのファイル名になるので注意')
rotaname = input()
print('当番表の名前は「' + str(rotaname) + '」となります:')

#メンバーの名前を聞く
orgmembers = []
while True:
    print('メンバー' + str(len(orgmembers) + 1) + 'の名前を入力してください' + '(終了するにはEnterキーだけ押してください)')
    name = input()
    if name == '':
        break
    orgmembers = orgmembers + [name]
print('メンバーは' + str(len(orgmembers)) + '名で、以下の通りですね:')
for name in orgmembers:
    print('  '+name)

#当番1回あたりの人数を聞く
print('当番人数は一回当たり何人ですか?(半角の数字で入力)')
rotanum = input()
print('当番1回当たり' + str(rotanum) + '名ですね:')


#当番表出力
print('第53週までの当番表を出力します')
import random
members = orgmembers

#トータル何人が当番か計算
# トータルの人数×53週を計算し、totalmemに格納
totalmem = 53 * int(rotanum)

#トータルの当番数を、リストの当番で割って商qと余りmodを算出
# totalmemをorgmembersで割って、その商を算出
q = int(totalmem) // len(orgmembers)
mod = int(totalmem) % len(orgmembers)

#トータルメンバーリストの作成
# qの回数+1だけ、orgmembersを繰り返しtmlistに追加
tmlist = orgmembers
for i in range(int(q)):
    tmlist = tmlist + orgmembers

#トータルメンバーリストのシャッフル
# 念のため、tmlistをシャッフルする
random.shuffle(tmlist)

#当番人数分の名前を抽出
# 最終的なメンバーをfinalmemに格納
# エクセルファイルに最終的なメンバー表を出力
# memに、tmlist内からrotanumの数だけランダム抽出し、格納
# mem1に、memの固有要素数を抽出し、格納(重複が削除される)
# memの長さとmem1の長さを比較し、等しくなかった場合はmemの選びなおし、等しかったら次へ
# (例:memリスト(選んだメンバーリストの要素数)と、mem1(選んだメンバーリストの個有数)が一致しないと、
# 重複があるということになるので、重複がなくなるまで選びなおす)
# memの長さがrotanumより小さかった場合、memの選びなおし
# (例:2人当番で重複するとmem1が1となり、memと等しくなってしまい、
# 重複があるのに処理が次に移ってしまう為)
# 重複無しの選抜メンバーにfinalmemに第何週かの情報をつけて結果を格納
# Excelに出力
# 53週分ループしたら終わり
finalmem = []
totaldelmem = []
import openpyxl
wb = openpyxl.Workbook()
sheet = wb.active
for i in range(53):
    mem = random.sample(tmlist,int(rotanum))
    mem1 = list(set(mem))
    if len(mem1) < len(mem):
        mem = random.sample(tmlist,int(rotanum))
        mem1 = list(set(mem))
        if len(mem1) != int(rotanum):
            mem = random.sample(tmlist,int(rotanum))
            mem1 = list(set(mem))
    sheet['A' + str(i+1)] = '第' + str(i+1) + '週 ' + str(mem)
    print('第' + str(i+1) + '週 ' + str(mem))
    finalmem.append(str(mem))
    for j in range(int(rotanum)):
        delmem = mem[0]
        tmlist.remove(delmem)
        mem.remove(delmem)
        totaldelmem.append(delmem)
wb.save(str(rotaname) + '.xlsx')

#finalmemに結果が格納されてるけど、うまく加工できない
#後で何とかしたい

#公平度チェック
print('今回の公平度は以下の通り')
uniq_tdm = list(set(totaldelmem))
for k in range(len(orgmembers)):
    tdm = uniq_tdm[0]
    print('●'+(tdm) + 'の当番回数は')
    print(totaldelmem.count(tdm))
    uniq_tdm.remove(tdm)

#おまけ
print('エクセルファイルは.pyファイルと同じフォルダに出来てるよ')
print('ファイル名は' + str(rotaname) + '.xlsx です')

 試したこと

当初重複に対応するため、

memに、tmlist内からrotanumの数だけランダム抽出し、格納
mem1に、memの固有要素数を抽出し、格納(重複が削除される)
memの長さとmem1の長さを比較し、等しくなかった場合はmemの選びなおし、等しかったら次へ
(例:memリスト(選んだメンバーリストの要素数)と、mem1(選んだメンバーリストの個有数)が
一致しないと、重複があるということになるので、重複がなくなるまで選びなおす)
memの長さがrotanumより小さかった場合、memの選びなおし
(例:2人当番で重複するとmem1が1となり、memと等しくなってしまい、
重複があるのに処理が次に移ってしまう為)

という仕組みで回避を試みていますが、これでもやっぱり重複してしまいます。

 補足情報(FW/ツールのバージョンなど)

Anaconda3 (64-bit)でPython 3.6.4 を使用しています

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 7

+7

考えてみました。
基本的には構成員をシャッフルしたリストからどんどん割り当てていき
なくなれば新たにリストを作成して再割り当てしていきます。
ただ、構成人数が1回の当番人数で割り切れない場合、重複を避けなければならないのがややこしいですね。

import random

N_MBR = 5  # 構成人数
N_GRP = 2  # 当番人数
N_WEEK= 10 # 稼働週

groups = [] # 選抜結果。週毎の当番人 [ [0,1],[2,3]....]

cur_members = [] # 現在の割り当て人員リスト
for i in range( N_WEEK):

    cur_grp = []

    # 残り割り当て人員が足りない
    if len(cur_members) < N_GRP:
        cur_grp = cur_members[:] # 残員をすべて割り当て

        # 新たな割り当てリストを作成
        cur_members = [i for i in range(N_MBR)]
        random.shuffle(cur_members)

        N_REMAIN = N_GRP-len(cur_grp) # 残り必要な人数
        del_members = []

        # すでに割り当て済みと重複しない人員を選抜
        for i in range(N_REMAIN):
            for m in cur_members:
                if m not in cur_grp:
                    del_members.append(m)
                    cur_grp.append(m)
                    break

        # 割り当て済みの人員を割り当てリストから削除
        for r in del_members:
            cur_members.remove(r)

    else:
        cur_grp = cur_members[:N_GRP] # 先頭から割り当て
        del cur_members[:N_GRP]       # 割り当て済みは削除

    groups.append(cur_grp)

# 結果
for g in groups:
    print(g)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/29 18:33

    重複排除がややこしいといっても他の方法に比べてわかりやすいのではないでしょうかw
    満たさないといけない制約を論理によって自動的に排除できる点が分かり易さのポイントである気がします!

    キャンセル

  • 2018/05/29 18:35

    ご回答頂きありがとうございます。

    理解に時間がかかる為、完全に理解できたとはいえない状況ですが、
    何回かrunしてみたところ、重複無しで選択できています!

    これから頂いた記述をしっかり理解したいと思いますが、
    取り急ぎ、お礼申し上げたく返信させていただきました。
    ありがとうございます!

    キャンセル

  • 2018/05/29 18:42

    動作は問題ないと思うのですが、重複削除部分がなんか泥臭いな~と思いつつ回答しちゃいました。

    キャンセル

  • 2018/05/29 19:31

    いえいえ、大変勉強になります!

    キャンセル

+5

もういい答えがありますが、せっかく書いたので。

import random

names = list('abcdefghijklmnopq')
nums = 5

names_ = names[:]
random.shuffle(names_)

hist = []
for _ in range(54):
    t = min(len(names_), nums)
    ans = [names_.pop() for _ in range(t)]
    if t < nums:
        names_ = list(set(names) - set(ans))
        random.shuffle(names_)
        ans_ = [names_.pop() for _ in range(nums-t)]
        names_ += ans
        random.shuffle(names_)
        ans += ans_
    print(ans)
    assert len(ans)==len(set(ans))
    hist += ans

from collections import Counter

c = Counter(hist)
print(c)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/29 18:39

    あ~なるほど!
    setを使うと簡潔に書けますね。

    キャンセル

  • 2018/05/29 18:44

    random.choicesが重複ありでなければ、と考えながら、ライブラリを漁ってみたり…

    if文内のリストの合成の順序が重要である割に、一意的ではないのが少し悩ましいところですね。

    キャンセル

  • 2018/05/29 18:46

    ご回答頂き、ありがとうございます!

    頂いた内容を理解するのに時間が必要ですが、
    何回かrunしてみたところ、早くて重複無しですね!
    ありがとうございます!

    これから頂いた記述をしっかり理解したいと思いますが、
    取り急ぎ、お礼申し上げたく返信させていただきました。
    ありがとうございます!

    キャンセル

  • 2018/05/29 18:53

    set減算で重複削除したあとにシャッフルと、シャッフル後に重複削除。
    たしかに合成順の違いから結果の違い(偏り)が生じないかちょっと気になりますね。

    キャンセル

  • 2018/05/29 22:25

    お二人とも
    ・同じ日にそれぞれ異なる人で当番グループを形成すること
    ・それぞれの人の総当番日数に偏りがないこと
    を条件に解いておられ、ある人が誰と組になるかは乱数に任せる方針と思います。グループで一緒になった人の頻度の分布や多分正規分布っぽくなると思います。メンバー数9人、当番人数/週=3、100週で結果を集計してみたところ、can110さん、mkgreさんともに差があるようには見えませんでした(ともにmin=12~24, max=44~58, 平均=33.3, 標準偏差6~7ぐらい)

    例えば当番割り当てでし〇かちゃんと16回、〇ャ〇ア〇と58回同じグループになるなんてこともありそんなとき○び○君は誰かに泣きつく気がしますが、NP困難or完全だったりするんでしょうか・・・

    キャンセル

  • 2018/05/29 22:32

    横槍。私もさっき組み合わせを先に列挙してそこから選べば・・・と思って回答書きかけたんですけど、単に可能な組み合わせからランダムに選ぶと、当番日数の偏りの判定がないので、悲しいことになります。
    組み合わせの集合から、各組み合わせに含まれる要素の回数に偏りがないように選ぶとすると、どんな方針が良いでしょうかね? いまいちうまいのが思いつかなくて

    キャンセル

  • 2018/05/29 22:36 編集

    検証ありがとうございます。
    > 例えば当番割り当てでし〇かちゃんと16回、〇ャ〇ア〇と58回同じグループになるなんてこともあり
    それはやだなあw
    何をもって「公平」かによりますが、いっそ初期状態はランダムからスタートし、あとは構成員m人から当番員n人の全組み合わせ順で割り当ててもらったほうが(少なくとも私は)良いです。

    キャンセル

  • 2018/05/29 22:41 編集

    自分もhayataka2049さんの方法をコメントしちゃったんですが、その方針だと下手に組み合わせをランダムに選ぶと今度は個人の当番日数の分布が正規分布になり...誰かと58回同じになるのは我慢してもらっても当番日数自体が正規分布だとクラスで暴動がおきますね...
    can110さんがおっしゃるような規則的な割り当てが現実的な気がしました。

    キャンセル

  • 2018/05/29 22:46 編集

    はい。というか結局KSwordOfHasteさんの回答で示した筋が妥当と思います。
    当事者として考えるとジ○イ○ンと58回と当たる可能性のあるルールはやだな、思いました(自分でそんな回答しといて何ですが)。

    キャンセル

  • 2018/05/29 22:57

    し〇かちゃんと絶対一緒に当番できなくなるのもこれまた寂しいのでなんとも言い難いですが・・・本件からはずれますが、実際の割り当て問題には「Aさんはこの日はダメ」とか「BとCは組み合わせちゃダメ」といった制約がありそうなのでもっと複雑な問題なのかも知れませんね。

    キャンセル

  • 2018/05/29 23:08

    > 実際の割り当て問題には「Aさんはこの日はダメ」とか「BとCは組み合わせちゃダメ」
    現実問題としてはこれが必ず入りますね。そのとたんに「公平」な割り当ては絶望的になりますがw
    現実的には、各員の総労働時間を平均化するルールが優先されるかと思います。

    キャンセル

+3

コメントを読む限り、『組み合わせ最適化』 で解く課題のような気がしてきました。(シフトスケジュール最適化の派生?)
と言う事で 試しにPuLPで書いてみました

今回いれた制約事項は

  • メンバーは全員で5人
  • 一回の当番は2人
  • 全てのメンバーができるだけ同じ回数だけ当番を行う
  • 2回連続の当番を避ける
    です

出来るだけ当番を組む相手がバラバラになるようにする為の制約は入れておりません - 面倒そうなので・・・

import pulp
import numpy as np

# メンバー数
members = 5
# 週
weeks = 53
# 当番の人数
duty_number = 2
# 一人当たりの最低当番数
minimum_number_of_duties = duty_number * weeks // members

prob = pulp.LpProblem()

### 目的関数は無し
prob += 0

# 変数を生成 (0: 当番なし, 1: 当番)
var = pulp.LpVariable.dicts("duty", (range(members),range(weeks)), 0,1, 'Binary')

### 制約条件
# 一回あたりの当番の人数の制約
for w in range(weeks):
    prob += pulp.lpSum([var[m][w] for m in range(members)]) == duty_number
# 一人当たりの最低当番数の制約
for m in range(members):
    prob += pulp.lpSum([var[m][w] for w in range(weeks)]) >= minimum_number_of_duties
# 2回連続の当番をしない
for w in range(weeks-1):
    for m in range(members):
        prob += var[m][w] + var[m][w+1] <= 1

### 解く
s = prob.solve()

# 結果表示
for w in range(weeks):
    print("Week{:02d} : ".format(w), end='')
    for m in range(members):
        print(int(pulp.value(var[m][w])), end=' ')
    print()
for m in range(members):
    print("Member{:02d} : ".format(m), end='')
    print("{:d}回".format(sum(int(pulp.value(var[m][w])) for w in range(weeks))))

#Week00 : 0 1 0 1 0
#Week01 : 0 0 1 0 1
#Week02 : 1 1 0 0 0
#Week03 : 0 0 1 0 1
#Week04 : 1 1 0 0 0
#Week05 : 0 0 0 1 1
#Week06 : 1 0 1 0 0
#Week07 : 0 1 0 0 1
#Week08 : 1 0 0 1 0
#Week09 : 0 1 0 0 1
#Week10 : 0 0 1 1 0
#Week11 : 0 1 0 0 1
#Week12 : 0 0 1 1 0
#Week13 : 0 1 0 0 1
#Week14 : 1 0 0 1 0
#Week15 : 0 1 0 0 1
#Week16 : 1 0 1 0 0
#Week17 : 0 1 0 1 0
#Week18 : 1 0 0 0 1
#Week19 : 0 0 1 1 0
#Week20 : 1 0 0 0 1
#Week21 : 0 1 0 1 0
#Week22 : 1 0 1 0 0
#Week23 : 0 0 0 1 1
#Week24 : 0 1 1 0 0
#Week25 : 1 0 0 0 1
#Week26 : 0 0 1 1 0
#Week27 : 1 0 0 0 1
#Week28 : 0 0 1 1 0
#Week29 : 1 0 0 0 1
#Week30 : 0 0 1 1 0
#Week31 : 0 1 0 0 1
#Week32 : 1 0 0 1 0
#Week33 : 0 0 1 0 1
#Week34 : 1 0 0 1 0
#Week35 : 0 0 1 0 1
#Week36 : 1 1 0 0 0
#Week37 : 0 0 1 1 0
#Week38 : 1 1 0 0 0
#Week39 : 0 0 1 1 0
#Week40 : 1 1 0 0 0
#Week41 : 0 0 1 0 1
#Week42 : 0 1 0 1 0
#Week43 : 1 0 1 0 0
#Week44 : 0 1 0 1 0
#Week45 : 1 0 0 0 1
#Week46 : 0 1 1 0 0
#Week47 : 0 0 0 1 1
#Week48 : 1 1 0 0 0
#Week49 : 0 0 0 1 1
#Week50 : 0 1 1 0 0
#Week51 : 1 0 0 0 1
#Week52 : 0 1 1 0 0
#Member0 : 21回
#Member1 : 21回
#Member2 : 21回
#Member3 : 21回
#Member4 : 22回

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

えーと・・・この目的には「完全にランダム」は本当は適してないと思います。

重複するかどうか以前に1日に当番に当たった人が2日にも当番にあたるという確率は0じゃないですし、ランダムにするという意味からはずれてないのでNGとも言えないと思います。

プログラミングの問題というよりは仕様の問題として「当番対象の人たちの順番だけ決めて置き」あとは「その順番に従って割り当てる」方法が一番公平感があると思います。

その際に必要なのは当番対象の人たちを最初だけランダムに並べることだけです。

そうしておいて並び替えた順番がA, B, C, D, Eさんの順番に並んだら

1日 A, B
2日 C, D
3日 E, A
4日 B, C
...以下同様

こうしたらよいと思います。

いやいやそういうことじゃなくて!といいたくなるかも知れませんけどw;

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/29 16:58 編集

    ご回答頂き、ありがとうございます。
    すみません。「完全にランダム」というのは目指しておりません。

    下のほうで、公平度の指標としてカウントしているように、あくまで
    「53週内で当番になる回数が出来るだけ公平」であることをまず目指しています。
    そのため、何週か連続で当番になることがあっても、当番回数さえできるだけ公平であれば
    いいと思っています。

    そして次に、組み合わせが固定化してしまうのを避ける為、
    つたない知識で出来るだけ工夫してみたのですが、なんだかうまくいかないという状況です。
    つまり、AさんとBさんがいつも同じ組み合わせである、という状況を避けたいのです。

    まとめると、当番自体が何週か連続になっても、(偶然組み合わせが同じになるのは仕方ないとして)
    組み合わせが出来るだけ変わっていて、53週内の当番回数が出来る限り同じ、
    というのを目指しています。

    頂いた方法をまず真っ先に考えたのですが、組み合わせが固定化してしまうため、
    ランダムにピックアップするというのをやってみた結果、うまくいかない、という状況です。

    キャンセル

  • 2018/05/29 17:08

    失礼しました!この回答はスルーしていただいた方が・・・
    ちなみにこの条件はなかなか難しい気がします。「組み合わせが固定化する」のをいかにばらけさせるかがポイントなのでしょうけど、充分人数が多いなら同一人物を選ばないようにするだけでも充分ランダムになると思えます。しかし要素の数が限られていてAさんが他の人となるべく均等に当番になるようにということならそれなりのプログラム上の制約を制御した方がよい気がします。

    例えばA~Eさんまでとしたらその全ての組み合わせを生成しておき、人単位ではなくその組み合わせの集合から選ぶとか?

    キャンセル

  • 2018/05/29 17:15 編集

    端的には、冒頭に書いたように、この記述を修正して、
    出てしまう「重複を避けたい」というのが質問なのですが、難しいですかね。。。
    難しいことなのかどうかの判断もつかず困っています。

    よりよい選び方へのご提案を頂いているのだとは思いますが、
    重複に関連したものではないと感じます。

    繰り返しになりますが、53週内の当番数が出来る限り公平であれば問題ないのです。
    例えば、総勢5人(例えばAさんからEさん)で1回当たり2人の当番だと、
    53週で1人あたりの当番回数は21回ないし22回です。
    繰り返し書かせていただいている通り、この誤差は問題ないと考えています。
    (以下追記します)
    何週か連続で当番にあたってしまった人も、早いうちに当番が終わってOKとなることを
    前提としています。
    (追記終わり)

    問題は、2人の当番をピックアップすると、この記述だと1回の当番2人に、(A、A)と、
    同じ人名がピックアップされてしまう点です。
    これを避けたい、というのが質問の内容です。

    キャンセル

  • 2018/05/29 17:15

    あーでもどうしても現実を考えてしまいます。40人いて1回あたり2人が当番として10日後にまわってきたら文句いいたくなります。個々の人があまりに連続して当番にならないようにも配慮すべきでそちらとまんべんなく組みにするというのを両立するのはなかなかややこしそう。やっぱり規則的に巡回させた方が簡単かもしれません。
    A,B
    C,D
    E,A
    B,D<=ここからペアを一つずらす
    C,E
    A,C
    ...
    みたいな・・・

    キャンセル

  • 2018/05/29 17:22 編集

    失礼、脱線してましたね。
    >(A、A)と、同じ人名がピックアップされてしまう

    こういう問題は同じ人を同じ日に割り当てようがなような制約制御を最初から考えるのが自然と思います。例えばある日の当番をAと決めたら同じ日の当番を決めるのはAを抜いた集合から決めるようにします。
    二人の当番を決めるのにグループ1、グループ2を独立に決めるのではなくてグループ1から一人候補を抜き出してある日に割り当てたら、グループ2からその人を一旦抜き出した残りから候補を決めるといった方法が使えませんか?ランダムに選んでしまい同じ人を割り当てたらやり直しというのはごく簡単な少数の集合を相手にするならまだしも普通はそういう非効率な論理は避けると思います。

    キャンセル

  • 2018/05/29 17:23 編集

    本当に当番を回す場合はそうかもしれません。
    しかし、冒頭書いたとおり、記述の練習ですので。。。

    私の質問はそんなに難易度が高いのでしょうか。。。?
    ピックアップした当番の中に重複をなくしたいだけなのですけれど、
    話がどんどん違う方向にいっている気がします。
    記述で修正するのは無理なんですかね。。。

    キャンセル

  • 2018/05/29 17:25

    すみません、2つ目のご回答を頂いている間に送信していたようです。

    一度選んだものを次回の選抜の集団から一旦抜き出しておく、というのは興味深いです。
    しかし全く皆目見当がつきません。。。

    キャンセル

  • 2018/05/29 17:36

    ゴメンナサイ現実問題として妥当な解法の論理を考えてしまいました。質問2の方に着目していたわけです。
    >記述の練習ですので。。。
    コードを書く前にアルゴリズムが問題になるのでアルゴリズムを色々アイデアだししてたつもりでしたがどうも暴走しちゃいました。すみません!
    >難易度が高いのでしょうか。。。?
    高くないけど低くもない印象です。
    >話がどんどん違う方向にいっている気がします。
    それについては申し訳ないです!
    >記述で修正するのは無理なんですかね。。。
    記述=アルゴリズムのことですよね?満足できるような方法はあるはずと思います。自分が簡単なアイデアを思いつけないだけです。もちょっと待ってればよいアドバイスがつくかも知れません。
    自分は今の質問者さんの論理をなるべく生かした形でのよい提案をすぐに思いつけません。
    申し訳ない!

    キャンセル

  • 2018/05/29 17:46

    いえいえ、いろいろとご示唆いただいてありがとうございます。
    私自身がアドバイスを生かすような知識がないために、すみません。

    Pythonの記述のことを指して言っていました(用語の使い方もおかしいかもしれません)
    難易度が低くないとのこと、わかりました。
    なんだか身の丈を大幅に超えたことをしようとしていたみたいです。

    キャンセル

  • 2018/05/29 17:49

    身の丈を超えているとは考えるべきでないです!
    誰だってちょっと難しい問題にぶつかるとそう簡単には解けないもんです。
    ベストでなくても色々解法を試している今の質問者さんのコードはちゃんと経験になるはずですよ!
    ちなみにPythonでどうこうの問題ではなくてアルゴリズム(解法)の問題だと思います。まずはうまくいく方法を考えるのが大事です。それさえ思いつけばPythonででもなんででも書けますよ。

    キャンセル

+2

基本的にはcan110さんのアイディアと同じなんですが、「割り切れない場合重複を避けなければならない」問題を片付けるために、「だったら割り切れるようにすればいいじゃん」という発想で書いてみました。

まず、当番人数の倍数となるような長さの「ランダムな人のリスト」を作ります。これは、大本の「人リスト」をシャフルしたのちに、リストの前の方にいる人をリサイクルすることで行います。
このリストから一週分づつリストを出力していき、尽きたら再度「ランダムな人のリスト」を作るところから繰り返します。

リサイクルされる人は2回当番が回ってくるわけですが、毎回シャフルした後にリサイクルするので、全体としては誰もが公平にリサイクルされるはず。…なのですが、やってみると微妙にばらついてしまいました。リサイクルメンバーは大本リストから順番に割り当てるのがいいかもしれません。

#!/usr/bin/env python3
import random
import csv
random.seed()

last_week_cnt = 53 # 週数
rotanum       = 3  # 当番の人数

#orgmembers = ["西住", "武部", "五十鈴", "秋山"]
#orgmembers = ["西住", "武部", "五十鈴", "秋山", "冷泉", "角谷", "小山", "河嶋", "磯辺"]
#orgmembers = ["西住", "武部", "五十鈴", "秋山", "冷泉", "角谷", "小山", "河嶋", "磯辺", "近藤"]
orgmembers = ["西住", "武部", "五十鈴", "秋山", "冷泉", "角谷", "小山", "河嶋", "磯辺", "近藤", "河西"]

divisible_cnt = (len(orgmembers) // rotanum) * rotanum
len_dutylist  = len(orgmembers)
len_dutylist  += 0 if (divisible_cnt==len(orgmembers)) else (rotanum - len(orgmembers) % rotanum)
week_dutylist = len_dutylist // rotanum

with open("dutylist.txt", "w", newline="") as fho:
  writer =  csv.writer(fho, delimiter = "\t", quoting = csv.QUOTE_NONE)
  for week_cnt in range(1, last_week_cnt+1, week_dutylist):
    # 当番表断片を作る
    dutylist = orgmembers[:]
    random.shuffle(dutylist)
    # 端数が出たときはリスト前部のメンバーをリサイクルしてだぶらせる
    dutylist += [] if divisible_cnt==len(orgmembers) else dutylist[:len_dutylist - len(orgmembers)]

    # 週ごと出力
    for i in range(0, week_dutylist):
      week_cnt2 = week_cnt  + i
      s         =  i * rotanum
      if(week_cnt2 > last_week_cnt):
        break
      out = [week_cnt2] + dutylist[s : s + rotanum]
      print(out)
      writer.writerow(out)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/30 13:49

    しつこくてスミマセン。
    特定のメンバーと一緒になる頻度に制約を付けようとすると・・・それはvar[m0][w]*var[m1][w]という項が出てきてしまい、線形問題じゃなくなるから非線形問題として捉えないとダメなのかな・・・と気付きました。多分非線形計画法(?)で解かないといけないのですよね・・・

    キャンセル

  • 2018/05/30 14:13

    すいません、その辺は全く考慮に入れてません。数学は苦手なので線形計画法もよくわかっていません(昔学校で習ったと思いますが忘れました)。

    キャンセル

  • 2018/05/30 14:18

    でも一次式で表現できる制約である限りはとても簡単に応用できる便利なライブラリーですよね・・・「Aさんはこの日に割り当てられない」といった制約ならとても簡単に思えます。また「BさんとCさんを一緒にしちゃだめ」はvar[m_b][w] + var[m_c][w] < 2と書けるのでこれも簡単にできそうです!

    キャンセル

0

javascriptで書いてみました。
参考まで。

let func2 = ()=>{

  // 前回の選択結果と必ず違う選択結果を返す乱数取得処理
  const choice = (max, prev = -1)=>{
    while(true){
      let next = Math.floor(Math.random() * max);
      if(next != prev) return next;
    }
  };

  let memberList = ['a','b','c','d','e','f','g']; // メンバー一覧
  let count = [0,0,0,0,0,0,0]; // 各メンバーの当番回数

  let candidates = []; // 当番抽出用の配列

  for(let i = 0; i < 53; i++){

    // 処理先頭で抽出用配列のサイズが0ならメンバー一覧から再抽出
    if(candidates.length == 0){
      candidates = memberList.filter(n=>true);
    }
    let c1 = choice(candidates.length);

    // 最初の抽出後、抽出用配列のサイズが1ならメンバー一覧から再抽出する準備
    let isNewCandidates = false;
    if(candidates.length == 1){
      isNewCandidates = true;
      c1 = memberList.indexOf(candidates[c1]);
      candidates = memberList.filter(n=>true);
    }
    let c2 = choice(candidates.length, c1);

    // 当番の出力
    console.log((i+1) + " : " + candidates[c1] + " & " + candidates[c2]);

    // 当番回数の加算
    count[memberList.indexOf(candidates[c1])]++;
    count[memberList.indexOf(candidates[c2])]++;

    // 抽出用配列から今回の抽出結果を削除
    candidates = candidates.filter((n,ind)=>{
      if(!isNewCandidates){
        if(ind == c1) return false;
      }
      if(ind == c2) return false;
      return true;
    });
  }

  memberList.forEach((n,i)=>{ console.log(n + "::" + count[i]);});
};

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/29 17:48

    ご回答頂き、ありがとうございます。
    こんなにも短時間に書いていただいておどろきました!

    しかし、私はPythonを先月本を買って勉強し始めたばかりで、javascriptは全く分かりません。
    これから頂いたものを理解する為にお時間いただければと思います。
    せっかくのご回答を理解できず、大変申し訳ございません。。。

    キャンセル

  • 2018/05/29 17:57

    ポイントは
    ・「前回の選択結果と必ず違う選択結果を返す乱数取得処理」を準備すること
    ・1回の抽出が終わったら「抽出用配列から今回の抽出結果を削除」すること
    ↑これを念頭に置いておけばどの言語でも実装可能なはずです。
    頑張ってください。

    キャンセル

  • 2018/05/29 18:21

    ご回答頂きありがとうございます。

    抽出用の配列とは別に、選択用の配列を用意しておく、ということでしょうか。
    考えて見ます!アドバイスありがとうございました。

    キャンセル

0

週ごとに当番分の人数を選ぶのではなく、人ごとに回数分の当番の週を選べば、同じ週を回数分選べるという処理がありますが、重複したらやり直しなどもなくなると思います。

追記
よく考えたら、同じ週が残れば、同じ問題を抱えてしまいます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/29 18:20

    回答ありがとうございます。
    人を週に割り当てるのではなく、週(1-53)を人に割り当てるということでしょうか。
    確かにそれだと重複は避けられませんね。。。

    ピックアップしたものの中に重複がないようにする、という記述は出来ないでしょうか?

    キャンセル

  • 2018/05/29 18:29

    どっちの割り当てにしても途中の選択時には、重複はなくしたとしても、最後のあまりものが重複してしまう恐れがあります。
    その場合、再選択などしても重複は解消されないので、無限ループになってしまいます。

    キャンセル

  • 2018/05/29 18:40

    同じ週が余らないように、当番の週を順番に割り当てた後、シャッフルするという方法もありますが、組み合わせにパターンがでてくる気がします。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    Python入力

    Python3での入力についての質問です。 もっとスマートな書き方を教えてほしいです。 a = int(input()) b = int(input()) c = int(in

  • 受付中

    ターミナルで実行するのに時間がかかりすぎる

    ターミナルで実行するのに時間がかかりすぎます。 画像圧縮のアルゴリズムを書いています。 N × N ピクセルのグレースケール画像があり各ピクセルの画素値は 0 から 255

  • 解決済

    ランダムフォレストで特徴量の重要度を表示する際のpltで、エラーが発生して苦慮しています。

    ランダムフォレストで特徴量の重要度を表示する際のplotで、エラーが発生して苦慮しています。 競馬データで統計の勉強をしている初心者でございます。 今回のソースコードは以下

  • 解決済

    Pythonのrandomについて

    Pythonのrandomについての質問です。 ディクショナリーの中にある全てのキーをランダムで被り無く、出したいのですがどうすればよいでしょう。 全てのキーは dic

  • 解決済

    Python3 リストのから一致する数字の項数を削除する方法

    問題) 部屋の全体のリストからアンラッキーナンバーを含む数だけ除き、その他を表示する方法 疑問点) アンラッキーナンバーを含む部屋の場合は NO それ以外は YES と出力しま

  • 解決済

    文字列の配列を、重複なしで乱数にするには

     前提・実現したいこと C#とUnityで現在クイズゲームを作っています。クイズの問題を、一度解いたものが出ないように、ランダムで出したいと思っています。  発生している問題・

  • 解決済

    pythonのprint関数におけるエラー

     前提・実現したいこと Word2Vecを使った単語間の類似度算出をしようとしています。 配列に入っている単語それぞれの類似度を算出します。 Word2Vecに関する参考記事

  • 解決済

    pythonでの結果をexcelに出力する方法

    pythonでwebスクレイピングをして、その検索ワードや検索結果をexcelに出力したいと考えています。 excelでの出力の例としてこのような形を構想しています。 で

同じタグがついた質問を見る

  • Python

    6803questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5275questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • トップ
  • Pythonに関する質問
  • Pythonで出来るだけ公平なランダム当番表(重複なし)を作ってみましたが重複が出てしまいます