2D配列 削除部分の検索

[botta]

 ありがとう御座います。

はい、その通りです。

　ランダム関数のアルゴリズムがわからないため

サイコロを二個使って1万の座標、もしくはサイコロ1個で2万出して折り返す

最大4万個、座標的には200ｘ200の乱数を作って実際の重複数を知りたいと

思っています。この、1万分の1程度ならそのまま使おうかという算段です。

[botta]

 　　お忙しい中、つたない質問に返信いただき誠に申し訳ありません。

　返信いただいたvi（大変ありがとう御座いました）を基に自分で作ってみて、かなりの重複があることがわかりました。

そして質問自体に間違いがあると気づきました。

　100ｘ100の結果1万の座標で座標一杯（1万個）にランダムって意味がわかりませんよね。

　1万個の座標を100％として例えば15％（1500個）、35％、50％の成分が低い方からランダムに色を変えて

座標を埋めていき、重ならないように表示する、が目的です。

　拡大してランダムに連続表示すると、視野角の狭い人は色が変わって見えるのでは？というテストです。

[bungee-gum]

お役に立てたのであればなによりです。

また、解決済みなのであれば、botta様や他ユーザーが後に参照しやすくなるように、「解決策」マークを付けておくことをお勧めいたします。

****以下引用

ディスカッションフォーラムに新しい機能が追加されました

ディスカッションフォーラムで新しいスレッドを作成して質問を投稿し、その質問に対して誰かから回答が投稿された場合、「解決策？」アイコンをクリックすると、それが解決策であると示すことができます。この機能を使用すれば、他のユーザがメッセージを検索したり、スレッドを閲覧したときに、どの質問に回答が投稿されているかが一目瞭然です。質問に対する解決策となった回答にマークを付けることにより、将来、別のユーザが同じ問題に悩んだときにその解決策を再利用することができます。

****引用ここまで

よろしくお願いします。

[TAKASU]

とても興味深いアプリケーションを作られようとしておりますね。

「成分が低いほうから」というのと「ランダムに色を変えて」というのがどのような処理を意図されているのかが分かりませんが。。。

「成分」とはおそらくグレースケール画像のピクセル値なのかな、と思いますがそれですと「色」と結びつきません。。。

さらに、果たして「同じ座標の重複を検出する」という処理が、目的のアプリケーションにとって最適なのかが気になります。

根本的な問題はまだ解決していないのではないかと気になりますが、アルゴリズムのアイデアなどが必要であればまた質問して頂けると幸いです。

[botta]

 　気に掛けていただき誠に申し訳ありません。

　1万～数万個のドットの割合を変え各々のグループのドットに色を付けます。

その座標はランダムであって連続実行すると配置が常に変わるというｖｉ作りました。

　きれいに分散していたら1万個では1、2個の重複だろうと思っていたのですが予想以上に多く、

作ったｖｉを基にして、「重複を削除して、補填して検査して・・・・・」って言う方向に凝り固まって

いました。

　つまづいたとき最初からループで数万個のｘ、ｙを作り、ランダムに抜き出し削除したほうが合理的だし

簡単かなと思い直しましたがどう思われますか？

　　（ｖｉ作りも、もう若くないなあと思いつつ、皆様のしなやかさはうらやましい限りです）

[TAKASU]

そうですね、仰られている「ランダムに抜き出し削除する」ほうが楽に組める気がします。ただ、全体的なアルゴリズムが見えていない状態ではまだ何とも言えない気がします。

お仕事・研究の都合上すべてを開示するわけにもいかないとは思いますが、色々と試して頂きご不明な点はご質問頂けると幸いです。

[bungee-gum · Accepted solution]

まだ完全に理解できておりませんが、100×100ピクセル、計10000ピクセルの2次元フィールドを色を変えたドットで埋める(色は指標の小さなものからパーセントで指定、数グループ)ということでしょうか。

視野角の狭い人は色が変わって見える、というのがいまいち想像できませんが。。

ただ単に重複していない10000個のランダム順の座標が欲しいということであれば、(1,1)~(100,100)まで順番に作った後にランダムに並べ替えるといった処理のほうが良いように思いますが、いかがでしょうか。

[M.Shiraishi · Accepted solution]

横槍恐縮です。

既にみなさん書かれているように、重複を避けることは必要と思います。

1万の座標に対して、1万のBooleanの配列も作って、一度選んだところはBoolean配列にもフラグを立てて

次ランダムに選んだ時に既にフラグが立っているものだったら選び直す、とか。

(ただ、最初の内は良いですが、フラグが立ってきて残りが少なくなると遅くなるのが玉にきずですが)

ちなみに、

>きれいに分散していたら1万個では1、2個の重複だろうと思っていたのですが予想以上に多く、

とありますが、これって、まさに「誕生日のパラドックス」の話ではないでしょうか。

つまり、誕生日は365(366)通りでバラバラですが、ランダムに23人集めるだけで、

「23人とも誕生日が重複しない」確率よりも、「誰かしか誕生日が同じ、という人が1組以上いる」確率が高くなります。

23人は365人の1割にも満たない人数です。

それと同じで、「10000通りの座標の中から、ランダムに××個の座標を選ぶと、重複するか」というと、

計算してみると、たった119個選んだだけで、「119個とも座標がバラバラ」な確率が50%を切り、

「119個の中で重複がある」確率が50%以上になります。

(＝1万の座標から119個以上ランダムに選ぶ場合は、「重複がある」方が普通、ということになる)

>1万個の座標を100％として例えば15％（1500個）、35％、50％の成分が低い方からランダムに色を変えて

のような場合だと、10000の座標から1500個ランダムに選ぶと、重複が無い確率などほとんどゼロに近く、

それも1個や2個などではなく、一番ありうるのは「100個～120個くらいは重複している」というケースです。

(「1500個選ぶ」を何べん繰り返しても、毎回100個くらいは重複する)

3500個ランダムに選んだ場合は、何べん繰り返しても、毎回「500個～600個くらいは重複している」

という状態になります。

・・・それで、明示的に、「既に選んだものとの重複を避ける」というプログラムの仕組みは必須であると思います。