C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[15]: 0から9までをシャッフルする


(過去ログ 125 を表示中)

[トピック内 21 記事 (1 - 20 表示)]  << 0 | 1 >>

■74460 / inTopicNo.1)  0から9までをシャッフルする
  
□投稿者/ マリオ (1回)-(2015/01/05(Mon) 12:09:42)

分類:[C#] 

C# で 0 から 9 の数字が入っている配列をシャッフルするコードを書いてください。
配列のサイズは 10 で全て異なる数値です。0 から 9 が順番に入っている配列になります。
ただし、配列のシャッフルではそれぞれの数値が出力される確率に偏りがあってはいけません。

この回答がどうしてもわかりません、どうすればいいですか?
引用返信 編集キー/
■74461 / inTopicNo.2)  Re[1]: 0から9までをシャッフルする
□投稿者/ shu (654回)-(2015/01/05(Mon) 12:16:27)
No74460 (マリオ さん) に返信

//--- 元の配列
int[] cards = (Enumerable.Range(0, 10)).ToArray();
//--- 乱数発生用
Random rnd = new Random();
//--- シャッフルして新しい配列に格納
int[] cards2 = cards.OrderBy((r) => rnd.Next(100)).ToArray();

引用返信 編集キー/
■74463 / inTopicNo.3)  Re[2]: 0から9までをシャッフルする
□投稿者/ マリオ (4回)-(2015/01/05(Mon) 12:49:51)
確率に偏りがあってはいけません。
100回シャッフルした場合、均等に分配されるようにしたいんですが・・・

引用返信 編集キー/
■74464 / inTopicNo.4)  Re[2]: 0から9までをシャッフルする
□投稿者/ なちゃ (12回)-(2015/01/05(Mon) 12:51:57)
No74461 (shu さん) に返信
> ■No74460 (マリオ さん) に返信
>
> //--- 元の配列
> int[] cards = (Enumerable.Range(0, 10)).ToArray();
> //--- 乱数発生用
> Random rnd = new Random();
> //--- シャッフルして新しい配列に格納
> int[] cards2 = cards.OrderBy((r) => rnd.Next(100)).ToArray();
>

こういうやり方は基本的にダメです。
偏りがない保証はないし、というかたぶん偏りができるし、まともに動く保証もありません。

シャッフルは定石がありますので、探せば出てくると思いますが。
引用返信 編集キー/
■74465 / inTopicNo.5)  Re[3]: 0から9までをシャッフルする
□投稿者/ なちゃ (13回)-(2015/01/05(Mon) 13:09:07)

> こういうやり方は基本的にダメです。
> 偏りがない保証はないし、というかたぶん偏りができるし、まともに動く保証もありません。

すみません、ちょっと訂正です。
まともに動く保証がないとかは、ちょっと別のやり方との勘違いです。
偏りについては、この方法の場合どうなるんだろう…
ちょっと判断できないですね…条件ができてしまうので完全ではないと思いますが…

#繰り返した時に同じ結果になるとかであれば、シードの調整やRandomの初期化を毎回行わないなどで防げます>元質問者さん
引用返信 編集キー/
■74466 / inTopicNo.6)  Re[3]: 0から9までをシャッフルする
□投稿者/ shu (655回)-(2015/01/05(Mon) 13:18:30)
No74460 (マリオ さん) に返信
> 確率に偏りがあってはいけません。
用意されている乱数を使ってはダメという事でしょうか?
だとすると乱数発生処理部分は自作するとよいかと思います。


No74464 (なちゃ さん) に返信
> まともに動く保証もありません。
まともに動かないとはどういうことでしょうか?
無限ループになったりスタックオーバーフローを起こしたりする
コードでないことは間違いないです。



提示したコードの意味を考えてみて下さい。乱数の発生が一様であれば
配列の再作成を除き要件に合うはずです。提示したコードはそのまま課題提出しない
と思いますので参考程度にとらえて下さい。

引用返信 編集キー/
■74467 / inTopicNo.7)  Re[4]: 0から9までをシャッフルする
□投稿者/ なちゃ (14回)-(2015/01/05(Mon) 13:32:29)
まともに動かないは、上に書きましたが別の方法との勘違いです。申し訳ない。

気になるのは偏りで、例えば乱数を100にしてますが、その根拠はなんでしょう?
元の配列の10倍丁度だから偏らない?
今回は10しかないでしょうけど、10以外だと偏る可能性がある気がしますので、100にするくらいなら生データから調整しない方がいいかもしれません。

個人的には、定石的なアルゴリズムになっている、
以下のような方法(以前ここでも出てきたもの)
for ( i = 0; i < N; ++i )
{
int value = i以上N未満の乱数。
i 番目と value 番目を交換
}
がいいと思ったりします。

引用返信 編集キー/
■74468 / inTopicNo.8)  Re[5]: 0から9までをシャッフルする
□投稿者/ shu (656回)-(2015/01/05(Mon) 13:36:39)
No74467 (なちゃ さん) に返信

> がいいと思ったりします。
>
なんかの課題だと思ったので直接その答えは避けました。
引用返信 編集キー/
■74469 / inTopicNo.9)  Re[5]: 0から9までをシャッフルする
□投稿者/ なちゃ (15回)-(2015/01/05(Mon) 13:38:57)

> 気になるのは偏りで、例えば乱数を100にしてますが、その根拠はなんでしょう?
> 元の配列の10倍丁度だから偏らない?
> 今回は10しかないでしょうけど、10以外だと偏る可能性がある気がしますので、100にするくらいなら生データから調整しない方がいいかもしれません。

うーん、丁度10倍でも一様にならない(あまり関係ない)気もしてきた…
100では少なすぎる気がしますね…
やっぱり生データのままくらいの方がいい気がします。
引用返信 編集キー/
■74470 / inTopicNo.10)  Re[5]: 0から9までをシャッフルする
□投稿者/ shu (657回)-(2015/01/05(Mon) 13:44:39)
No74467 (なちゃ さん) に返信

> 気になるのは偏りで、例えば乱数を100にしてますが、その根拠はなんでしょう?
> 元の配列の10倍丁度だから偏らない?
> 今回は10しかないでしょうけど、10以外だと偏る可能性がある気がしますので、100にするくらいなら生データから調整しない方がいいかもしれません。
乱数が一様であれば10でも100でも1000でもいいのですが
出来るだけ同じ数字にならないほうがソート時の揺れが減るかなと考えました。
10未満だと確実に同じ数が発生するのでソート処理による揺れが発生してしまい乱数に影響が大きいと考えました。



引用返信 編集キー/
■74472 / inTopicNo.11)  Re[3]: 0から9までをシャッフルする
□投稿者/ shu (658回)-(2015/01/05(Mon) 14:24:37)
No74463 (マリオ さん) に返信

> 100回シャッフルした場合、均等に分配されるようにしたいんですが・・・
10*10のint配列cnt[,]を作成し0で初期化
シャッフルした配列のn番目にmが入っているとき
cnt[n,m]を1増やす。
この操作前にcnt[n,m]が10であったらn番目にmが入るのを避け
cnt[n2,m]<10のところと数値を交換
のような動きにしていけばなんとかなると思います。
引用返信 編集キー/
■74473 / inTopicNo.12)  Re[6]: 0から9までをシャッフルする
□投稿者/ なちゃ (17回)-(2015/01/05(Mon) 14:59:57)
No74470 (shu さん) に返信
> ■No74467 (なちゃ さん) に返信
>
>>気になるのは偏りで、例えば乱数を100にしてますが、その根拠はなんでしょう?
>>元の配列の10倍丁度だから偏らない?
>>今回は10しかないでしょうけど、10以外だと偏る可能性がある気がしますので、100にするくらいなら生データから調整しない方がいいかもしれません。
> 乱数が一様であれば10でも100でも1000でもいいのですが
> 出来るだけ同じ数字にならないほうがソート時の揺れが減るかなと考えました。
> 10未満だと確実に同じ数が発生するのでソート処理による揺れが発生してしまい乱数に影響が大きいと考えました。

まあ、そんな感じですよね。
10未満や10程度だと、同じ数字が出て何かしら影響がありそうだというのは直感的な物だと思うのですが、実際には、例えば100の場合でも、4割くらいの確率で同じ数値が出るわけです。
#こういうのバースデーパラドックスとか言いますね、別にパラドックスじゃないけど

で同じ数字が出るとどの程度まずいかですが、例えばOrderByは安定ソートなので、同じ数値になると必ず元の順のままになるわけで、本来乱数が持っていた順序が消えて固定順になってしまいます。
この辺りが、やっぱり多少の偏りになる気がして、100とかにするのはまずいような気がしたわけですね。

まあ、ホントのところどの程度影響があるかは分かりませんが。


引用返信 編集キー/
■74478 / inTopicNo.13)  Re[7]: 0から9までをシャッフルする
□投稿者/ shu (659回)-(2015/01/05(Mon) 16:41:33)
No74473 (なちゃ さん) に返信

偏りを検証

            //--- 乱数発生用
            Random rnd = new Random();
            //--- 元の配列
            int[] cards = (Enumerable.Range(0, 10)).ToArray();
            
            int[,] cnt = new int[10, 10];
            Array.Clear(cnt,0,cnt.Length);
            for (int i = 0; i < 100; i++)
            {
                //--- シャッフルして新しい配列に格納
                int[] cards2 = cards.OrderBy((r) => rnd.Next(100)).ToArray();
                //--- 各数字の場所をカウント
                for (int j = 0; j < cards2.Length; j++)
                {
                    cnt[cards2[j], j]++;
                }
            }

            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    Console.Write("{0}  ", cnt[i, j].ToString().PadLeft(4,' '));
                }
                Console.WriteLine();
            }
            Console.WriteLine();


結果:3回実行してみました。これが偏りとみるかは難しいところですが
   気になるようなら前述のように10になったところでその場所でないところへ
   移動するよう補正するとよいかと。
1回目:
   7     6    14     9    10    10    13    11    12     8  
  12     8     6    14     8    12     7    10    12    11  
  10     9     7    12    12    10    11     8    13     8  
  10     9    10     9     8     9    10    14    12     9  
  11    16    10    13     8    13     6     7     7     9  
   6    14    13     6    10     4    17     8    12    10  
  14     9    16     8    11     6    10    12     3    11  
  11    10    10     8    10    12     7    11     8    13  
   9     9     5    12    10    16     7     8    13    11  
  10    10     9     9    13     8    12    11     8    10  

2回目:
   7     6    10     6    15    14    12    12    12     6  
  17    14     6     6    11     8     9    11     6    12  
   7     7    15    10     9    10     8    13     4    17  
  12     7    14    18     4     8    11     6    12     8  
  12     5    13     6    16     9    11     7     8    13  
   6    13     9    14     5     9    13    16     9     6  
   6     9    12    11    12    13     3    10    12    12  
  16    11     6    11     5    13     8     9    14     7  
   8    17     6     6    10     8    14     9    11    11  
   9    11     9    12    13     8    11     7    12     8  

3回目:
  12     6     9     7     8    10    18    13     7    10  
   7     9    14    14     8    12     9     9     9     9  
  12     6     8    18    11    10     6     9    11     9  
   7     7     6     9     9    10    14    12    16    10  
  13     9    14    12    10    12     9     9     7     5  
  14     9     9     6    14     9     8     5     8    18  
  11     7    10     7    10    12     7    14     9    13  
   7    14    13     9     7     9    11     9    11    10  
   8    13     8    11    10     9    10    10    11    10  
   9    20     9     7    13     7     8    10    11     6  

引用返信 編集キー/
■74479 / inTopicNo.14)  Re[8]: 0から9までをシャッフルする
□投稿者/ shu (660回)-(2015/01/05(Mon) 17:01:57)
2015/01/05(Mon) 17:08:57 編集(投稿者)
2015/01/05(Mon) 17:02:11 編集(投稿者)

■No74478 (shu さん) に返信

ついでにループ回数10000にした結果

1015  1048   989   976   981  1015  1012  1016   952   996  
1007   959  1041   973  1022  1045   957  1014   983   999  
 992  1040  1001   983  1005   919   988  1007  1046  1019  
1015   978  1044   998  1005  1019  1019   970   971   981  
1013   984   954  1008   995  1031  1019  1010  1032   954  
 989  1000   945  1015  1017  1031   966   985  1066   986  
 979  1006  1015  1042   962   985  1043   978   971  1019  
1036   975  1022   958  1016   986  1043  1005   951  1008  
 964  1043   963  1039   966   970   984  1016  1020  1035  
 990   967  1026  1008  1031   999   969   999  1008  1003  



ループ回数10000、rnd.Next(10)にした結果:
※1000からかけ離れた回数が発生してしまっている。
1510   915   992   967  1031  1008  1000  1048   928   601  
1425  1007   990   986   994  1007   966  1013   985   627  
1217  1054  1021  1020   952  1040  1011   999   975   711  
1103  1039   919  1023  1028  1061  1014   983  1019   811  
 994  1080  1017   983   992  1006   962  1019  1072   875  
 909  1028  1043  1028   999   948  1040   961  1052   992  
 813   966  1036  1032   998   990  1022  1005  1005  1133  
 770  1011   961  1020  1027   935  1011   972  1011  1282  
 657  1006   993   968   985   988  1002  1015  1006  1380  
 602   894  1028   973   994  1017   972   985   947  1588  


引用返信 編集キー/
■74480 / inTopicNo.15)  Re[9]: 0から9までをシャッフルする
□投稿者/ なちゃ (18回)-(2015/01/05(Mon) 17:14:27)
100000回くらいのシャッフルを何回か繰り返してみると、意外とはっきり偏ってるのが分かります。
この頻度表でいうと、左下の方は少なくなります。
何回実行しても同様。
一方、定石的なシャッフルの方では、少なくとも100000回でははっきりした偏りは見られません。
引用返信 編集キー/
■74481 / inTopicNo.16)  Re[10]: 0から9までをシャッフルする
□投稿者/ shu (661回)-(2015/01/05(Mon) 17:41:16)
No74480 (なちゃ さん) に返信
> 100000回くらいのシャッフルを何回か繰り返してみると、意外とはっきり偏ってるのが分かります。
> この頻度表でいうと、左下の方は少なくなります。
> 何回実行しても同様。
> 一方、定石的なシャッフルの方では、少なくとも100000回でははっきりした偏りは見られません。
分かりました。とりあえず私の提示コードはそのままでは偏りの要件を満たさないということにします。
ただ私の言いたいのは乱数を使って何らかのソートをすることでシャッフルが出来るということであり
偏りが気になるなら補正して下さいということです。
引用返信 編集キー/
■74482 / inTopicNo.17)  Re[11]: 0から9までをシャッフルする
□投稿者/ なちゃ (19回)-(2015/01/05(Mon) 18:04:38)
ちょっと語弊があったかもしれないので。
ランダムキーでソートする方法自体は別に有りだと思います。
乱数を100にしているせいで偏りが出るのが問題で、単にrnd.Next()ならまず問題ありません。
補正する方法は

色々細かいこと言ったり試したりしてるのは、単に面白く興味深かったから、というだけです。
#実際偏りが出るのか、どんな出方するのかなどに興味がわいただけ

ただし、補正する方法はお勧めしません。
というか、きちんと補正する方法が思いつきません。
無理に補正しても多分別の特徴で偏りが出てしまうでしょう。

補正するくらいなら、単に上限を指定しない乱数にするだけの方がいいです。

ちなみに乱数を1000にすると、偏りはかなりなくなりますが、1000000回くらいシャッフルしてみるとやっぱり少し偏っているのが分かります。
#乱数が1000の場合、同じ数値が出る確率は5%くらいになります。

あ、別に実用上はこの程度の偏りは問題ないという事ももちろんあります。
単に理論上などの話であって、この辺も面白いから色々試してみただけです。
引用返信 編集キー/
■74483 / inTopicNo.18)  Re[12]: 0から9までをシャッフルする
□投稿者/ なちゃ (20回)-(2015/01/05(Mon) 18:12:22)
ちなみに偏る原因ですが、乱数の上限を上げると偏りは減ること、またその減り方の傾向と、
頻度表で左下や右上が少なくなる→元の順がわずかに残りやすい傾向にあること、
などから、やっぱりおそらく同一の値が出てしまうことで、安定ソートによる元の順序の保持がわずかに影響を与えるのだろうと思われます。
引用返信 編集キー/
■74485 / inTopicNo.19)  Re[13]: 0から9までをシャッフルする
□投稿者/ マリオ (5回)-(2015/01/05(Mon) 19:03:25)
No74483 (なちゃ さん) に返信
> ちなみに偏る原因ですが、乱数の上限を上げると偏りは減ること、またその減り方の傾向と、
> 頻度表で左下や右上が少なくなる→元の順がわずかに残りやすい傾向にあること、
> などから、やっぱりおそらく同一の値が出てしまうことで、安定ソートによる元の順序の保持がわずかに影響を与えるのだろうと思われます。
解決済み
引用返信 編集キー/
■74486 / inTopicNo.20)  Re[14]: 0から9までをシャッフルする
 
□投稿者/ マリオ (6回)-(2015/01/05(Mon) 19:04:48)
No74485 (マリオ さん) に返信
> ■No74483 (なちゃ さん) に返信
>>ちなみに偏る原因ですが、乱数の上限を上げると偏りは減ること、またその減り方の傾向と、
>>頻度表で左下や右上が少なくなる→元の順がわずかに残りやすい傾向にあること、
>>などから、やっぱりおそらく同一の値が出てしまうことで、安定ソートによる元の順序の保持がわずかに影響を与えるのだろうと思われます。
解決済み
引用返信 編集キー/

次の20件>
トピック内ページ移動 / << 0 | 1 >>

管理者用

- Child Tree -