-
Notifications
You must be signed in to change notification settings - Fork 12
/
CombinationsGauche.html
227 lines (187 loc) · 8.52 KB
/
CombinationsGauche.html
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
<p>This SRFI implements several useful procedures of
combinations, permutations and related operations.
</p>
<h3>Set operations</h3>
<p>Sets in the following procedures are in
the sense of SRFI 1, that is, lists.
Some of these procedures have two variants: a procedure without
star (e.g. <code>permutations</code>) treats all elements in the given
set distinct, while a procedure with star (e.g. <code>permutations*</code>)
considers duplication. The procedures with star take a <var>pred</var>
argument that is used to test equality.
</p>
<dl>
<dt><a name="index-permutations"></a><code>permutations</code> <em>set</em></dt>
<dt><a name="index-permutations_002a"></a><code>permutations*</code> <em>pred set</em></dt>
<dd><p>Returns a list of all permutations of a list <var>set</var>.
</p>
<div class="example">
<pre class="example">(permutations '(a b c))
⇒ ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
(permutations '(a a b))
⇒ ((a a b) (a b a) (a a b) (a b a) (b a a) (b a a))
(permutations* '(a a b))
⇒ ((a a b) (a b a) (b a a))
</pre></div>
<p>The number of possible permutations explodes if <var>set</var> has
more than several elements. Use with care. If you want to process
each permutation at a time, consider <code>permutations-for-each</code> below.
</p></dd></dl>
<dl>
<dt><a name="index-permutations_002dfor_002deach"></a><code>permutations-for-each</code> <em>proc set</em></dt>
<dt><a name="index-permutations_002a_002dfor_002deach"></a><code>permutations*-for-each</code> <em>proc pred set</em></dt>
<dd><p>For each permutation of a list <var>set</var>, calls <var>proc</var>.
Returns an undefined value.
</p></dd></dl>
<dl>
<dt><a name="index-combinations"></a><code>combinations</code> <em>set n</em></dt>
<dt><a name="index-combinations_002a"></a><code>combinations*</code> <em>pred set n</em></dt>
<dd><p>Returns a list of all possible combinations of <var>n</var> elements out
of a list <var>set</var>.
</p>
<div class="example">
<pre class="example">(combinations '(a b c) 2)
⇒ ((a b) (a c) (b c))
(combinations '(a a b) 2)
⇒ ((a a) (a b) (a b))
(combinations* '(a a b) 2)
⇒ ((a a) (a b))
</pre></div>
<p>Watch out for the explosion of combinations when <var>set</var> is large.
</p></dd></dl>
<dl>
<dt><a name="index-combinations_002dfor_002deach"></a><code>combinations-for-each</code> <em>proc set n</em></dt>
<dt><a name="index-combinations_002a_002dfor_002deach"></a><code>combinations*-for-each</code> <em>proc pred set n</em></dt>
<dd><p>Calls <var>proc</var> for each combination of <var>n</var> elements out of <var>set</var>.
Returns an undefined value.
</p></dd></dl>
<dl>
<dt><a name="index-power_002dset"></a><code>power-set</code> <em>set</em></dt>
<dt><a name="index-power_002dset_002a"></a><code>power-set*</code> <em>pred set</em></dt>
<dd><p>Returns power set (all subsets) of a list <var>set</var>.
</p>
<div class="example">
<pre class="example">(power-set '(a b c))
⇒ (() (a) (b) (c) (a b) (a c) (b c) (a b c))
(power-set* '(a a b)
⇒ (() (a) (b) (a a) (a b) (a a b))
</pre></div>
</dd></dl>
<dl>
<dt><a name="index-power_002dset_002dfor_002deach"></a><code>power-set-for-each</code> <em>proc set</em></dt>
<dt><a name="index-power_002dset_002a_002dfor_002deach"></a><code>power-set*-for-each</code> <em>proc pred set</em></dt>
<dd><p>Calls <var>proc</var> for each subset of <var>set</var>.
</p></dd></dl>
<dl>
<dt><a name="index-power_002dset_002dbinary"></a><code>power-set-binary</code> <em>set</em></dt>
<dd><p>Returns power set of <var>set</var>, like <code>power-set</code>, but in different order.
<code>Power-set-binary</code> traverses subset space in depth-first order,
while <code>power-set</code> in breadth-first order.
</p>
<div class="example">
<pre class="example">(power-set-binary '(a b c))
⇒ (() (c) (b) (b c) (a) (a c) (a b) (a b c))
</pre></div>
</dd></dl>
<dl>
<dt><a name="index-cartesian_002dproduct"></a><code>cartesian-product</code> <em>list-of-sets</em></dt>
<dt><a name="index-cartesian_002dproduct_002dright"></a><code>cartesian-product-right</code> <em>list-of-sets</em></dt>
<dd><p>Returns a cartesian product of sets in <var>list-of-sets</var>.
<code>Cartesian-product</code> construct the result in left fixed order
(the rightmost element varies first), while
<code>cartesian-product-right</code> in right fixed order
(the leftmost element varies first).
</p>
<div class="example">
<pre class="example">(cartesian-product '((a b c) (0 1)))
⇒ ((a 0) (a 1) (b 0) (b 1) (c 0) (c 1))
(cartesian-product-right '((a b c) (0 1)))
⇒ ((a 0) (b 0) (c 0) (a 1) (b 1) (c 1))
</pre></div>
</dd></dl>
<dl>
<dt><a name="index-group_002dlist"></a><code>group-list</code> <em>list [[|key [ test ]]
]</em></dt>
<dd><p>Groups consecutive elements in a list <var>list</var> which
have the common key value. A key value of an element is
obtained by applying the procedure <var>key</var> to the element;
the default procedure is <code>identity</code>.
For each element in <var>list</var>, <var>key</var> is applied exactly once.
The equal-ness of keys are compared by <var>test</var> procedure,
whose default is <code>eqv?</code>.
</p>
<div class="example">
<pre class="example">(group-list '(1 1 1 2 3 4 4 2 2 3 1 1 3))
⇒ ((1 1 1) (2) (3) (4 4) (2 2) (3) (1 1) (3))
(group-list '(1 1 1 2 3 4 4 2 2 3 1 1 3)
:key (cut modulo <> 2)))
⇒ ((1 1 1) (2) (3) (4 4 2 2) (3 1 1 3))
(group-list '#("a" "a" "b" "b" "c" "d" "d")
:test string=?)
⇒ (("a" "a") ("b" "b") ("c") ("d" "d"))
(group-list "aabbcdd"
:test char=?)
⇒ ((#\a #\a) (#\b #\b) (#\c) (#\d #\d))
</pre></div>
</dd></dl>
<dl>
<dt><a name="index-permute"></a><code>permute</code> <em>vector permuter [[|fallback ]]</em></dt>
<dd><p>Returns a newly created vector, in which
the elements are permuted from <var>src</var> according to <var>permuter</var>.
</p>
<p><var>Permuter</var> is a list of exact integers. When the <var>k</var>-th element
of <var>permuter</var> is <var>i</var>, the <var>k</var>-th element of the result
is <code>(ref <var>src</var> <var>i</var>)</code>. Therefore, the size of the result
list is the same as the size of <var>permuter</var>. <var>Permuter</var>
can be any kind of list, unrelated to the type of <var>src</var>.
</p>
<p>The same index <var>i</var> can appear more than once
in <var>permuter</var>.
</p>
<div class="example">
<pre class="example">(permute '#(a b c d) '(3 2 0 1)) ⇒ #(d c a b)
(permute '#(a b c d) '(0 2)) ⇒ #(a c)
(permute '#(a b c d) '(0 0 1 1 2 2)) ⇒ #(a a b b c c)
</pre></div>
<p>If an integer in <var>permuter</var> is out of the valid range for an index
of <var>vector</var>, then <var>fallback</var> is returned.
</p>
<div class="example">
<pre class="example">(permute '#(a b c) '(3 2 1 0) 'foo) ⇒ #(foo c b a)
(permute "!,HWdelor" #(2 5 6 6 7 1 -1 3 7 8 6 4 0) #\space)
⇒ "Hello, World!"
</pre></div>
</dd></dl>
<h3>Random operations</h3>
These procedures use <code>default-random-source</code> from
<a href="http://srfi.schemers.org/srfi-27/srfi-27.html">SRFI 27</a>.
<dl>
<dt><a name="index-permutations_002dof"></a><code>make-permutation-generator</code><i> vector</i></dt>
<dd><p>Returns a generator that yields random permutations of <var>vector</var>.
</p>
<table><tr><td> </td><td><pre class="example">(generator->list (make-permutation-generator '(1 2 3)) 3)
⇒ ((1 2 3) (2 3 1) (3 2 1))
(generator->list (make-permutation-generator "abc") 3)
⇒ ("cba" "cba" "cab")
</pre></td></tr></table>
</dd></dl>
<dl>
<dt><a name="index-combinations_002dof"></a><code>make-combination-generator</code><i> size vector</i></dt>
<dd><p>Returns a generator that yields vectors of <var>size</var> elements
randomly picked from <var>vector</var>.
</p>
<table><tr><td> </td><td><pre class="example">(generator->list (make-combination-generatorh 2 #(a b c)) 5)
⇒ (#(a c) #(a b) #(a c) #(b a) #(a c))
(generator->list (make-combination-generator 2 '#(a b c)) 5)
⇒ (#(a c) #(b c) #(c b) #(b a) #(b c))
</pre></td></tr></table>
</dd></dl>
<dl>
<dt><a name="index-shuffle"></a><code>shuffle</code> <em>vector [[|random-source ]]</em></dt>
<dd><p>Returns a new vector of the same size as <var>vector</var>,
in which elements are randomly permuted.
</p>
<div class="example">
<pre class="example">(shuffle '#(a b c d e)) ⇒ #(e b d c a)
</pre></div>
</dd></dl>