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