|
1
|
Index: array.c
|
|
2
|
===================================================================
|
|
3
|
--- array.c (revision 27218)
|
|
4
|
+++ array.c (working copy)
|
|
5
|
@@ -4051,7 +4051,187 @@
|
|
6
|
}
|
|
7
|
|
|
8
|
/*
|
|
9
|
+ * Recursively compute repeated permutations of r elements of the set
|
|
10
|
+ * [0..n-1].
|
|
11
|
+ * When we have a complete repeated permutation of array indexes, copy the
|
|
12
|
+ * values at those indexes into a new array and yield that array.
|
|
13
|
+ *
|
|
14
|
+ * n: the size of the set
|
|
15
|
+ * r: the number of elements in each permutation
|
|
16
|
+ * p: the array (of size r) that we're filling in
|
|
17
|
+ * index: what index we're filling in now
|
|
18
|
+ * values: the Ruby array that holds the actual values to permute
|
|
19
|
+ */
|
|
20
|
+static void
|
|
21
|
+rpermute0(long n, long r, long *p, long index, VALUE values)
|
|
22
|
+{
|
|
23
|
+ long i, j;
|
|
24
|
+ for (i = 0; i < n; i++) {
|
|
25
|
+ p[index] = i;
|
|
26
|
+ if (index < r-1) { /* if not done yet */
|
|
27
|
+ rpermute0(n, r, p, index+1, values); /* recurse */
|
|
28
|
+ }
|
|
29
|
+ else {
|
|
30
|
+ /* We have a complete permutation of array indexes */
|
|
31
|
+ /* Build a ruby array of the corresponding values */
|
|
32
|
+ /* And yield it to the associated block */
|
|
33
|
+ VALUE result = rb_ary_new2(r);
|
|
34
|
+ VALUE *result_array = RARRAY_PTR(result);
|
|
35
|
+ const VALUE *values_array = RARRAY_PTR(values);
|
|
36
|
+
|
|
37
|
+ for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
|
|
38
|
+ ARY_SET_LEN(result, r);
|
|
39
|
+ rb_yield(result);
|
|
40
|
+ if (RBASIC(values)->klass) {
|
|
41
|
+ rb_raise(rb_eRuntimeError, "repeated permute reentered");
|
|
42
|
+ }
|
|
43
|
+ }
|
|
44
|
+ }
|
|
45
|
+}
|
|
46
|
+
|
|
47
|
+/*
|
|
48
|
* call-seq:
|
|
49
|
+ * ary.repeated_permutation(n) { |p| block } -> array
|
|
50
|
+ * ary.repeated_permutation(n) -> enumerator
|
|
51
|
+ *
|
|
52
|
+ * When invoked with a block, yield all repeated permutations of length
|
|
53
|
+ * <i>n</i> of the elements of <i>ary</i>, then return the array itself.
|
|
54
|
+ * The implementation makes no guarantees about the order in which
|
|
55
|
+ * the repeated permutations are yielded.
|
|
56
|
+ *
|
|
57
|
+ * When invoked without a block, return an enumerator object instead.
|
|
58
|
+ *
|
|
59
|
+ * Examples:
|
|
60
|
+ *
|
|
61
|
+ * a = [1, 2]
|
|
62
|
+ * a.repeated_permutation(1).to_a #=> [[1], [2]]
|
|
63
|
+ * a.repeated_permutation(2).to_a #=> [[1,1],[1,2],[2,1],[2,2]]
|
|
64
|
+ * a.repeated_permutation(3).to_a #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
|
|
65
|
+ * # [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
|
|
66
|
+ * a.repeated_permutation(0).to_a #=> [[]] # one permutation of length 0
|
|
67
|
+ */
|
|
68
|
+
|
|
69
|
+static VALUE
|
|
70
|
+rb_ary_repeated_permutation(VALUE ary, VALUE num)
|
|
71
|
+{
|
|
72
|
+ long r, n, i;
|
|
73
|
+
|
|
74
|
+ n = RARRAY_LEN(ary); /* Array length */
|
|
75
|
+ RETURN_ENUMERATOR(ary, 1, &num); /* Return enumerator if no block */
|
|
76
|
+ r = NUM2LONG(num); /* Permutation size from argument */
|
|
77
|
+
|
|
78
|
+ if (r < 0) {
|
|
79
|
+ /* no permutations: yield nothing */
|
|
80
|
+ }
|
|
81
|
+ else if (r == 0) { /* exactly one permutation: the zero-length array */
|
|
82
|
+ rb_yield(rb_ary_new2(0));
|
|
83
|
+ }
|
|
84
|
+ else if (r == 1) { /* this is a special, easy case */
|
|
85
|
+ for (i = 0; i < RARRAY_LEN(ary); i++) {
|
|
86
|
+ rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
|
|
87
|
+ }
|
|
88
|
+ }
|
|
89
|
+ else { /* this is the general case */
|
|
90
|
+ volatile VALUE t0 = tmpbuf(r, sizeof(long));
|
|
91
|
+ long *p = (long*)RSTRING_PTR(t0);
|
|
92
|
+ VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
|
|
93
|
+ RBASIC(ary0)->klass = 0;
|
|
94
|
+
|
|
95
|
+ rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
|
|
96
|
+ tmpbuf_discard(t0);
|
|
97
|
+ RBASIC(ary0)->klass = rb_cArray;
|
|
98
|
+ }
|
|
99
|
+ return ary;
|
|
100
|
+}
|
|
101
|
+
|
|
102
|
+static void
|
|
103
|
+rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
|
|
104
|
+{
|
|
105
|
+ long j;
|
|
106
|
+ if (rest > 0) {
|
|
107
|
+ for (; index < n; ++index) {
|
|
108
|
+ p[r-rest] = index;
|
|
109
|
+ rcombinate0(n, r, p, index, rest-1, values);
|
|
110
|
+ }
|
|
111
|
+ }
|
|
112
|
+ else {
|
|
113
|
+ VALUE result = rb_ary_new2(r);
|
|
114
|
+ VALUE *result_array = RARRAY_PTR(result);
|
|
115
|
+ const VALUE *values_array = RARRAY_PTR(values);
|
|
116
|
+
|
|
117
|
+ for (j = 0; j < r; ++j) result_array[j] = values_array[p[j]];
|
|
118
|
+ ARY_SET_LEN(result, r);
|
|
119
|
+ rb_yield(result);
|
|
120
|
+ if (RBASIC(values)->klass) {
|
|
121
|
+ rb_raise(rb_eRuntimeError, "repeated combination reentered");
|
|
122
|
+ }
|
|
123
|
+ }
|
|
124
|
+}
|
|
125
|
+
|
|
126
|
+/*
|
|
127
|
+ * call-seq:
|
|
128
|
+ * ary.repeated_combination(n) { |c| block } -> ary
|
|
129
|
+ * ary.repeated_combination(n) -> enumerator
|
|
130
|
+ *
|
|
131
|
+ * When invoked with a block, yields all repeated combinations of
|
|
132
|
+ * length <i>n</i> of elements from <i>ary</i> and then returns
|
|
133
|
+ * <i>ary</i> itself.
|
|
134
|
+ * The implementation makes no guarantees about the order in which
|
|
135
|
+ * the repeated combinations are yielded.
|
|
136
|
+ *
|
|
137
|
+ * When invoked without a block, returns an enumerator object instead.
|
|
138
|
+ *
|
|
139
|
+ * Examples:
|
|
140
|
+ *
|
|
141
|
+ * a = [1, 2, 3]
|
|
142
|
+ * a.repeated_combination(1).to_a #=> [[1], [2], [3]]
|
|
143
|
+ * a.repeated_combination(2).to_a #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
|
|
144
|
+ * a.repeated_combination(3).to_a #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
|
|
145
|
+ * # [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
|
|
146
|
+ * a.repeated_combination(4).to_a #=> [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
|
|
147
|
+ * # [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
|
|
148
|
+ * # [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
|
|
149
|
+ * a.repeated_combination(0).to_a #=> [[]] # one combination of length 0
|
|
150
|
+ *
|
|
151
|
+ */
|
|
152
|
+
|
|
153
|
+static VALUE
|
|
154
|
+rb_ary_repeated_combination(VALUE ary, VALUE num)
|
|
155
|
+{
|
|
156
|
+ long n, i, len;
|
|
157
|
+
|
|
158
|
+ n = NUM2LONG(num); /* Combination size from argument */
|
|
159
|
+ RETURN_ENUMERATOR(ary, 1, &num); /* Return enumerator if no block */
|
|
160
|
+ len = RARRAY_LEN(ary);
|
|
161
|
+ if (n < 0) {
|
|
162
|
+ /* yield nothing */
|
|
163
|
+ }
|
|
164
|
+ else if (n == 0) {
|
|
165
|
+ rb_yield(rb_ary_new2(0));
|
|
166
|
+ }
|
|
167
|
+ else if (n == 1) {
|
|
168
|
+ for (i = 0; i < len; i++) {
|
|
169
|
+ rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
|
|
170
|
+ }
|
|
171
|
+ }
|
|
172
|
+ else if (len == 0) {
|
|
173
|
+ /* yield nothing */
|
|
174
|
+ }
|
|
175
|
+ else {
|
|
176
|
+ volatile VALUE t0 = tmpbuf(n, sizeof(long));
|
|
177
|
+ long *p = (long*)RSTRING_PTR(t0);
|
|
178
|
+ VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
|
|
179
|
+ RBASIC(ary0)->klass = 0;
|
|
180
|
+
|
|
181
|
+ rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
|
|
182
|
+ tmpbuf_discard(t0);
|
|
183
|
+ RBASIC(ary0)->klass = rb_cArray;
|
|
184
|
+ }
|
|
185
|
+ return ary;
|
|
186
|
+}
|
|
187
|
+
|
|
188
|
+/*
|
|
189
|
+ * call-seq:
|
|
190
|
* ary.product(other_ary, ...) -> array
|
|
191
|
* ary.product(other_ary, ...) { |p| block } -> ary
|
|
192
|
*
|
|
193
|
@@ -4361,6 +4541,8 @@
|
|
194
|
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
|
|
195
|
rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
|
|
196
|
rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
|
|
197
|
+ rb_define_method(rb_cArray, "repeated_permutation", rb_ary_repeated_permutation, 1);
|
|
198
|
+ rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, 1);
|
|
199
|
rb_define_method(rb_cArray, "product", rb_ary_product, -1);
|
|
200
|
|
|
201
|
rb_define_method(rb_cArray, "take", rb_ary_take, 1);
|
|
202
|
Index: test/ruby/test_array.rb
|
|
203
|
===================================================================
|
|
204
|
--- test/ruby/test_array.rb (revision 27218)
|
|
205
|
+++ test/ruby/test_array.rb (working copy)
|
|
206
|
@@ -814,6 +814,40 @@
|
|
207
|
assert_match(/reentered/, e.message)
|
|
208
|
end
|
|
209
|
|
|
210
|
+ def test_repeated_permutation_with_callcc
|
|
211
|
+ respond_to?(:callcc, true) or require 'continuation'
|
|
212
|
+ n = 1000
|
|
213
|
+ cont = nil
|
|
214
|
+ ary = [1,2,3]
|
|
215
|
+ begin
|
|
216
|
+ ary.repeated_permutation(2) {
|
|
217
|
+ callcc {|k| cont = k} unless cont
|
|
218
|
+ }
|
|
219
|
+ rescue => e
|
|
220
|
+ end
|
|
221
|
+ n -= 1
|
|
222
|
+ cont.call if 0 < n
|
|
223
|
+ assert_instance_of(RuntimeError, e)
|
|
224
|
+ assert_match(/reentered/, e.message)
|
|
225
|
+ end
|
|
226
|
+
|
|
227
|
+ def test_repeated_combination_with_callcc
|
|
228
|
+ respond_to?(:callcc, true) or require 'continuation'
|
|
229
|
+ n = 1000
|
|
230
|
+ cont = nil
|
|
231
|
+ ary = [1,2,3]
|
|
232
|
+ begin
|
|
233
|
+ ary.repeated_combination(2) {
|
|
234
|
+ callcc {|k| cont = k} unless cont
|
|
235
|
+ }
|
|
236
|
+ rescue => e
|
|
237
|
+ end
|
|
238
|
+ n -= 1
|
|
239
|
+ cont.call if 0 < n
|
|
240
|
+ assert_instance_of(RuntimeError, e)
|
|
241
|
+ assert_match(/reentered/, e.message)
|
|
242
|
+ end
|
|
243
|
+
|
|
244
|
def test_hash
|
|
245
|
a1 = @cls[ 'cat', 'dog' ]
|
|
246
|
a2 = @cls[ 'cat', 'dog' ]
|
|
247
|
@@ -1504,6 +1538,54 @@
|
|
248
|
assert_equal(@cls[1, 2, 3, 4].permutation.to_a, b)
|
|
249
|
end
|
|
250
|
|
|
251
|
+ def test_repeated_permutation
|
|
252
|
+ a = @cls[1,2]
|
|
253
|
+ assert_equal(@cls[[]], a.repeated_permutation(0).to_a)
|
|
254
|
+ assert_equal(@cls[[1],[2]], a.repeated_permutation(1).to_a.sort)
|
|
255
|
+ assert_equal(@cls[[1,1],[1,2],[2,1],[2,2]],
|
|
256
|
+ a.repeated_permutation(2).to_a.sort)
|
|
257
|
+ assert_equal(@cls[[1,1,1],[1,1,2],[1,2,1],[1,2,2],
|
|
258
|
+ [2,1,1],[2,1,2],[2,2,1],[2,2,2]],
|
|
259
|
+ a.repeated_permutation(3).to_a.sort)
|
|
260
|
+ assert_equal(@cls[], a.repeated_permutation(-1).to_a)
|
|
261
|
+ assert_equal("abcde".each_char.to_a.repeated_permutation(5).sort,
|
|
262
|
+ "edcba".each_char.to_a.repeated_permutation(5).sort)
|
|
263
|
+ assert_equal(@cls[].repeated_permutation(0).to_a, @cls[[]])
|
|
264
|
+ assert_equal(@cls[].repeated_permutation(1).to_a, @cls[])
|
|
265
|
+
|
|
266
|
+ a = @cls[1, 2, 3, 4]
|
|
267
|
+ b = @cls[]
|
|
268
|
+ a.repeated_permutation(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
|
|
269
|
+ assert_equal(@cls[9, 8, 7, 6], a)
|
|
270
|
+ assert_equal(@cls[1, 2, 3, 4].repeated_permutation(4).to_a, b)
|
|
271
|
+ end
|
|
272
|
+
|
|
273
|
+ def test_repeated_combination
|
|
274
|
+ a = @cls[1,2,3]
|
|
275
|
+ assert_equal(@cls[[]], a.repeated_combination(0).to_a)
|
|
276
|
+ assert_equal(@cls[[1],[2],[3]], a.repeated_combination(1).to_a.sort)
|
|
277
|
+ assert_equal(@cls[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]],
|
|
278
|
+ a.repeated_combination(2).to_a.sort)
|
|
279
|
+ assert_equal(@cls[[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
|
|
280
|
+ [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]],
|
|
281
|
+ a.repeated_combination(3).to_a.sort)
|
|
282
|
+ assert_equal(@cls[[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
|
|
283
|
+ [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
|
|
284
|
+ [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]],
|
|
285
|
+ a.repeated_combination(4).to_a.sort)
|
|
286
|
+ assert_equal(@cls[], a.repeated_combination(-1).to_a)
|
|
287
|
+ assert_equal("abcde".each_char.to_a.repeated_combination(5).map{|a|a.sort}.sort,
|
|
288
|
+ "edcba".each_char.to_a.repeated_combination(5).map{|a|a.sort}.sort)
|
|
289
|
+ assert_equal(@cls[].repeated_combination(0).to_a, @cls[[]])
|
|
290
|
+ assert_equal(@cls[].repeated_combination(1).to_a, @cls[])
|
|
291
|
+
|
|
292
|
+ a = @cls[1, 2, 3, 4]
|
|
293
|
+ b = @cls[]
|
|
294
|
+ a.repeated_combination(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
|
|
295
|
+ assert_equal(@cls[9, 8, 7, 6], a)
|
|
296
|
+ assert_equal(@cls[1, 2, 3, 4].repeated_combination(4).to_a, b)
|
|
297
|
+ end
|
|
298
|
+
|
|
299
|
def test_take
|
|
300
|
assert_equal([1,2,3], [1,2,3,4,5,0].take(3))
|
|
301
|
assert_raise(ArgumentError, '[ruby-dev:34123]') { [1,2].take(-1) }
|