うえ
(13:14:55)[Atzy] ここにあるみたい
(13:15:12)[tea] どうしてあっちの人は大文字を使うんだろう。
(13:15:53)[はらだ] Atzyの人
(13:16:42)[Glenn] glennでは
(13:16:45)[Glenn] かっこわるいから
(13:16:53)[Atzy] atzyではかっこわるいし
(13:17:12)[Glenn] へるしんき。ふぃらんどー
(13:17:23)[Atzy] どー
(13:17:25)[Glenn] 大文字の方が
(13:17:29)[Glenn] いんぱくとあるのかな
(13:17:38)[Glenn] fiはふぃじーで、FIがフィンランドとか。(嘘
(13:17:52)[tea] フィリピンかも。
(13:18:06)[Glenn] philipine!
(13:18:22)[Atzy] フェリペ二世
(13:18:27)[Glenn] superumisuttayouda
(13:18:28)[tea] ぎく。
(13:18:51)[Atzy] Philippines
(13:19:02)[Glenn]  philippineだ!
(13:19:09)[tea] うーむ。
(13:19:14)[Atzy] それは形容詞らしいよ
(13:19:15)[Glenn]  philippinesか!
(13:19:17)[tea] めちゃくちゃ無駄なプログラムを書いていた。
(13:19:27)[Atzy] おう!
(13:19:27)[Glenn] 島がたくさんあるからねえ
(13:19:47)[Atzy] るっくあっぷきのうがほしいね
(13:20:04)[tea] るっくるっく
(13:20:09)[Glenn] すぺるえらーには赤波線がでたり。
(13:20:13)[Atzy] おうおう
(13:20:16)[Glenn] うざそう
(13:20:18)[tea] 赤外線が出るのはどうですか。
(13:20:23)[はらだ] M-x what-domain はデータが少ないのがいかんな。
(13:20:30)[tea] 追加してください。
(13:20:37)[Glenn] びーむがとびかう。
(13:20:38)[はらだ] 最近のemacsだと追加されてるのかも。
(13:21:37)[tea] FI: The Republic of Finland
(13:21:40)[tea] と出たな。
(13:21:59)[はらだ] めじゃーどころは出ますな。
(13:22:27)[げる] 175個あった
(13:22:57)[はらだ] BITNET: Because It's Time NET
(13:23:00)[はらだ] そうだったのか。
(13:23:22)[tea] (13:23:34)[tea] 必ず大文字で出るのか。
(13:23:49)[はらだ] ARPA がないな。
(13:24:17)[tea] うちのはあるな。
(13:24:23)[はらだ] ほう。
(13:24:23)[げる] ARPA: Advanced Research Projects Agency (U.S. DoD)
(13:24:28)[げる] とでた。
(13:24:42)[はらだ] Emacs 20.7.1付属のやつなんだがな。
(13:24:59)[tea] 補完がきくのだな。
(13:25:00)[はらだ] む、嘘だ。
(13:25:04)[はらだ] やっぱり arpa もあるや。
(13:25:07)[tea] :D
(13:25:27)[Glenn] あの先生方、
([Nishi@cj3048348-a.stama1.kt.home.ne.jp] logged in @ 2001-04-19(Thu) 13:25:28 JST)
(13:25:28)[げる] natoもあるのか
(13:25:33)[はらだ] Argentine Republic に邪魔されていた。
(13:25:35)[tea] ねばねば
(13:25:36)[Glenn] お知恵をおかりしたいのですが、
(13:25:43)[tea] どこの先生だろう。
(13:25:47)[Glenn] ここに問題があります。
([ったく@gold.ma.onlab.ntt.co.jp] logged out @ 2001-04-19(Thu) 13:26:08 JST)
(13:26:37)[Glenn] n個のものの並べ替えをしたいのですが
(13:26:42)[Glenn] (順列)
([Nishi@cj3048348-a.stama1.kt.home.ne.jp] logged out @ 2001-04-19(Thu) 13:26:52 JST)
(13:26:54)[Glenn] n個の配列に
(13:27:15)[Glenn] かぶらないように0〜n-1の数字を割り振っていきたいのです。
(13:27:23)[Glenn] で、
(13:28:01)[Glenn] nの数が、9以上の平方数(9とか16とか)なんですが、
(13:28:30)[Glenn] 現在はとりあえずn-1回サイコロをふって順列を決めています。
(13:28:39)[Glenn] これをもっと効率化したいのですが
(13:28:45)[Glenn] お知恵を拝借できませんでしょうか。
(13:28:57)[tea] n-1回のさいころでできるのか。
(13:29:06)[Atzy] さいころがおなじめを
(13:29:09)[はらだ] 順列を全部生成するわけじゃないのか。
(13:29:09)[Atzy] だしたりしないんですか?
(13:29:17)[Glenn] 1パターンをきめたい。
(13:29:20)[Glenn] えーと
([ったく@gold.ma.onlab.ntt.co.jp] logged in @ 2001-04-19(Thu) 13:29:27 JST)
(13:29:31)[Glenn] ランダムに決めたいんです。
(13:29:42)[Glenn] ええと、
(13:29:45)[Glenn] もう少し細かく言うと
(13:29:54)[Glenn] 画像の各ピクセルに対して
(13:29:56)[はらだ] 一個だけランダムな順列を得ればいいのかな。
(13:30:05)[Glenn] 1つの順列をつくってあげたい。
(13:30:19)[Atzy] なるほど
(13:30:22)[Glenn] 1ピクセルを n 個のサブピクセルに分割して
(13:30:34)[tea] ディザですか。
(13:30:39)[Glenn] その中のサブピクセルの並び方をランダムに決める、ということをやりたいんです。
(13:30:55)[Glenn] あーー
(13:30:56)[ったく] 自由度がnなんだからアルゴリズムがO(n)なのは自明じゃないの
(13:30:57)[Glenn] ちょいとちがうぞ
(13:30:59)[Glenn] まちがえたぞ
(13:31:03)[Glenn] まちがえた
(13:31:07)[Glenn] 問題をまちがえました!先生!
(13:31:10)[Glenn] もとい!
(13:31:23)[Glenn] n個の配列があります。
(13:31:32)[Glenn] そこに、4種類のものを詰めなければなりません。
(13:31:49)[tea] 自由度って何だろう。
(13:31:58)[ったく] なんだろう(ぉ
(13:32:13)[ったく] 乱数の個数がn個必要ということかしら
(13:32:19)[Glenn] n個の配列のうち、A個はりんごを、B個にはみかんを、C個にはぶどうを、D個には桃を
(13:32:24)[tea] そうみたいですね。
(13:32:25)[Glenn] 詰めてあげたい。
(13:32:26)[Glenn] ここで、
(13:32:36)[はらだ] 配列をシャッフルする方法っていつもど忘れするな。
(13:32:38)[Glenn] A,B,C,Dは全てぜろいじょうの整数で、
(13:32:47)[Glenn] A+B+C+D=n.
(13:32:50)[Atzy] 配列の長さがnなのか
(13:32:54)[Glenn] はい。
(13:33:00)[おおいわ] AAABBBCCCDDDDD とか初期化しておいて
(13:33:07)[おおいわ] シャッフルする
(13:33:07)[tea] いたのか。
(13:33:12)[ったく] それ以外ないよねえ
(13:33:12)[おおいわ] でいいきがするな
(13:33:22)[Glenn] しゃっふるって、
(13:33:23)[tea] さて何回のシャッフルが必要でしょうか。
(13:33:30)[おおいわ] n-1
(13:33:38)[Glenn] n-1回サイコロ投げる以外の方法ありますか?
(13:33:45)[ったく] ないのでは
(13:33:48)[Glenn] やはり。
(13:33:49)[Glenn] しくり。
(13:34:04)[Glenn] 単純に、はっしゅてーぶるつくればいーじゃん、といった人がいるのですが、
(13:34:14)[Glenn] ハッシュが簡単にできるような大きさではないのです。
(13:34:15)[おおいわ] random という条件下ではそうなるよね
(13:34:17)[Glenn] よね。
(13:34:24)[Atzy] 疑似的なというかそれっぽくするだけなら
(13:34:28)[おおいわ] randomness が低くていいとか
(13:34:39)[Atzy] まあ,他の方法があると思いますけど.
(13:34:44)[おおいわ] 全パターン発生しなくていいとかなら
(13:34:49)[おおいわ] 何かありそうな気はするが
(13:35:03)[Glenn] もしよろしければ、ポインタだけでも
(13:35:05)[おおいわ] その辺はもっと条件を精査しないとあれだけどね
(13:35:07)[Glenn] いただけますか?
(13:35:09)[Glenn] キーワードでも。
(13:35:14)[Glenn] 全くして無知なもので。(^^;
(13:35:14)[おおいわ] しらない
(13:35:20)[Glenn] あう(^^;
(13:35:22)[おおいわ] ありそうだなーとおもっただけ。
(13:35:26)[ったく] 乱数発生関数の呼び出しを半分にするだけなら
(13:35:51)[ったく] k*(k-1)の乱数をつくって商と余りを取るとかすれば
(13:35:54)[ったく] 半分になるな:-)
(13:36:01)[ったく] シミュレーションには品質的につかえんが
(13:36:07)[おおいわ] そう?
(13:36:13)[おおいわ] 乱数の性質次第では。
(13:36:17)[Glenn] ディザリングに使うので
(13:36:25)[ったく] そうだけど、疑似乱数だと
(13:36:33)[ったく] さすがに組にして使うと質落ちないかな。
(13:36:46)[Glenn] 人間の目に周期性が見えなければいいんですが…
(13:36:56)[はらだ] なんとかツイスターを。
(13:36:57)[ったく] 落ちないとすると、k*...*(k-x) とか無限にいけるわけで:-)
(13:37:07)[おおいわ] え゛
(13:37:16)[おおいわ] それは「乱数が何bitかあるか」
(13:37:17)[おおいわ] なのでは
(13:37:21)[ったく] ああ、それはそうだけど
(13:37:35)[ったく] そこにたどり着く前に、乱数の良くなさ加減のほうが先に影響する気が
(13:37:37)[Glenn] ふむ
(13:37:47)[おおいわ] だってM系列とか
(13:37:51)[おおいわ] 各ビット独立でしょ
(13:37:59)[おおいわ] あまり関係ないきが。
(13:38:09)[tea] うーむ。
(13:38:12)[ったく] それもそうか
(13:38:26)[ったく] 浮動小数演算経由するからそんな単純じゃないにしても。
(13:38:34)[おおいわ] (13:38:41)[おおいわ] 整数でやるんじゃないの (^^;
(13:38:45)[ったく] (13:38:58)[ったく] 乱数発生器は0...1を返すんじゃないのか:->
(13:39:14)[ったく] 0...(k*...*(k-x)-1)を返しても内部処理は等価だが
(13:39:18)[おおいわ] d = MAX_RAND / m; do {r = rand() / d;} while (r < m);
(13:39:28)[おおいわ] じゃないの? :-)
(13:39:34)[ったく] まあ要するに、切れ目は2^nじゃないところにあるから
(13:39:40)[ったく] bit独立だからといってそれでいいかは
(13:39:44)[ったく] 自明とまではいえないような
(13:39:56)[おおいわ] うーん
(13:40:06)[おおいわ] まぁそうだけどねぇ
(13:40:06)[ったく] 2^10とりだして2^2を5個としてつかうなら自明にそうだけど。
([あぶら@italk.ne.jp] logged in @ 2001-04-19(Thu) 13:40:12 JST)
(13:40:16)[あぶら] ぷぷぅ
(13:40:21)[ったく] ま、画像の見た目ごまかすくらいならなんでもよさげ
(13:40:26)[あぶら] 数学の香里が。
(13:40:44)[Glenn] うーむ
(13:40:45)[おおいわ] でもさー
(13:41:03)[おおいわ] m, n とりだして変な依存関係があるってことは
(13:41:17)[おおいわ] m * 5 + n に強烈な規則性があるって事だよね
(13:41:19)[Glenn] おおいわさんとったくさんの会話に
(13:41:23)[Glenn] ついていけない…
(13:41:32)[ったく] そうだな:-)
(13:41:33)[おおいわ] 問題になるような依存があったら
(13:41:36)[ったく] よくなさげ:-)
(13:41:48)[おおいわ] だよね :-)
(13:41:59)[おおいわ] 逆に m * 5 + n がマトモになってれば
(13:42:03)[ったく] というわけでアルゴリズム自体がO(n)なのは自明で
(13:42:05)[あぶら] ほえほえ
(13:42:09)[おおいわ] そこそこいけそうだと思うんだがねぇ :-)
(13:42:16)[ったく] 乱数発生関数呼び出しを定数おーだーで減らすことは可能
(13:42:17)[ったく] (13:42:27)[おおいわ] 一般に乱数の2つ組とかは
(13:42:27)[あぶら] 問題定義の問題らしい
(13:42:31)[おおいわ] やばいんだけどね :-)
(13:43:02)[はらだ] プロットすると模様が出ますか。
(13:43:06)[おおいわ] そうそう:-)
した
れろ