Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Combinations
AUTHORS:
- Mike Hansen (2007): initial implementation
- Vincent Delecroix (2011): cleaning, bug corrections, doctests
""" #***************************************************************************** # Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>, # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import from six.moves import range
from sage.interfaces.all import gap from sage.rings.all import ZZ, Integer from sage.arith.all import binomial from .combinat import CombinatorialClass from .integer_vector import IntegerVectors from sage.misc.misc import uniq
def Combinations(mset, k=None): """ Return the combinatorial class of combinations of the multiset ``mset``. If ``k`` is specified, then it returns the combinatorial class of combinations of ``mset`` of size ``k``.
A *combination* of a multiset `M` is an unordered selection of `k` objects of `M`, where every object can appear at most as many times as it appears in `M`.
The combinatorial classes correctly handle the cases where mset has duplicate elements.
EXAMPLES::
sage: C = Combinations(range(4)); C Combinations of [0, 1, 2, 3] sage: C.list() [[], [0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]] sage: C.cardinality() 16
::
sage: C2 = Combinations(range(4),2); C2 Combinations of [0, 1, 2, 3] of length 2 sage: C2.list() [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]] sage: C2.cardinality() 6
::
sage: Combinations([1,2,2,3]).list() [[], [1], [2], [3], [1, 2], [1, 3], [2, 2], [2, 3], [1, 2, 2], [1, 2, 3], [2, 2, 3], [1, 2, 2, 3]]
::
sage: Combinations([1,2,3], 2).list() [[1, 2], [1, 3], [2, 3]]
::
sage: mset = [1,1,2,3,4,4,5] sage: Combinations(mset,2).list() [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 4], [4, 5]]
::
sage: mset = ["d","a","v","i","d"] sage: Combinations(mset,3).list() [['d', 'd', 'a'], ['d', 'd', 'v'], ['d', 'd', 'i'], ['d', 'a', 'v'], ['d', 'a', 'i'], ['d', 'v', 'i'], ['a', 'v', 'i']]
::
sage: X = Combinations([1,2,3,4,5],3) sage: [x for x in X] [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
It is possible to take combinations of Sage objects::
sage: Combinations([vector([1,1]), vector([2,2]), vector([3,3])], 2).list() [[(1, 1), (2, 2)], [(1, 1), (3, 3)], [(2, 2), (3, 3)]]
TESTS:
We check that the code works even for non mutable objects::
sage: l = [vector((0,0)), vector((0,1))] sage: Combinations(l).list() [[], [(0, 0)], [(0, 1)], [(0, 0), (0, 1)]] """
#Check to see if everything in mset is unique else:
else: else: else:
class Combinations_mset(CombinatorialClass): def __init__(self, mset): """ TESTS::
sage: C = Combinations(range(4)) sage: C == loads(dumps(C)) True """
def __contains__(self, x): """ EXAMPLES::
sage: c = Combinations(range(4)) sage: all( i in c for i in c ) True sage: [3,4] in c False sage: [0,0] in c False """ except TypeError: return False
def __repr__(self): """ TESTS::
sage: repr(Combinations(range(4))) 'Combinations of [0, 1, 2, 3]' """
def __iter__(self): """ TESTS::
sage: Combinations(['a','a','b']).list() #indirect doctest [[], ['a'], ['b'], ['a', 'a'], ['a', 'b'], ['a', 'a', 'b']] """
def cardinality(self): """ TESTS::
sage: Combinations([1,2,3]).cardinality() 8 sage: Combinations(['a','a','b']).cardinality() 6 """
class Combinations_set(Combinations_mset): def __iter__(self): """ EXAMPLES::
sage: Combinations([1,2,3]).list() #indirect doctest [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] """
def unrank(self, r): """ EXAMPLES::
sage: c = Combinations([1,2,3]) sage: c.list() == list(map(c.unrank, range(c.cardinality()))) True """
def rank(self, x): """ EXAMPLES::
sage: c = Combinations([1,2,3]) sage: list(range(c.cardinality())) == list(map(c.rank, c)) True """
class Combinations_msetk(CombinatorialClass): def __init__(self, mset, k): """ TESTS::
sage: C = Combinations([1,2,3],2) sage: C == loads(dumps(C)) True """
def __contains__(self, x): """ EXAMPLES::
sage: c = Combinations(range(4),2) sage: all( i in c for i in c ) True sage: [0,1] in c True sage: [0,1,2] in c False sage: [3,4] in c False sage: [0,0] in c False """ except TypeError: return False
def __repr__(self): """ TESTS::
sage: repr(Combinations([1,2,2,3],2)) 'Combinations of [1, 2, 2, 3] of length 2' """
def __iter__(self): """ EXAMPLES::
sage: Combinations(['a','a','b'],2).list() # indirect doctest [['a', 'a'], ['a', 'b']] """
def cardinality(self): """ Returns the size of combinations(mset,k). IMPLEMENTATION: Wraps GAP's NrCombinations.
EXAMPLES::
sage: mset = [1,1,2,3,4,4,5] sage: Combinations(mset,2).cardinality() 12 """
class Combinations_setk(Combinations_msetk): def _iterator(self, items, len_items, n): """ An iterator for all the n-combinations of items.
EXAMPLES::
sage: it = Combinations([1,2,3,4],3)._iterator([1,2,3,4],4,3) sage: list(it) [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]] """ else:
def _iterator_zero(self): """ An iterator which just returns the empty list.
EXAMPLES::
sage: it = Combinations([1,2,3,4,5],3)._iterator_zero() sage: list(it) [[]] """
def __iter__(self): r""" Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124
EXAMPLES::
sage: Combinations([1,2,3,4,5],3).list() # indirect doctest [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]] """ else:
def list(self): """ EXAMPLES::
sage: Combinations([1,2,3,4,5],3).list() [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]] """
def unrank(self, r): """ EXAMPLES::
sage: c = Combinations([1,2,3], 2) sage: c.list() == list(map(c.unrank, range(c.cardinality()))) True """
def rank(self, x): """ EXAMPLES::
sage: c = Combinations([1,2,3], 2) sage: list(range(c.cardinality())) == list(map(c.rank, c.list())) True """
def rank(comb, n, check=True): """ Return the rank of ``comb`` in the subsets of ``range(n)`` of size ``k`` where ``k`` is the length of ``comb``.
The algorithm used is based on combinadics and James McCaffrey's MSDN article. See: :wikipedia:`Combinadic`.
EXAMPLES::
sage: import sage.combinat.combination as combination sage: combination.rank((), 3) 0 sage: combination.rank((0,), 3) 0 sage: combination.rank((1,), 3) 1 sage: combination.rank((2,), 3) 2 sage: combination.rank((0,1), 3) 0 sage: combination.rank((0,2), 3) 1 sage: combination.rank((1,2), 3) 2 sage: combination.rank((0,1,2), 3) 0
sage: combination.rank((0,1,2,3), 3) Traceback (most recent call last): ... ValueError: len(comb) must be <= n sage: combination.rank((0,0), 2) Traceback (most recent call last): ... ValueError: comb must be a subword of (0,1,...,n)
sage: combination.rank([1,2], 3) 2 sage: combination.rank([0,1,2], 3) 0 """
#Generate the combinadic from the #combination
#w = [n-1-comb[i] for i in range(k)]
#Calculate the integer that is the dual of #the lexicographic index of the combination
def _comb_largest(a,b,x): r""" Returns the largest `w < a` such that `binomial(w,b) <= x`.
EXAMPLES::
sage: from sage.combinat.combination import _comb_largest sage: _comb_largest(6,3,10) 5 sage: _comb_largest(6,3,5) 4 """
def from_rank(r, n, k): r""" Returns the combination of rank ``r`` in the subsets of ``range(n)`` of size ``k`` when listed in lexicographic order.
The algorithm used is based on combinadics and James McCaffrey's MSDN article. See: :wikipedia:`Combinadic`
EXAMPLES::
sage: import sage.combinat.combination as combination sage: combination.from_rank(0,3,0) () sage: combination.from_rank(0,3,1) (0,) sage: combination.from_rank(1,3,1) (1,) sage: combination.from_rank(2,3,1) (2,) sage: combination.from_rank(0,3,2) (0, 1) sage: combination.from_rank(1,3,2) (0, 2) sage: combination.from_rank(2,3,2) (1, 2) sage: combination.from_rank(0,3,3) (0, 1, 2) """ raise ValueError("k must be > 0") raise ValueError("k must be <= n")
########################################################## # Deprecations
class ChooseNK(Combinations_setk): def __setstate__(self, state): r""" For unpickling old ``ChooseNK`` objects.
TESTS::
sage: loads(b"x\x9ck`J.NLO\xd5K\xce\xcfM\xca\xccK,\xd1K\xce\xc8\xcf" ....: b"/N\x8d\xcf\xcb\xe6r\x06\xb3\xfc\xbc\xb9\n\x195\x1b\x0b" ....: b"\x99j\x0b\x995B\x99\xe2\xf3\nY :\x8a2\xf3\xd2\x8b\xf52" ....: b"\xf3JR\xd3S\x8b\xb8r\x13\xb3S\xe3a\x9cB\xd6PF\xd3\xd6\xa0" ....: b"B6\xa0\xfa\xecB\xf6\x0c \xd7\x08\xc8\xe5(M\xd2\x03\x00{" ....: b"\x82$\xd8") Combinations of [0, 1, 2, 3, 4] of length 2 """
from sage.structure.sage_object import register_unpickle_override register_unpickle_override("sage.combinat.choose_nk", "ChooseNK", ChooseNK) |