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