- 締切済み
N個の整数の並び替えるアルゴリズム
N個の整数1,2,3,...Nから任意のM個(M < N )を取り出すのですが、重複はダメという場合、どのようなアルゴリズムがあるでしょうか。重複ありなら、Nまでの一様乱数を発生させて整数化して取り出すことは可能です。今回は重複なしです。重複があったらやり直して重複なしになるまでやり続けるというのはダメだなと思っています。 データ処理言語のRはコマンド1つのようですが。言語はFortranなのですが、アルゴリズムのレベルだとどれでも同じと考えています。よろしくお願いします。
- skmsk1941093
- お礼率52% (611/1161)
- C・C++・C#
- 回答数4
- ありがとう数3
- みんなの回答 (4)
- 専門家の回答
みんなの回答
- pooh26
- ベストアンサー率48% (63/130)
f272さんが紹介しているのは、Fisher–Yates shuffle ですね。 Wikipediaにもありますが、実装さえ間違えなければ大丈夫です。
- f272
- ベストアンサー率46% (8009/17117)
乱数発生が完全に一様であれば,このアルゴリズムですべての場合が等確率で出てきますから,これ以上よけいなことをする必要はありません。
お礼
回答ありがとうございます。すでに実績のある標準アルゴリズムということですね。これをサブルーチン化して外部から呼び込めるようにしたいと思います。
- f272
- ベストアンサー率46% (8009/17117)
こんな感じ? program test implicit none integer,parameter :: n=10 integer,parameter :: m=5 integer :: t, i, j integer,dimension(n) :: ar=(/(i,i=1,n)/) real :: rnd(n) call random_number(rnd) do i=n,2,-1 j=int(rnd(i)*i)+1 t=ar(i) ar(i)=ar(j) ar(j)=t enddo print*,(ar(i),i=1,m) end program test
お礼
回答ありがとうございます。このアルゴリズムは乱数に基づいた交換というシャッフルをカードの枚数回、しかもすべてのカードが必ずシャッフルの対象となるようにすればそのカードの先頭から順番に抜き出せば重複のないランダムな取り出しになっているということですね。 この場合、最初が順番どおりになっているので初期の影響が完全に消えるということをするため、再度シャッフル(2枚の交換)をした方がいいというようなことはないでしょうか。どこまでやると最初の条件の影響が消えていくのだろうと思いますが。案外すぐに消えるものでしょうか。
- m5048172715
- ベストアンサー率16% (860/5258)
ざっと、 今取り出した物aを、 既に取り出した物bと比較して、 a=bのとき、aを破棄する。 を、bがm個になるまで繰り返す。
関連するQ&A
- 0 からa-1 までの整数の乱数をn 個発生させ、発生した整数のヒスト
0 からa-1 までの整数の乱数をn 個発生させ、発生した整数のヒストグラムをプリントアウトしたいです.また,a とnはコマンドラインから引き渡します 0 からa-1 までの整数を発生する乱数の書き方は (int)((double)rand()/((double)RAND_MAX+1) *a); プログラムをRandHist としたとき RnadHist 10 1000 と入力すれば 0 982 1 1035 2 956 3 1102 ・ ・ 9 971 などと。出力されるようなプログラムを作る問題ですが,a とn は、任意に変えられるように したいです. どなたか教えてください.
- 締切済み
- C・C++・C#
- 1~Nの中から、任意にM個の数を返す関数
PHP初心者です。 PHPのソースを眺めていて、 mt_rand(1、N) とあり、それが、1~Nの中から、任意に一つ選び出す(乱数を発生させる)関数 ということは理解できました。 そこで、1~Nの数から、任意にM個選び出す(乱数を発生させる)関数を考えています。 そんな関数がドンピシャリあれば、話が早いんですが、 あいにく、知りません。。 例えば、N=10、M=3だとすれば、 7、4、9 などの数を得たいと思っています。 (重複はせずに) 何か、いい方法はありませんでしょうか。 ご存知の方、よろしくお願いいたします!
- 締切済み
- PHP
- N個の一様乱数[0,1]の平均の分布
N個の一様乱数(例えば[0,1])の平均はどのような確率分布になりますでしょうか。 また、一様乱数の平均を、適当な処理をして同じ区間で一様にできないものでしょうか。 何卒よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 偏りのある乱数のアルゴリズム
偏りのある乱数のアルゴリズムを教えてください。 ただし、中心極限定理などに見られるような「中心にのみ偏る」乱数ではなく、「任意の位置を中心に偏る」乱数です。 例えば、範囲を0<N<1、任意の位置を0.75とした場合の分布を見ると、0.75がカーブの頂点となります。 ビットマップ上にプロットすると、部分的に固まるように見えれば理想的です。 言語・精度・速度不問。できればPHPでお願いします。
- ベストアンサー
- その他(プログラミング・開発)
- m個の数字をn個のグループに分けるとき、
m個の数字をn個のグループに分けるとき、 各グループの和s(i) ,(1<=i<=n) が、指定した比 r(0):r(1): ・・・ :r(n-1):r(n) ( = s(0):s(1): ・・・ :s(n-1):s(n) ) に一番近くなるようなグループ分けを導けるアルゴリズムはありますか。 例えば、{1, 3, 4, 6}を和の比が1:2に一番近くなるように2つのグループに分けると、 {1, 4}, {3, 6} となります。(もし違ってたら指摘してください) アルゴリズムでなくても、こうしたら良いんじゃないか、という考えがありましたら 教えてください。 総当たりで調べる場合はどのようにすれば、効率良く調べられるかという点もお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 整数の選択
アルゴリズムに関する質問です. n個の相異なる整数が配列 A[1..n] に格納されていて,その配列の中からk番目に小さい整数を選ぶ問題のアルゴリズムを考えています.kは 1<=k<=n を満たす自然数であり,この選択問題は O(n) で解けるものです. ヒープを使ったりして考えたのですがうまくいきません.どなたかこのアルゴリズムを教えてください.よろしくお願いします.
- ベストアンサー
- その他(プログラミング・開発)
- 偏りのある乱数のアルゴリズム
偏りのある乱数のアルゴリズム(コード)を教えてください。 ただし、中心極限定理などに見られるような「中心にのみ偏る」乱数ではなく、「任意の位置を中心に偏る」乱数です。例えば、範囲を0.0<1.0、任意の位置を0.75とした場合の分布グラフを見ると、0.75がカーブの頂点となります。 また一方で、複数の偏りが見られる乱数のアルゴリズムも知りたいです。カーブが心電図のように複数見られる乱数です。ビットマップ上にプロットすると、部分的に点の集合が形成されるようなものが理想的です。 ※プログラミング言語・精度・速度は不問。本人数学に関しては素人です。
- ベストアンサー
- 数学・算数
- C++でのアルゴリズム
次の条件を満たすアルゴリズムをC++のコードで教えてください! 大きさ2×1の長方形n個を 縦2 横n の長方形になるように並べるときの並べ方の総数を求めるアルゴリズム 入力nは、1以上の整数が入力される前提でよい。 例として、 n=1 1通り n=2 2通り n=3 3通り n=5 8通り n=7 21通り となります お願いします。
- ベストアンサー
- C・C++・C#
- (1)m>n≧1を満たす整数m,nに対して次式が成り立つことを証明せよ
(1)m>n≧1を満たす整数m,nに対して次式が成り立つことを証明せよ (nCn)+(n+1Cn)+(n+2Cn)+……(mCn)=(m+1Cn+1) (2)2n個の整数 1,2,3,……2n-1,2n を無作為にn個ずつの集合に分けると、一方の集合に含まれる最大値は 2n である。もう一方の集合に含まれる最大値をXとして、Xの期待値を求めよ。 教えてくださいお願いします
- 締切済み
- 数学・算数
- ”部分分数分解(m/nのm,nは整数)のアルゴリズム化の方針を示せ。”
”部分分数分解(m/nのm,nは整数)のアルゴリズム化の方針を示せ。”です。 内容は情報ではなく数学なので、ここで質問をさせていただきます。 m/n * x/x = mx/nx mx/nx = (mx-n)/nx + n/nx = (mx-n)/nx + 1/x ただし、mx-n>0, mx>n ∴mx/nx = m/nより m/n = mx/nx = (mx-n)/nx + 1/x , ただし、mx>nとなるxを定める必要がある。 x={n(分母)/m(分子)の小数点以下切り捨て}+1であれば常にmx>nは満たされる。 あとは再帰的にm ← mx-n (次の分子をmx-nに更新), n ← nx (次の分母をnxに更新) でループ処理をして最新の分子が1の時にブレイクすれば処理完了。 というプログラム化の方針でどうでしょうか? プログラムの作成より、方向性を示せと言われる方が細部の説明において難しいですね…orz
- ベストアンサー
- 数学・算数
お礼
回答ありがとうございました。標準のアルゴリズムのようですね。 たぶん、python, Rなどのライブラリは間違いのないものが実装されていてそのような個別パーツは自分で考えて作り出すのではなく、出来上がっている間違いのないものを使うべきだということではないかと思います。Fortranにもそういうライブラリ集があるのでしょうか。大昔からテキストに載っているようなものの以外にですが。