# A view of some combinations over a base collections.
#
# This view *generates* some combinations and permutations on a collection.
#
# By default, the generated sequences are combinations:
#
# * each sequence has a length of `repeat`
# * elements are in sorted order (see `are_sorted` for details)
# * no repeated element (see `are_unique` for details)
#
# ~~~~
# var xs = [1, 2, 3]
# var cxs = new CombinationCollection[Int](xs, 2)
# assert cxs.length == 3
# assert cxs.to_a == [[1,2], [1,3], [2,3]]
# ~~~~
#
# Other kind of combinations can be generated by tweaking the attributes `are_sorted` and `are_unique`.
#
# * for permutation:
#
# ~~~~
# cxs.are_sorted = false
# cxs.are_unique = true
# assert cxs.length == 6
# assert cxs.to_a == [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
# ~~~~
#
# * for combinations with replacement:
#
# ~~~~
# cxs.are_sorted = true
# cxs.are_unique = false
# assert cxs.length == 6
# assert cxs.to_a == [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]
# ~~~~
#
# * for product:
#
# ~~~~
# cxs.are_sorted = false
# cxs.are_unique = false
# assert cxs.length == 9
# assert cxs.to_a == [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]
# ~~~~
#
# However, in the last case, a faster alternative is to use `CartesianCollection`:
#
# ~~~~
# var cp = new CartesianCollection[Int]([xs] * 2)
# assert cp.to_a == cxs.to_a
# ~~~~
#
# As seen in the examples, the patterns of the generated sequences produce a lexicographical order.
#
# Because it is a generator, it is memory-efficient and the sequences are created only when needed.
#
# Note: because it is a view, changes on the base collection are reflected on the view.
#
# ~~~~
# assert xs.pop == 3
# cxs.are_sorted = true
# cxs.are_unique = true
# assert cxs.to_a == [[1,2]]
# ~~~~
class CombinationCollection[E]
super Collection[SequenceRead[E]]
# The base collection used to generate the sequences.
var collection: Collection[E]
# The maximum length of each generated sequence.
var repeat: Int
init
do
assert repeat >= 0
end
# Are the elements in the generated sequences sorted?
# Default `true`.
#
# When `true`, the original order is preserved.
#
# Elements are compared by their order in the base collection,
# not by their intrinsic value or comparability.
#
# ~~~~
# var xs = [1, 1, 2]
# var cxs = new CombinationCollection[Int](xs, 2)
# cxs.are_sorted = true
# assert cxs.to_a == [[1,1], [1,2], [1, 2]]
# cxs.are_sorted = false
# assert cxs.to_a == [[1,1], [1,2], [1, 1], [1, 2], [2, 1], [2, 1]]
# ~~~~
var are_sorted = true is writable
# Are the element in the generated sequence unique?
# Default `true`.
#
# When `true`, an element cannot be reused in the same sequence (no replacement).
#
# Elements are distinguished by their order in the base collection,
# not by their intrinsic value or equality.
#
# ~~~~
# var xs = [1, 1, 2]
# var cxs = new CombinationCollection[Int](xs, 2)
# cxs.are_unique = true
# assert cxs.to_a == [[1,1], [1,2], [1, 2]]
# cxs.are_unique = false
# assert cxs.to_a == [[1,1], [1,1], [1,2], [1,1], [1,2], [2,2]]
# ~~~~
var are_unique = true is writable
redef fun length
do
var n = collection.length
if are_unique then
if repeat > n then
return 0
end
if are_sorted then
return n.factorial / repeat.factorial
else
return n.factorial / (n-repeat).factorial
end
else
if are_sorted then
return (n+repeat-1).factorial / repeat.factorial / (n-1).factorial
else
return n ** repeat
end
end
end
redef fun iterator do
return new CombinationIterator[E](self)
end
end
lib/combinations/combinations.nit:172,1--311,3