1\documentclass{article} 2\usepackage[latin1]{inputenc} 3\usepackage[T1]{fontenc} 4\usepackage{color} 5\definecolor{blue}{cmyk}{1,1,0,0} 6\definecolor{red}{cmyk}{0,1,1,0} 7\definecolor{green}{cmyk}{1,0,1,0} 8\definecolor{green}{rgb}{0,0.8,0} 9\definecolor{lightgreen}{rgb}{0.6,1,0.6} 10\definecolor{gray}{rgb}{0.33, 0.33, 0.33} 11\definecolor{forestgreen}{rgb}{0.1,0.6,0.1} 12\definecolor{darkgreen}{rgb}{0,0.6,0} 13\definecolor{lightblue}{rgb}{0.5,0.5,1} 14\definecolor{purple}{rgb}{1,0,1} 15\definecolor{lightred}{rgb}{1,0.5,0.5} 16\definecolor{darkred}{rgb}{0.6,0,0} 17\definecolor{magenta}{cmyk}{0,1,0,0} 18\definecolor{yellow}{cmyk}{0,0,1,0} 19\definecolor{cyan}{cmyk}{1,0,0,0} 20\definecolor{brown}{rgb}{0.3,0.3,0.8} 21\definecolor{orange}{named}{Salmon} 22\definecolor{classcolor}{named}{Peach} 23\definecolor{libcolor}{named}{MidnightBlue} 24\definecolor{commentcolor}{named}{Melon} 25\definecolor{kwdcolor}{named}{Tan} 26\definecolor{stringcolor}{rgb}{0.1,0.6,0.1} 27\usepackage{listings} 28\lstavoidwhitepre 29\lstset{language=caml} 30\def\bfcolor#1{\ttfamily\bfseries\color{#1}} 31\def\itcolor#1{\itshape\color{#1}} 32\newcommand{\kwd}{\bfcolor{kwdcolor}} 33\newcommand{\ndkwd}{\bfcolor{libcolor}} 34\newcommand{\emphstyle}{\bfcolor{classcolor}} 35\lstdefinestyle {javastyle}{ 36 keywordstyle=\kwd, 37 ndkeywordstyle=\ndkwd, 38 commentstyle=\color{commentcolor}\scshape, 39 emphstyle=\emphstyle, 40 emphstyle={[2]\color{lightred}}, 41 stringstyle=\color{stringcolor}\itshape, 42 moredelim=[s][keywordstyle]{(*+}{+*)} 43} 44\lstset{style=javastyle} 45\lstset{morekeywords={[2]Random,Sys,Printf,Array}} 46\let\lst\lstinline 47\begin{document} 48\title{Recursive fair? shuffle} 49\author{} 50\maketitle 51\lstset{emph={merge,shuffle}}% 52\lstset{emph=[2]{gen,split}} 53Significant functions are \lst|merge| and~\lst|shuffle|. 54Functions \lst|gen| and \lst|split| are also worth a look. 55\begin{lstlisting}[escapechar=@,mathescape=true,numbers=left,stepnumber=5,numberstyle=\color{brown},frame=tb,rulecolor=\color{kwdcolor}] 56(*+@\label{start}@ 57 Special comment! 58 Start at line @\ref{start}@. 59 End at line @\ref{over}@. 60+*) 61 62(* Read arguments, $n$ is list len, � nexp � is number of experiments *) 63let n = 64 if Array.length Sys.argv > 1 then int_of_string Sys.argv.(1) 65 else 10 66 67let nexp = 68 if Array.length Sys.argv > 2 then int_of_string Sys.argv.(2) 69 else 100 70 71(* Generate list $[m\ldots{}n]$ *) 72let rec gen m n = 73 if m <= n then m::gen (m+1) n 74 else [] 75 76(* Merge (uniformly) at random *) 77let rec merge r xs sx ys sy = match xs, ys with 78| [],[] -> r 79| x::rx, [] -> merge (x::r) rx (sx-1) ys sy 80| [],y::ry -> merge (y::r) xs sx ry (sy-1) 81| x::rx, y::ry -> 82 if Random.int(sx+sy) < sx then 83 merge (x::r) rx (sx-1) ys sy 84 else 85 merge (y::r) xs sx ry (sy-1) 86 87(* Split a list into two lists of same size *) 88let rec do_split even se odd so = function 89 | [] -> (even,se), (odd,so) 90 | [x] -> (x::even,se+1), (odd,so) 91 | x::y::rem -> do_split (x::even) (se+1) (y::odd) (so+1) rem 92 93let split xs = do_split [] 0 [] 0 xs 94 95(* Actual suffle *) 96let rec shuffle xs = match xs with 97| []|[_] -> xs 98| _ -> 99 let (ys,sy), (zs,sz) = split xs in 100 merge [] (shuffle ys) sy (shuffle zs) sz 101 102 103 104(* Perform experiment *) 105let zyva n m = 106 let xs = gen 1 n in 107 let t = Array.make_matrix (n+1) (n+1) 0 in 108 for k = 1 to m do 109 let ys = shuffle xs in 110 let idx = ref 1 in 111 List.iter 112 (fun x -> t.(!idx).(x) <- t.(!idx).(x) + 1 ; incr idx) 113 ys 114 done ; 115 let mm = float_of_int m in 116 for i = 1 to n do 117 let t = t.(i) in 118 for k=1 to n do 119 let f = float_of_int t.(k) *. 100.0 /. mm in 120 printf " %02.2f" f 121 done ; 122 print_endline "" 123 done 124 125let _ = zyva n nexp ; exit 0 126 127(* @\label{over}@Start at line @\ref{start}@, end here. *) 128 129(* 130(***************) 131(* Print lists *) 132(***************) 133*) 134 135open Printf 136 137let rec do_plist = function 138 | [] -> printf "}" 139 | x::xs -> printf ", %i" x ; do_plist xs 140 141let plist = function 142 | [] -> printf "{}" 143 | x::xs -> printf "{%i" x ; do_plist xs 144 145let plistln xs = plist xs ; print_endline "" 146\end{lstlisting} 147\end{document} 148