1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # Memory-efficient Cartesian products, combinations and permutation on collections.
13 # This module offers memory-efficient views on combinatoric collections.
14 # Methods of the views create objects only when needed.
15 # Moreover, produced objects during iterations are free to be collected and
16 # their memory reused.
18 # This enable these views and method to works with very combinatoric large collections.
20 # When small combinatoric views need to be kept in memory (for fast access by example).
21 # The `Collection::to_a` method and other related factories can be used to transform
22 # the combinatoric views into extensive collections,
25 redef class Collection[E
]
26 # Cartesian product, over `r` times `self`.
28 # See `CartesianCollection` for details.
30 # FIXME: Cannot be used if RTA is enabled. So `niti` or `--erasure` only.
31 fun product
(r
: Int): Collection[SequenceRead[E
]]
33 return new CartesianCollection[E
]([self]*r
)
36 # All `r`-length permutations on self (all possible ordering) without repeated elements.
38 # See `CartesianCollection` for details.
40 # FIXME: Cannot be used if RTA is enabled. So `niti` or `--erasure` only.
41 fun permutations
(r
: Int): Collection[SequenceRead[E
]]
43 var res
= new CombinationCollection[E
](self, r
)
44 res
.are_sorted
= false
49 # All `r`-length combinations on self (in same order) without repeated elements.
51 # See `CartesianCollection` for details.
53 # FIXME: Cannot be used if RTA is enabled. So `niti` or `--erasure` only.
54 fun combinations
(r
: Int): Collection[SequenceRead[E
]]
56 var res
= new CombinationCollection[E
](self, r
)
62 # All `r`-length combination on self (in same order) with repeated elements.
64 # See `CartesianCollection` for details.
66 # FIXME: Cannot be used if RTA is enabled. So `niti` or `--erasure` only.
67 fun combinations_with_replacement
(r
: Int): Collection[SequenceRead[E
]]
69 var res
= new CombinationCollection[E
](self, r
)
71 res
.are_unique
= false
76 # A view of a Cartesian-product collection over homogeneous collections.
78 # Therefore, this view *generates* all the sequences of elements constructed by associating
79 # en element for each one of the original collections.
81 # It is equivalent to doing nesting `for` for each collection.
86 # var xys = new CartesianCollection[Int]([xs, ys])
87 # assert xys.length == 6
88 # assert xys.to_a == [[1,8], [1,9], [2,8], [2,9], [3,8], [3,9]]
91 # The pattern of the generate sequences produces a lexicographical order.
93 # Because it is a generator, it is memory-efficient and the sequences are created only when needed.
95 # Note: because it is a view, changes on the base collections are reflected on the view.
100 # assert xys.to_a == [[1,8], [2,8]]
102 class CartesianCollection[E
]
103 super Collection[SequenceRead[E
]]
105 # The base collections used to generate the sequences.
106 var collections
: SequenceRead[Collection[E
]]
111 for c
in collections
do res
= res
* c
.length
115 redef fun iterator
do return new CartesianIterator[E
](self)
118 private class CartesianIterator[E
]
119 super Iterator[SequenceRead[E
]]
120 var collection
: CartesianCollection[E
]
122 # The array of iterations that will be increased in the lexicographic order.
123 var iterators
= new Array[Iterator[E
]]
127 for c
in collection
.collections
do
130 if not it
.is_ok
then is_ok
= false
134 redef var is_ok
= true
138 var len
= iterators
.length
139 var res
= new Array[E
].with_capacity
(len
)
141 var it
= iterators
[i
]
149 var rank
= iterators
.length
- 1
151 # Odometer-like increment starting from the last iterator
153 var it
= iterators
[rank
]
155 if it
.is_ok
then return
157 # The iterator if over
159 # It it is the first, then the whole thing is over
164 # If not, restart the iterator and increment the previous one
166 iterators
[rank
] = collection
.collections
[rank
].iterator
172 # A view of some combinations over a base collections.
174 # This view *generates* some combinations and permutations on a collection.
176 # By default, the generated sequences are combinations:
178 # * each sequence has a length of `repeat`
179 # * elements are in sorted order (see `are_sorted` for details)
180 # * no repeated element (see `are_unique` for details)
184 # var cxs = new CombinationCollection[Int](xs, 2)
185 # assert cxs.length == 3
186 # assert cxs.to_a == [[1,2], [1,3], [2,3]]
189 # Other kind of combinations can be generated by tweaking the attributes `are_sorted` and `are_unique`.
194 # cxs.are_sorted = false
195 # cxs.are_unique = true
196 # assert cxs.length == 6
197 # assert cxs.to_a == [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
200 # * for combinations with replacement:
203 # cxs.are_sorted = true
204 # cxs.are_unique = false
205 # assert cxs.length == 6
206 # assert cxs.to_a == [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]
212 # cxs.are_sorted = false
213 # cxs.are_unique = false
214 # assert cxs.length == 9
215 # assert cxs.to_a == [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]
218 # However, in the last case, a faster alternative is to use `CartesianCollection`:
221 # var cp = new CartesianCollection[Int]([xs] * 2)
222 # assert cp.to_a == cxs.to_a
225 # As seen in the examples, the patterns of the generated sequences produce a lexicographical order.
227 # Because it is a generator, it is memory-efficient and the sequences are created only when needed.
229 # Note: because it is a view, changes on the base collection are reflected on the view.
233 # cxs.are_sorted = true
234 # cxs.are_unique = true
235 # assert cxs.to_a == [[1,2]]
237 class CombinationCollection[E
]
238 super Collection[SequenceRead[E
]]
240 # The base collection used to generate the sequences.
241 var collection
: Collection[E
]
243 # The maximum length of each generated sequence.
251 # Are the elements in the generated sequences sorted?
254 # When `true`, the original order is preserved.
256 # Elements are compared by their order in the base collection,
257 # not by their intrinsic value or comparability.
261 # var cxs = new CombinationCollection[Int](xs, 2)
262 # cxs.are_sorted = true
263 # assert cxs.to_a == [[1,1], [1,2], [1, 2]]
264 # cxs.are_sorted = false
265 # assert cxs.to_a == [[1,1], [1,2], [1, 1], [1, 2], [2, 1], [2, 1]]
267 var are_sorted
= true is writable
269 # Are the element in the generated sequence unique?
272 # When `true`, an element cannot be reused in the same sequence (no replacement).
274 # Elements are distinguished by their order in the base collection,
275 # not by their intrinsic value or equality.
279 # var cxs = new CombinationCollection[Int](xs, 2)
280 # cxs.are_unique = true
281 # assert cxs.to_a == [[1,1], [1,2], [1, 2]]
282 # cxs.are_unique = false
283 # assert cxs.to_a == [[1,1], [1,1], [1,2], [1,1], [1,2], [2,2]]
285 var are_unique
= true is writable
289 var n
= collection
.length
295 return n
.factorial
/ repeat
.factorial
297 return n
.factorial
/ (n-repeat
).factorial
301 return (n
+repeat-1
).factorial
/ repeat
.factorial
/ (n-1
).factorial
308 redef fun iterator
do
309 return new CombinationIterator[E
](self)
313 private class CombinationIterator[E
]
314 super Iterator[SequenceRead[E
]]
315 var product
: CombinationCollection[E
]
317 var iterators
= new Array[Iterator[E
]]
318 var indices
= new Array[Int]
320 var are_sorted
: Bool is noinit
321 var are_unique
: Bool is noinit
325 are_sorted
= product
.are_sorted
326 are_unique
= product
.are_unique
328 for rank
in [0..product
.repeat
[ do
333 redef var is_ok
= true
337 var len
= product
.repeat
338 var res
= new Array[E
].with_capacity
(len
)
340 var it
= iterators
[i
]
348 var rank
= product
.repeat
- 1
351 var it
= iterators
[rank
]
353 if are_unique
and not are_sorted
then
354 var idx
= indices
[rank
] + 1
356 var adv
= next_free
(rank
, idx
)
357 for i
in [idx
..adv
[ do it
.next
364 if it
.is_ok
then break
372 for r
in [rank
+1..product
.repeat
[ do
377 fun next_free
(rank
: Int, start
: Int): Int
380 for i
in [0..rank
[ do
381 if indices
[i
] == start
then
391 fun reset_iterator
(rank
: Int): Iterator[E
]
393 var it
= product
.collection
.iterator
397 if (not are_sorted
and not are_unique
) or rank
== 0 then
399 else if are_sorted
and are_unique
then
400 skip
= indices
[rank-1
] + 1
401 else if are_sorted
then
402 skip
= indices
[rank-1
]
404 skip
= next_free
(rank
, 0)
407 for i
in [0..skip
[ do it
.next
409 if not it
.is_ok
then is_ok
= false
415 if not are_sorted
and not are_unique
then
417 else if are_sorted
and are_unique
then
420 if i
<= max
then return true
424 else if are_sorted
then
427 if i
< max
then return true
434 if indices
.count
(i
) > 1 then return true