重複せず担当を割り振りたい

質問

人数をX人とします。
担当が同数のX個あります。
これらを「ランダム」に「1人1担当」で「過去に担当したものは重複しない」結果を出すプログラムを検討しています。
何かいいアルゴリズムや方法はないでしょうか？
例：4人（A、B、C、D）
出力結果
担当１：A→B→C→D
担当２：B→D→A→C
担当３：C→A→D→B
担当４：D→C→B→A
このような結果を、ランダムで出力したいです。

回答No.5

f272 · ベストアンサー

4の場合だけでなく，一般のnの場合については，最終的には作りながら条件を満たしているかどうかをチェックしていくことになる。
まず完全順列(p(j)≠j (1≦j≦n)を満たす順列)を作成しておく。ここでも作成しながら条件を満たすかどうかをチェックする。全部でa(n)=n!*Σ((-1)^k/k!)個あります。k=0からnまでの和です。
そしてPk = {{p(j)} | p(1) = k} (2≦k≦n)を満たすように分類する。

まず1行目は1 2 3 4で固定する。
k行目はPkから選ぶようにして条件をチェックする。このときPkの作り方から1行目とは絶対に重複しないので2行目以降とだけチェックを行えばよい。
n行目まで行ったら標準形は完成です。n=4の場合は標準形は4個あります。非標準形は2行目からn行目までをランダムに入れ替えて，さらに1列目からn列目までをランダムに入れ替えます。入れ替えの数はn!*(n-1)!だけあります。
以上で終了です。

お礼

ありがとうございます！
試しにこの数式から調べてみたいと思います。

回答No.4

f272

https://www.densu.jp/kyoto/20kyotospass.pdf
の[5]を参照する。全部で576通りしかないので，それをテーブル化して，ランダムにどれかを選べばよい。

回答No.3

AsarKingChang

暇つぶしに、マジで作ってみたのね。
結果、ちょい私では挫折＾＾
1 3 2 0
2 1 0 3
3 2 1 -1 　例えばここの、最後。。
-1 -1 -1 -1

頭に３２１なので、選択肢は０しかないが、
上に、03があるので、0が選べない！と、
エラーはいて止まっちゃいました＾＾

ひとまず、「動かなかった使えないアルゴリズム」は
書いておきます。同じことをして、時間を無駄にしないように、、
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33

なので、たとえば「22」の位置なら、
20 21 それに、02 12 で使っていない物を探させたのですが。
ダメでした（あははは）
ただ、エラー吐いた事を検出はできるので「やり直し」で
答えが出るまで？なら、確かに満たしたんですが＾＾。

2 0 1 3
3 2 0 1
1 3 2 0
0 1 3 2
エラーが出なかったときの、結果（この結果は、満たしてますよね～）

補足

ありがとうございます。
そう、そこなんです。
何度か考えてみましたが、やっぱり最後があわなくなっちゃうんですよね。
なので、何か使えるアルゴリズムはないかなぁと検討している次第です。
同じ轍を踏まないよう、気を付けます。

回答No.2

AsarKingChang

あ、ごめん！縦軸もだったのね＾
読み直してて、意味違ってたみたい。すいません。

回答No.1

AsarKingChang

簡単です。
初期値をABCDの順で格納します。
それをランダムバブルソートすればいいんです。
言語が不明なので、アルゴリズムとして書いておきます。

for (i=0;i<4;i++) {
t=rand()&3;
swap(i,t); // i番目とt番目の「中身」が入れ替わるようにコードを書けばOK
}

先頭から「どこか」と入れ替え。
このアルゴリズムは、元々あるものをシャッフルしてるので、
同じものが２回出ることはありえず、初期変数以外（A~D以外）が出ることもあり得ません。

これでOKですか？