- ベストアンサー
重複せず担当を割り振りたい
人数をX人とします。 担当が同数のX個あります。 これらを「ランダム」に「1人1担当」で「過去に担当したものは重複しない」結果を出すプログラムを検討しています。 何かいいアルゴリズムや方法はないでしょうか? 例:4人(A、B、C、D) 出力結果 担当1:A→B→C→D 担当2:B→D→A→C 担当3:C→A→D→B 担当4:D→C→B→A このような結果を、ランダムで出力したいです。
- kinmokusei001
- お礼率20% (1/5)
- その他([技術者向] コンピューター)
- 回答数5
- ありがとう数4
- みんなの回答 (5)
- 専門家の回答
質問者が選んだベストアンサー
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)!だけあります。 以上で終了です。
その他の回答 (4)
- f272
- ベストアンサー率46% (8017/17135)
https://www.densu.jp/kyoto/20kyotospass.pdf の[5]を参照する。全部で576通りしかないので,それをテーブル化して,ランダムにどれかを選べばよい。
- AsarKingChang
- ベストアンサー率46% (3467/7472)
暇つぶしに、マジで作ってみたのね。 結果、ちょい私では挫折^^ 1 3 2 0 2 1 0 3 3 2 1 -1 例えばここの、最後。。 -1 -1 -1 -1 頭に321なので、選択肢は0しかないが、 上に、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 エラーが出なかったときの、結果(この結果は、満たしてますよね~)
補足
ありがとうございます。 そう、そこなんです。 何度か考えてみましたが、やっぱり最後があわなくなっちゃうんですよね。 なので、何か使えるアルゴリズムはないかなぁと検討している次第です。 同じ轍を踏まないよう、気を付けます。
- AsarKingChang
- ベストアンサー率46% (3467/7472)
あ、ごめん!縦軸もだったのね^ 読み直してて、意味違ってたみたい。すいません。
- AsarKingChang
- ベストアンサー率46% (3467/7472)
簡単です。 初期値をABCDの順で格納します。 それをランダムバブルソートすればいいんです。 言語が不明なので、アルゴリズムとして書いておきます。 for (i=0;i<4;i++) { t=rand()&3; swap(i,t); // i番目とt番目の「中身」が入れ替わるようにコードを書けばOK } 先頭から「どこか」と入れ替え。 このアルゴリズムは、元々あるものをシャッフルしてるので、 同じものが2回出ることはありえず、初期変数以外(A~D以外)が出ることもあり得ません。 これでOKですか?
関連するQ&A
- エクセルで 任意の単語を重複なしで抽出したい
エクセルに入力した単語の行 ※(例えば G行2列から G行101列までの100個) の中から 5つの単語をランダムに出力したい ※(例えば A2 B2 C2 D2 E2 へ) ・ここで おなじ列の中では 単語の重複を避けたい ・出力は A2 B2 C2 D2 E2 、 A3 B3 C3 D3 E3、、、、、、、、、、 と、任意の量にふやしたい エクセルにまだ詳しくないので、少し優しめに解答もらえると嬉しいです よろしくお願いします
- 締切済み
- 経営情報システム
- 乱数について
今、あるデータの順番をばらばらにするプログラムを作ろうとしています。 たとえば、a,b,c,dとあったら、d,b,c,aとするように、この時考えられるプログラムは、データの数だけ配列を用意して、乱数で、どのデータを出力させるかを決定し、出力し終わったら、その配列のところに印を立てて、次にくるデータに対して、2重にならないように順次、出力していく方法が考えられるのですが。。。 膨大なデータをこのように、すると、二重になる確立が出力するたびに、高くなっていって、なかなか終わらなくなってしまいます。 そこで、残ったデータから、ランダムに選び出すアルゴリズムまたは、関数はないでしょうか?よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 重複エラーを出したい
Excelで重複エラーを出したくて、 A列はリスト、B列は任意に値を入力出来るようにし、 C列で「=A3&B3」として、結合しています。 そこで、C列で同じ値となった場合、重複エラーを出したいのですが、 COUNTIFを使用して「=COUNTIF(C:C,C3)=1」としても、重複エラーが出力されません。 「=A3&B3」の値をC列の数式内に引き継いでエラー出力させるには、 どのようにすればいいのでしょうか。 よろしくおねがいいたします。
- 締切済み
- Excel(エクセル)
- エクセル 重複調べる
エクセルの重複を調べる方法について何ですが、 a1,b1,c1に文字列が入っているのですが、 a1~c1の中に重複しているものが一つあったら(a1とc1が同じ、もしくはa1とb1が同じ、b1とc1が同じ)d1に1と表示して、重複無しだったら0と表示する関数はありますか?
- 締切済み
- オフィス系ソフト
- ACCESSのフィールドのデータを無重複に抽出する
お世話になります。 ACCESS2000を使用しています初心者です。 あるフィールドに入力されているデータを無重複に抽出したいのですが、簡単で良い方法を教えて下さい。 エクセルでの無重複抽出はできるのですが、データ数が34万件くらいあり、推測される結果は2万件くらいになります。 例) 商品 A B C A B D C 結果 A B C D よろしくお願いします。
- ベストアンサー
- オフィス系ソフト
- Perlでハッシュや配列で重複するキーについて
ハッシュで重複するキーが値となるので、このハッシュはabdの3つのキーしか存在しないということでしょうか? %a = ('a'=>1, 'b'=>2, 'a'=>3, 'd'=>4); また、配列の場合はabadと4つ数になるということでしょうか? @a = ('a','b','a','d'); この場合配列で、重複する値を抽出するアルゴリズムが知りたいです。
- ベストアンサー
- Perl
- EXCELで重複する値の検索
EXCELで重複する値を検索して、かつその重複した値と同じ行の隣のセルの値を返すということをしたいのですが、どうすればうまくいきますでしょうか。 具体的には下記のようになります。 A B C 1 りんご A市場 2 みかん C市場 3 りんご D市場 4 なし B市場 5 バナナ A市場 6 りんご F市場 上のような表があったとして、A列の重複を検索(この場合はりんごが重複)して、重複した場合はB列の値をC列に返すことをしたいんです。 希望する出力は以下のような形です。 A B C 1 りんご A市場 D市場、F市場 2 みかん C市場 3 りんご D市場 A市場、F市場 4 なし B市場 5 バナナ A市場 6 りんご F市場 A市場、D市場 よろしくお願いします。
- ベストアンサー
- オフィス系ソフト
お礼
ありがとうございます! 試しにこの数式から調べてみたいと思います。