3

暦月に無作為に 8 日間の休暇をクルーに割り当てます。

無作為に 8 日を選びたいのですが、休日の配分はできるだけ均等にする必要があります。たとえば、8 日間の休日すべてを月の最初の 8 日間に集めるべきではないということです。

例: [1, 5, 8, 14, 18, 24, 27, 30] は適切な分布です。[1,2,3,4,26,27,28,29] は良い分布ではありません。

実際、クルーは 7 日間連続して働くことはできません。7日ごとに、1日の休日が必要です。

すべての日は平等に扱われます。つまり、日曜日自体は休みではありません。クルーは週末も出勤することがあります。

休日は一つ一つ選びたい。一度に 8 つではありません。

これを達成するためにpythonを使用したアルゴリズムをお勧めできますか?

月のすべての日が休日になるとは限りません。

よろしくお願いします

4

5 に答える 5

8

random.sample()シーケンスからランダム セットを取得するために使用します。利用可能な日を一覧表示し、それを.sample()関数に渡します。

import sample
daysoff = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20]

picked = random.sample(daysoff, 8)

上記の例では、月の日を使用しました。リストでは特定の日 (たとえば、日曜日と月の最後の 10 日) が省略され、その母集団から 8 つのランダムな日が選択されます。

于 2012-12-19T19:53:35.157 に答える
3

これがここでの鍵です：

Actually, a crew can't work 7 consecutive days. In every 7 days, there must be 1 day-off.

問題を言い換えると、7日ごとにランダムに2日と言います（または、必要に応じて月を4つの時間に分割します）。そうすれば、均等な配布が保証されます。random.sample()MartijnPietersが提案するように 使用します。

この手法を使用して最初の週から2つの値を生成し、必要に応じて1つずつ順番に生成できます。

編集：

tcaswellが観察したように、10日連続で勤務する場合がまだあります。これに対抗するために、3日ごとに休日を割り当て、10のリストを作成し、7連続日の基準を無効にしない日のサブセットからランダムに2日を削除することができます。

または、とにかく有効なソリューションが得られる可能性が非常に高いため、基準に適合するまで元のアルゴリズムを使用してリストを生成し続けることもできます。ある種の検証関数を作成する必要がありますが、最も長い連続した日数を数えているだけなので、非常に簡単に作成できます。

コード：

2番目のオプションの実装。

import random
from itertools import chain
from itertools import count

def candidate(m):
    ''' Returns 2 days per week, in m days, where m is the length of the month. '''
    weeks = weeksmaker(m)
    return sorted(list(chain(*[random.sample(week, 2) for week in weeks])))

def weeksmaker(m):
    ''' Divides a month up into four weeks, randomly assigning extra days to weeks. '''
    weeks = [range(i, i+7) for i in xrange(1,29,7)]
    for i in range(m - 28):
        weeks[random.randint(1, len(weeks))-1].append(i)
    c = count(1)
    return [[c.next() for day in week] for week in weeks]

def valid(days, c):
    ''' Validity check. Cant work more than c consecutive days. '''
    for i in xrange(1, len(days)):
        if days[i] - days[i-1] > c:
            return False
    else:
        return True

def daysoff(m, n, c):
    ''' In month length m, need n days off, cant work more than c consecutive days. '''
    while True:
        days = candidate(n)
        if valid(days, c):
            return days

>>> for i in range(28, 32):
...     daysoff(i, 8, 7)
... 
[6, 7, 10, 14, 18, 20, 27, 28]
[4, 7, 10, 13, 19, 21, 23, 24]
[2, 4, 9, 13, 15, 20, 25, 27]
[1, 3, 9, 12, 18, 19, 24, 28]
于 2012-12-19T20:36:54.333 に答える
1

合計日数を分割するだけです。

このコードは、必要な休日の数に関係なく、また合計日数に関係なく機能します。

from random import randint
def foo(l, n):
    dist = round(len(l)/n)
    return [randint(l[i*dist], l[(i+1)*dist-1]) for i in range(n)]

In [1]: days = [i for i in range(1,31)]
In [2]: foo(days, 8)
Out[2]: [1, 4, 6, 9, 13, 16, 20, 27]

In [3]: mylist = [i for i in range(500)]
In [4]: foo(mylist, 5)
Out[4]: [80, 147, 250, 346, 448]

丸めでいくつかの問題が発生し、リストのインデックスが範囲外になる可能性があります。

于 2012-12-19T20:42:20.207 に答える
1

これは（私が思うに）@Martijnが行ったことを行い、連続した日を含めないという追加の利点があります（たとえば、8日続けて休みたくない場合）：

#Day selector

import random

Ndays = 8
daysoff = range(1,25)
concurrent_tol = 3

while True:
    cntr = 0
    sample = random.sample(daysoff, Ndays)
    sample.sort()
    for i in range(1,Ndays-1):
        if abs(sample[i]-sample[i-1]) == 1:
            cntr +=1
        if abs(sample[i]-sample[i+1]) == 1:
            cntr +=1

    if cntr<concurrent_tol:
        print "Found a good set of off-days :"
        print sample
        break
    else:
        print "Didn't find a good set, trying again"
        print sample

出力例:

Didn't find a good set, trying again
[3, 4, 5, 6, 7, 8, 9, 11]
Didn't find a good set, trying again
[1, 5, 6, 7, 12, 14, 19, 20]
Didn't find a good set, trying again
[4, 5, 7, 9, 11, 15, 16, 20]
Didn't find a good set, trying again
[3, 4, 6, 7, 12, 13, 14, 23]
Didn't find a good set, trying again
[1, 7, 10, 12, 15, 16, 17, 22]
Didn't find a good set, trying again
[5, 7, 8, 11, 17, 18, 19, 23]
Didn't find a good set, trying again
[3, 8, 11, 12, 13, 15, 17, 21]
Didn't find a good set, trying again
[2, 5, 7, 8, 9, 12, 13, 21]
Found a good set of off-days :
[1, 2, 5, 12, 15, 17, 19, 20]

これには、見栄えが悪いという追加の利点もあります。daysoff で定義されているように、可能な日は 1 ～ 24 であることに注意してください。

于 2012-12-19T22:08:26.333 に答える
0

すべての有効な勤務スケジュールのリストを生成 (および保存) します (力ずくで...それを行う方法は 30C8 しかありません)。後でそのリストから安全かつ迅速に選択できます。

import itertools
import numpy as np
good_lst = []
for days_off in itertools.combinations(range(30),8):
    if np.max(np.diff( (0,) + days_off + (30,))) < 7:
        good_lst.append(days_off)

(そこにいくつかのオフバイワンのバグがあるかもしれません)

これは、まともなマシンで約5分で実行されました。(0, 1, 2, 3, 6, 12, 18, 24) は有効な勤務スケジュールですが、6 勤務日の 4 つのセクションが含まれるため、おそらくさらに剪定を行う必要があります。

于 2012-12-19T21:05:46.643 に答える