4

多くの牧師のスケジュールを作りたいです。条件は次のとおりです。

  1. 毎月、各牧師は別の教会に行かなければなりません。
  2. 牧師は、彼が来たのと同じ教会に行ってはならない
  3. 1年で12の異なる教会に行かなければならない
  4. 13 の教会と 13 人の牧師がいて、どの教会も毎月 1 人の牧師しか受け入れていません。

ランダム (1 から 12) は使用できません。なぜなら、牧師が同じ教会に行く可能性があるからです (彼が同じ教会に行く可能性は 8.3%)。

彼が同じ教会に通う可能性を小さくしたい(3%以下程度)。

4

2 に答える 2

12

あなたの条件では、特定の牧師の次の教会がランダムに選択される必要はありません。教会リストを反復処理できませんか?

つまり、各牧師に0から12までの番号を割り当てます。各教会に 0 ～ 12 の番号を割り当てます。最初の月:

月 0:
牧師-0 --> 教会-0
牧師-1 --> 教会-1
牧師-2 --> 教会-2
...
牧師-n --> 教会-n

翌月、カウンターの 1 つをインクリメントするだけです (ラップアラウンドあり)。

月 1:
牧師-0 --> 教会-1
牧師-1 --> 教会-2
牧師-2 --> 教会-3
...
牧師-n --> 教会-0

次に、残りの月について繰り返します。

月 3:
牧師-0 --> 教会-2
牧師-1 --> 教会-3
牧師-2 --> 教会-4
...牧師
-(n-1) --> 教会-0
牧師-n - -> 教会-1

このすべて (O(n)) には非常に単純なループがあります。わかりにくい場合は、紙の上で n=3 と言ってループを試してみることをお勧めします。

ランダム性が必要な場合は、質問を更新してください。

パックスによる編集

それはO（n）であり、編集に対応するための私の拡張は少なくともO（n ^ 2）だったので、私は自分の答えを削除してこれに賛成票を投じています。

牧師-0 から牧師-N までの値のインデックスをランダムにソートされた牧師の配列にすることで、ランダム性を維持することができます。これにより、このソリューションは少なくとも私のものと同じくらい優れたものになります。

PAX による編集の終了

于 2008-12-01T13:31:34.113 に答える
1

あなたが同じ数の牧師と教会を持っているとすると、これは本当に単純なアルゴリズムです：

  1. 各教会に0から12まで番号を付けます

  2. 要素0〜12を含む配列を作成します。

  3. アレイでクヌースシャッフル（以下を参照）を実行し、ランダムにシャッフルされた教会のリストを作成します。

  4. 各牧師は自分の教会から始めます（牧師が教会を割り当てていない場合は、牧師に0から12までの任意の番号を付け、同じ番号の教会と一致させます）。毎月、すべての牧師はリストの次の教会に移動します。彼らがリストの最後の教会にいる場合、彼らは最初の教会に行きます。

これには、説明が非常に簡単であるという利点があります。各牧師にシャッフルされたリストを提示し、どこから始めればよいかを伝えるだけです。

クヌースシャッフルは（大まかに）これです：

def knuth_shuffle(l):
    for i in range(len(l)):
        j = random.randint(i, len(l))
        l[i], l[j] = l[j], l[i]

各反復で、リスト内の現在のアイテムを、まだ選択されていない要素のみから選択されたランダムな要素と交換していることに注意することが非常に重要です。これにより、可能なシャッフルの数が順列の数と正確に一致する（したがって、すべてが等しい確率になる）、ランダムな要素の交換、または現在の要素をリスト全体の任意の要素と交換することに基づく単純なシャッフルは行わないでください。持っています。

于 2008-12-01T13:49:39.083 に答える