3

クラスの生徒にランダムな論文を割り当てる必要がありますが、次のような制約があります。

  1. 各学生は2つの論文を割り当てる必要があります。
  2. 各論文は（ほぼ）同数の学生に割り当てられる必要があります。

このプロパティを持つ行列を生成するエレガントな方法はありますか？つまり、シャッフルされますが、行と列の合計は一定ですか？例として：

Student A   1  0  0  1  1  0 |  3
Student B   1  0  1  0  0  1 |  3
Student C   0  1  1  0  1  0 |  3
Student D   0  1  0  1  0  1 |  3
            ---------------- 
            2  2  2  2  2  2

最初に正しい行/列の合計で「初期行列」を作成し、次に最初に行、次に列をランダムに並べ替えることを考えましたが、この初期行列を生成するにはどうすればよいですか？ここでの問題は、（たとえば）次の選択肢から選択することです。同じペアの論文が割り当てられている2人の学生がいるという事実（左側の設定）は、行/列のシャッフルによって変更されません。

INITIAL (MA):            OR (MB):
A   1  1  1  0  0  0  ||  1  1  1  0  0  0  
B   1  1  1  0  0  0  ||  0  1  1  1  0  0
C   0  0  0  1  1  1  ||  0  0  0  1  1  1
D   0  0  0  1  1  1  ||  1  0  0  0  1  1

私は何か迅速で汚いものを思い付くことができ、必要に応じて微調整することができることを知っていますが、それは楽しい運動のように思えました。

4

2 に答える 2

1

次のように初期行列を生成できます（疑似Python構文）。

column_sum = [0] * n_students

for i in range(n_students):
    if column_sum[i] < max_allowed:
        for j in range(i + 1, n_students):
            if column_sum[j] < max_allowed:
                generate_row_with_ones_at(i, j)
                column_sum[i] += 1
                column_sum[j] += 1

                if n_rows == n_wanted:
                    return

これは、 n個の2つの異なる行を選択するすべての単純な反復ですが、列の合計に対する制約ができるだけ早く適用されます。

于 2013-01-30T16:39:10.820 に答える
1

順列を作成したい場合は、どうでしょうか。

  • 学生をランダムに選択しました。たとえば、学生1

  • この学生のために、彼が持っているランダムな紙、たとえば紙Aを選びました

  • 別の学生をランダムに選んだ

  • この学生のために、彼が持っているランダムな紙、たとえば紙B（Aとは異なる）を選びました

  • 紙Bを生徒1に、紙Aを生徒2に渡します。

そうすれば、異なる論文の数と学生ごとの論文の数の両方を保持できます。確かに、両方の学生は1つの論文を与え、1つを返します。また、紙の作成や削除はありません。

表では、A（i1、j1）= 1、A（i2、j2）= 1、A（i1、j2）=となるようなインデックス（i1、i2）と（j1、j2）の2つのペアを見つけることを意味します。 0およびA（i2、j1）= 0であり、0を1に、1を0に変更=>行と列の合計は変更されません。

備考1：順列を進めたくない場合は、すべての紙をベクトルに入れるだけです（紙Aを2倍、紙Bを2倍、...）。次に、ベクトルをランダムにシャッフルし、最初にkを最初の生徒に、次のkを生徒2に割り当てます...ただし、同じ紙を数回持っている生徒で終了することもできます。この場合、追加の論文から始めていくつかの順列を作成します。

于 2013-01-30T20:09:06.150 に答える