リストのシャッフル

http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p04
の正しさについてしばし考えた。

リストの各要素について[0,1]区間の一様乱数を振って、その値でsortしていると理解してみた。もっと単純な解釈はないだろうか。

追記

これを実装したのが、上記のアルゴリズムだという解釈です。任意の順列に付いて容易に出現する確率が計算できて、正しいシャッフルだと証明できます。

http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051025#p01 より

  • 直感的には「平等」なのですが、全ての順列が等確率で出現するかどうかとは距離があります。例えば、出現しない順列があるかもしれない。
  • 小学生はしばしば騙されるので:-)、ちゃんと理解しようとするとややこしいことが沢山あるように思います。
  • 「決まるまでジャンケン/コイン投げをする」というそのままのモデル化だと、単純な確率空間の一つの事象というわけにいかないように思います。

リストのシャッフル

先日のアルゴリズムは逆向きにしたほうがわかりやすいと思う。Haskellで(効率を無視して)書くと、こういうこと。Arrayを使用する場合はselectOneに代えてswapにしたりすればO(N)にできる。

module Shuffle where
import System.Random

listShuffle :: StdGen -> [a] -> [a]
listShuffle g [] = []
listShuffle g xs = y:listShuffle g' ys
  where (m, g') = randomR (0, length xs - 1) g
	(y, ys) = selectOne xs !! m

selectOne [] = []
selectOne (x:xs) = (x, xs):[(y, x:ys) | (y, ys) <- selectOne xs]

前のページ・次のページ

前のページ・次のページ。 Web を徘徊していて気になった「次のページ」という記述。これは「後のページ」の方がわかりやすいんではないか。時間を一方向にしか進めない人にとっては 次 = 未来 なのかもしれないけど。

http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p01

back <-> next がわかりやすいので、日本誤訳すると、「後*1のページ・次のページ」だろうか:-)*2

私は「後(あと)のページ」を不自然に感じるのだが、それは、未来は前にあって過去は後にあるからだろうか?

…「前」を時間的に過去にある事象に使うときは、その時系列(A -> B -> C)全体を最初の地点から眺めているように思う。そうすると、AはBの手「前」にある。「Bの後(うしろ)」は意味をなさない。

(  @_@)  A -> B -> C

しかし、自分が現在Bにいるのであれば、Aは自分の背「後」(back)にあることにある。

A -> (  @_@) B -> C 

時間を超越した始点に視点を置くのが日本語で、現在の自分を主体とするのが英語の表現だろうか。

最も、後者の図式でも、BやCが自分の方を向いているなら、Bの目の「前」にAは依然としてあるわけだし、、Bの「後(うしろ)」にCがあることになる。どちらの図式でも、Bの「後(あと)」にCがあり、Bの次にCがあるのは変わらないだろう。
してみると、日本語の表現は、Bの「前/後」のA/Cという表現は、過去を向いている事象Bを主体として述べた表現だと解釈して、前・後それぞれの意味の二重性を解決したほうがよいのだろうか。
過去を向いている事象という立場にたつと、「前のページ・後のページ」が良いことになりそうだ。

しかし、私の頭は無意識に前者の図式を観ていて、後(うしろ)を想起してしまうので、不自然に感じる。不自然さの原因はまだある。「次」には行為の主体と選択の余地を感じさせるが、「後」は感じさせない。もちろん「*のページ」に進むかどうかは私の自由だ。それに、「次」は意味の連関を感じさせるが、「後」は感じさせない。こっちは文脈次第であり、無関係な「*のページ」もあるかもしれないが、それこそ、そのページを「後(あと)」にする理由がないではないか。

そもそも、ウェブページのリンクは時間的構造なのだろうか?

本はそうだ。一本の線をなしている。本の線形に積み重なった文章は、時間の構造と一致するから、既に参照したページを「前に戻って」読むことができるのだ*3
しかし、空間的構造である道路では違う。歩いていて、「後に戻る」ことはできるが、誰も「前に戻る」なんてことはしない。地球は球体だが、少し大きすぎる。

ウェブページは空間的構造ではないか?なにしろ、ネットサーフィンするのだし、リンクは一本の線ではなく網なのだ。もちろん「前のページ・次のページ」が書かれるページは局所的に線の構造をもってはいるし、読者は時間の前後関係のなかで辿り着く。しかし、依然としてそれはネットワークの一部であり、つまりそれらページは本質的に空間的な構造の一員であって、眼前のページは空間における一本道の一点なのである。

したがって、やはり「後のページ・次のページ」*4というのが良いのではないだろうか。

# いや、本当は「後のページ・前のページ」が望ましいのだ。道は前に進み、後に戻るものなのだから。だが残念なことに、今やhackerはcrackerなのだ。そしてもう一つの折衷案の「前のページ・前のページ」には致命的な欠点がある。

追記

http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p03 より
  • 日記の場合は、読者ではなく日記の時間における過去(前)、未来(後)を指すものとして、前のページ(前の日記)、後のページ(後(のち)の日記)が自然だと思います。
  • 「誤訳」なのは、「語訳」とするべきかどうか迷いましたが、翻訳は逐語的であるよりは適切に意味内容・意図を伝えるものであるという意味で、それが正しい訳ではないからです*5
捕捉1
(  @_@)  A -> B -> C
A -> (  @_@) B -> C 

明確な前後を持たない物体については、Bの向う側にCがあるということを、「Bの後(うしろ)」にCがあると表現するのは自然である。従って、事象自体には「向き」を導入せずに、人の視点からのみ議論する事もできた。しかし、その「後(うしろ)」という表現が、自分の観ている面をその物体の前面として認識したがる人間の性質によるものであると考えると、未来方向を観ている人間の視点から従った「向き」を明示的に導入するほうが議論が明晰である。

捕捉2
A -> (o_o ) B -> C 

その事象の地点に過去を向いている人間を考えることで、後(うしろ)を説明してもよいかもしれない。

が、既にわかっている過去 と、何があるかわからない未来 とを比べると、目に見えない後ろ側を未来と対応づける考え方も自然かもしれない。
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p03

*1:うしろ

*2:prev <-> nextのほうがなお良いか

*3:物質的にページが積み重なった手「前」のページでもある。一方、空間的構造でもあるから、前に読み進むこともできる

*4:振り仮名が推奨される

*5:実際には、所謂「意訳」よりも、原文を復元して意味を推定できる逐語訳のほうが却って理解しやすいことが多いのですが

リストのシャッフル

http://d.hatena.ne.jp/yts/20051022#p1 で言及されたアルゴリズムを実装してみる。

{-# OPTIONS -fglasgow-exts #-}
module Shuffle where
import Control.Monad.Fix (fix)
import System.Random

import Control.Monad.ST

import Data.Array.MArray
import Data.Array.ST

シャッフルのための互換の列を生成する関数。

swaps :: (Int -> Int -> a) -> StdGen -> [a]
swaps f gen = map fst . fix $ \lst -> 
    (f 0 0, (0, gen)):[(f j a, (j, g')) | (_, (i, g)) <- lst
	, let j = i + 1; (a, g') = randomR (0, j) g]
*Shuffle> take 20 $ swaps (,) (mkStdGen 0)
[(0,0),(1,1),(2,2),(3,1),(4,0),(5,4),(6,3),(7,3),(8,1),(9,3),(10,4),(11,11),(12,4),(13,8),(14,7),(15,8),(16,14),(17,2),(18,14),(19,7)]

互換の効率のためにリストをSTArrayに変換してからシャッフルする。

listShuffle :: StdGen -> [e] -> [e]
listShuffle gen (lst :: [e]) = runST (
	  foldl (>>=)
	    (newListArray (0, len - 1) lst :: ST s (STArray s Int e))
	    (take len $ swaps mArraySwap gen)
	  >>= getElems)
  where
    len = length lst

mArraySwap i j ar
  = do	ei <- readArray ar i
	ej <- readArray ar j
	writeArray ar j ei
	writeArray ar i ej
	return ar

[Memo] ペアマッチあみだくじ

こういうものらしい。

単に普通のあみだくじの(隣り合う)二本を底で繋げればいいと思う。
どっちに進むかわかりやすいし、下から一度折れば良い。

けれん味に欠けるからだろうか?

「あー、もういいわ。キャンセルする」
そう言って斜め後ろの客は出ていった。店に入る時に見た後ろ姿では、白髪交じりのボサボサ髪、歳の頃は五十ぐらいの男であった。注文してからは一分と経ってない。苦笑しながら給仕の女性が厨房にキャンセルを告げた。
すぐに引き戸の音がして、誰かが入って来た。
「おーい」
この声はさっきの男である。
「鍋焼きうどんはキャンセルでよろしいんですか」
「…」
「さっき鍋焼きうどん注文されましたよね。覚えてらっしゃいませんか?」
「覚えてない」
つい振り返って男を見た。…まだボケそうな歳には見えないのだが。
男は品書きを見始めたようだ。
「おーい、注文できるんか」
「はーい…何にします?」
「…何にしようかな…」
保護者はどこかにいないのだろうか。ややあって
「味噌汁とご飯」
「はい」
辛抱強く対応するものである。
私には男の鍋焼きの直後に注文した親子丼が届いた。しばらくして男の味噌汁ができた。
「これ、キャンセル」
「困ります!」
さすがに、彼女も「きっ」となった。
「あっちの人の方が早く来た。これすぐできるでしょ。キャンセル」
「キャンセルはできません!」
理路整然と説明し始めた。味噌汁は温めるだけではないらしい。
「…私何か間違ったこといってますか?」
反語調でしめる。気の強い人だ。
「じゃあキャンセルはできんのか」
「できません!」
何が起こるかとおもったが…
この男、どうやら待つということができないらしかった。結局諦めて、追加注文すると言ったのだが、三十秒後には気が変わって金を払うといいだし、支払った。食事には手をつけていない。立ち上がって、トイレに行きたいと言い、奥まで行きかけたのだが、彼女に言われて別の店員が案内しようとしたところで
「もういいわ」
出ていったのだった。