summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorVincent Delecroix <20100.delecroix at gmail.com>2012-07-20 11:36:24 +0000
committerFrédéric Chapoton <chapoton@math.univ-lyon1.fr>2014-06-06 13:51:32 +0200
commit48cd968c79718dbf13a5ce769dbdc3a2a16b0309 (patch)
tree324806b6b614bba542d03b4932c2f863d800fb7a
parentUpdated Sage version to 6.3.beta3 (diff)
trac 10534: Optimizations for the generation of subwords, subsets and set partitions
Make links to itertools + doc improvements for choose_nk.py, split_nk.py, subword.py, subset.py, set_partition_ordered.py and set_partition.py * call to itertools.combinations for enumeration * call to functions in sage.rings.arith for cardinality * random generation for the various submultisets * corrected error for Subwords([1,2,3],0).last() * add a default implementation for _an_element_ in CombinatorialClass * return Integer value (and not Python int, or Sage Rational) for cardinality method * test coverage up to 100%
-rw-r--r--src/sage/combinat/choose_nk.py189
-rw-r--r--src/sage/combinat/combination.py15
-rw-r--r--src/sage/combinat/split_nk.py63
-rw-r--r--src/sage/combinat/subset.py411
-rw-r--r--src/sage/combinat/subword.py287
5 files changed, 652 insertions, 313 deletions
diff --git a/src/sage/combinat/choose_nk.py b/src/sage/combinat/choose_nk.py
index bd84848..e863129 100644
--- a/src/sage/combinat/choose_nk.py
+++ b/src/sage/combinat/choose_nk.py
@@ -1,5 +1,12 @@
"""
Low-level Combinations
+
+AUTHORS:
+
+- Mike Hansen (2007): initial implementation
+
+- Vincent Delecroix (2011): call itertools for faster iteration, bug
+ corrections, doctests.
"""
#*****************************************************************************
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
@@ -19,14 +26,18 @@ import sage.misc.prandom as rnd
from sage.rings.arith import binomial
from sage.misc.misc import uniq
from combinat import CombinatorialClass
+import itertools
+from sage.rings.integer import Integer
class ChooseNK(CombinatorialClass):
"""
Low level combinatorial class of all possible choices of k elements out of
- range(n) without repetitions.
+ range(n) without repetitions. The elements of the output are tuples of
+ Python int (and not Sage Integer).
+
This is a low-level combinatorial class, with a simplistic interface by
- design. It aim at speed. It's element are returned as plain list of python
+ design. It aims at speed. It's element are returned as plain list of python
int.
EXAMPLES::
@@ -34,11 +45,11 @@ class ChooseNK(CombinatorialClass):
sage: from sage.combinat.choose_nk import ChooseNK
sage: c = ChooseNK(4,2)
sage: c.first()
- [0, 1]
+ (0, 1)
sage: c.list()
- [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
+ [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: type(c.list()[1])
- <type 'list'>
+ <type 'tuple'>
sage: type(c.list()[1][1])
<type 'int'>
"""
@@ -66,15 +77,36 @@ class ChooseNK(CombinatorialClass):
False
sage: [0,1,3] in c52
False
+
+ TESTS::
+
+ sage: from sage.combinat.choose_nk import ChooseNK
+ sage: c52 = ChooseNK(5,2)
+ sage: [0,2] in c52 # trac 10534
+ True
+ sage: [0,5] in c52
+ False
"""
try:
- x = list(x)
+ x = map(int,x)
except TypeError:
return False
- r = range(len(x))
- return all(i in r for i in x) and len(uniq(x)) == self._k
+ # test if the length is the good one
+ r = len(x)
+ if r != self._k:
+ return False
+ # test if there is any repetition
+ x = set(x)
+ if len(x) != r:
+ return False
+
+ # test if x is a subset of {0,1,...,n-1}
+ if x.difference(xrange(self._n)):
+ return False
+
+ return True
def cardinality(self):
"""
@@ -97,53 +129,19 @@ class ChooseNK(CombinatorialClass):
EXAMPLES::
sage: from sage.combinat.choose_nk import ChooseNK
- sage: [c for c in ChooseNK(5,2)]
- [[0, 1],
- [0, 2],
- [0, 3],
- [0, 4],
- [1, 2],
- [1, 3],
- [1, 4],
- [2, 3],
- [2, 4],
- [3, 4]]
+ sage: list(ChooseNK(5,2))
+ [(0, 1),
+ (0, 2),
+ (0, 3),
+ (0, 4),
+ (1, 2),
+ (1, 3),
+ (1, 4),
+ (2, 3),
+ (2, 4),
+ (3, 4)]
"""
- k = self._k
- n = self._n
- dif = 1
- if k == 0:
- yield []
- return
-
- if n < 1+(k-1)*dif:
- return
- else:
- subword = [ i*dif for i in range(k) ]
-
- yield subword[:]
- finished = False
-
- while not finished:
- #Find the biggest element that can be increased
- if subword[-1] < n-1:
- subword[-1] += 1
- yield subword[:]
- continue
-
- finished = True
- for i in reversed(range(k-1)):
- if subword[i]+dif < subword[i+1]:
- subword[i] += 1
- #Reset the bigger elements
- for j in range(1,k-i):
- subword[i+j] = subword[i]+j*dif
- yield subword[:]
- finished = False
- break
-
- return
-
+ return itertools.combinations(range(self._n), self._k)
def random_element(self):
"""
@@ -153,10 +151,13 @@ class ChooseNK(CombinatorialClass):
sage: from sage.combinat.choose_nk import ChooseNK
sage: ChooseNK(5,2).random_element()
- [0, 2]
+ (0, 2)
"""
- r = sorted(rnd.sample(xrange(self._n),self._k))
- return r
+ return tuple(rnd.sample(range(self._n), self._k))
+
+ # r.sort() removed in trac 10534
+ # it is not needed to sort because sage.misc.prandom.sample returns
+ # ordered subword
def unrank(self, r):
"""
@@ -168,7 +169,7 @@ class ChooseNK(CombinatorialClass):
True
"""
if r < 0 or r >= self.cardinality():
- raise ValueError("rank must be between 0 and %s (inclusive)"%(self.cardinality()-1))
+ raise ValueError("rank must be between 0 and %d (inclusive)"%(self.cardinality() - 1))
return from_rank(r, self._n, self._k)
def rank(self, x):
@@ -180,13 +181,13 @@ class ChooseNK(CombinatorialClass):
sage: range(c52.cardinality()) == map(c52.rank, c52)
True
"""
- if len(x) != self._k:
- return
+ if x not in self:
+ raise ValueError, "%s not in Choose(%d,%d)" %(str(x),self._n,self._k)
return rank(x, self._n)
-def rank(comb, n):
+def rank(comb, n, check=True):
"""
Returns the rank of comb in the subsets of range(n) of size k.
@@ -196,40 +197,52 @@ def rank(comb, n):
EXAMPLES::
sage: import sage.combinat.choose_nk as choose_nk
- sage: choose_nk.rank([], 3)
+ sage: choose_nk.rank((), 3)
0
- sage: choose_nk.rank([0], 3)
+ sage: choose_nk.rank((0,), 3)
0
- sage: choose_nk.rank([1], 3)
+ sage: choose_nk.rank((1,), 3)
1
- sage: choose_nk.rank([2], 3)
+ sage: choose_nk.rank((2,), 3)
2
- sage: choose_nk.rank([0,1], 3)
+ sage: choose_nk.rank((0,1), 3)
0
- sage: choose_nk.rank([0,2], 3)
+ sage: choose_nk.rank((0,2), 3)
1
- sage: choose_nk.rank([1,2], 3)
+ sage: choose_nk.rank((1,2), 3)
2
- sage: choose_nk.rank([0,1,2], 3)
+ sage: choose_nk.rank((0,1,2), 3)
0
- """
+ sage: choose_nk.rank((0,1,2,3), 3)
+ Traceback (most recent call last):
+ ...
+ ValueError: len(comb) must be <= n
+ sage: choose_nk.rank((0,0), 2)
+ Traceback (most recent call last):
+ ...
+ ValueError: comb must be a subword of (0,1,...,n)
+ """
k = len(comb)
- if k > n:
- raise ValueError("len(comb) must be <= n")
+ if check:
+ if k > n:
+ raise ValueError("len(comb) must be <= n")
+ comb = map(int, comb)
+ for i in xrange(k - 1):
+ if comb[i + 1] <= comb[i]:
+ raise ValueError("comb must be a subword of (0,1,...,n)")
#Generate the combinadic from the
#combination
- w = [0]*k
- for i in range(k):
- w[i] = (n-1) - comb[i]
+
+ #w = [n-1-comb[i] for i in xrange(k)]
#Calculate the integer that is the dual of
#the lexicographic index of the combination
r = k
t = 0
for i in range(k):
- t += binomial(w[i],r)
+ t += binomial(n - 1 - comb[i], r)
r -= 1
return binomial(n,k)-t-1
@@ -267,21 +280,21 @@ def from_rank(r, n, k):
sage: import sage.combinat.choose_nk as choose_nk
sage: choose_nk.from_rank(0,3,0)
- []
+ ()
sage: choose_nk.from_rank(0,3,1)
- [0]
+ (0,)
sage: choose_nk.from_rank(1,3,1)
- [1]
+ (1,)
sage: choose_nk.from_rank(2,3,1)
- [2]
+ (2,)
sage: choose_nk.from_rank(0,3,2)
- [0, 1]
+ (0, 1)
sage: choose_nk.from_rank(1,3,2)
- [0, 2]
+ (0, 2)
sage: choose_nk.from_rank(2,3,2)
- [1, 2]
+ (1, 2)
sage: choose_nk.from_rank(0,3,3)
- [0, 1, 2]
+ (0, 1, 2)
"""
if k < 0:
raise ValueError("k must be > 0")
@@ -290,17 +303,17 @@ def from_rank(r, n, k):
a = n
b = k
- x = binomial(n,k) - 1 - r # x is the 'dual' of m
+ x = binomial(n, k) - 1 - r # x is the 'dual' of m
comb = [None]*k
- for i in range(k):
+ for i in xrange(k):
comb[i] = _comb_largest(a,b,x)
x = x - binomial(comb[i], b)
a = comb[i]
b = b -1
- for i in range(k):
+ for i in xrange(k):
comb[i] = (n-1)-comb[i]
- return comb
+ return tuple(comb)
diff --git a/src/sage/combinat/combination.py b/src/sage/combinat/combination.py
index 09a2156..802c5ff 100644
--- a/src/sage/combinat/combination.py
+++ b/src/sage/combinat/combination.py
@@ -1,5 +1,12 @@
r"""
Combinations
+
+AUTHORS:
+
+- Mike Hansen (2007): initial implementation
+
+- Vincent Delecroix (2011): cleaning, bug corrections, doctests
+
"""
#*****************************************************************************
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
@@ -139,6 +146,14 @@ def Combinations(mset, k=None):
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)]]
"""
diff --git a/src/sage/combinat/split_nk.py b/src/sage/combinat/split_nk.py
index eb378c5..008d3fd 100644
--- a/src/sage/combinat/split_nk.py
+++ b/src/sage/combinat/split_nk.py
@@ -1,5 +1,11 @@
"""
Low-level splits
+
+Authors:
+
+- Mike Hansen (2007): original version
+
+- Vincent Delecroix (2011): improvements
"""
#*****************************************************************************
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
@@ -32,20 +38,20 @@ def SplitNK(n, k):
sage: S = SplitNK(5,2); S
Splits of {0, ..., 4} into a set of size 2 and one of size 3
sage: S.first()
- [[0, 1], [2, 3, 4]]
+ [(0, 1), (2, 3, 4)]
sage: S.last()
- [[3, 4], [0, 1, 2]]
+ [(3, 4), (0, 1, 2)]
sage: S.list()
- [[[0, 1], [2, 3, 4]],
- [[0, 2], [1, 3, 4]],
- [[0, 3], [1, 2, 4]],
- [[0, 4], [1, 2, 3]],
- [[1, 2], [0, 3, 4]],
- [[1, 3], [0, 2, 4]],
- [[1, 4], [0, 2, 3]],
- [[2, 3], [0, 1, 4]],
- [[2, 4], [0, 1, 3]],
- [[3, 4], [0, 1, 2]]]
+ [[(0, 1), (2, 3, 4)],
+ [(0, 2), (1, 3, 4)],
+ [(0, 3), (1, 2, 4)],
+ [(0, 4), (1, 2, 3)],
+ [(1, 2), (0, 3, 4)],
+ [(1, 3), (0, 2, 4)],
+ [(1, 4), (0, 2, 3)],
+ [(2, 3), (0, 1, 4)],
+ [(2, 4), (0, 1, 3)],
+ [(3, 4), (0, 1, 2)]]
"""
return SplitNK_nk(n,k)
@@ -62,12 +68,12 @@ class SplitNK_nk(CombinatorialClass):
self._n = n
self._k = k
- def __repr__(self):
+ def _repr_(self):
"""
TESTS::
sage: from sage.combinat.split_nk import SplitNK
- sage: repr(SplitNK(5,2))
+ sage: repr(SplitNK(5,2)) #indirect doctest
'Splits of {0, ..., 4} into a set of size 2 and one of size 3'
"""
return "Splits of {0, ..., %s} into a set of size %s and one of size %s"%(self._n-1, self._k, self._n-self._k)
@@ -93,22 +99,21 @@ class SplitNK_nk(CombinatorialClass):
EXAMPLES::
sage: from sage.combinat.split_nk import SplitNK
- sage: [c for c in SplitNK(5,2)]
- [[[0, 1], [2, 3, 4]],
- [[0, 2], [1, 3, 4]],
- [[0, 3], [1, 2, 4]],
- [[0, 4], [1, 2, 3]],
- [[1, 2], [0, 3, 4]],
- [[1, 3], [0, 2, 4]],
- [[1, 4], [0, 2, 3]],
- [[2, 3], [0, 1, 4]],
- [[2, 4], [0, 1, 3]],
- [[3, 4], [0, 1, 2]]]
+ sage: for c in SplitNK(5,2): print c
+ [(0, 1), (2, 3, 4)]
+ [(0, 2), (1, 3, 4)]
+ [(0, 3), (1, 2, 4)]
+ [(0, 4), (1, 2, 3)]
+ [(1, 2), (0, 3, 4)]
+ [(1, 3), (0, 2, 4)]
+ [(1, 4), (0, 2, 3)]
+ [(2, 3), (0, 1, 4)]
+ [(2, 4), (0, 1, 3)]
+ [(3, 4), (0, 1, 2)]
"""
range_n = range(self._n)
for kset in choose_nk.ChooseNK(self._n,self._k):
- yield [ kset, filter(lambda x: x not in kset, range_n) ]
-
+ yield [ kset, tuple(filter(lambda x: x not in kset, range_n))]
def random_element(self):
"""
@@ -119,11 +124,11 @@ class SplitNK_nk(CombinatorialClass):
sage: from sage.combinat.split_nk import SplitNK
sage: SplitNK(5,2).random_element()
- [[0, 2], [1, 3, 4]]
+ [(0, 2), (1, 3, 4)]
"""
r = rnd.sample(xrange(self._n),self._n)
r0 = r[:self._k]
r1 = r[self._k:]
r0.sort()
r1.sort()
- return [ r0, r1 ]
+ return [ tuple(r0), tuple(r1) ]
diff --git a/src/sage/combinat/subset.py b/src/sage/combinat/subset.py
index 1a7acb5..d236971 100644
--- a/src/sage/combinat/subset.py
+++ b/src/sage/combinat/subset.py
@@ -1,9 +1,9 @@
r"""
Subsets
-The combinatorial class of the subsets of a finite set. The set can
-be given as a list or a Set or else as an integer `n` which encodes the set
-`\{1,2,...,n\}`. See :class:`Subsets` for more information and examples.
+The set of subsets of a finite set. The set can be given as a list or a Set
+or else as an integer `n` which encodes the set `\{1,2,...,n\}`.
+See :class:`Subsets` for more information and examples.
AUTHORS:
@@ -11,6 +11,8 @@ AUTHORS:
- Florent Hivert (2009/02/06): doc improvements + new methods
+- Vincent Delecroix (2011/03/10): use iterator from itertools, implement basic
+ random uniform generation
"""
#*****************************************************************************
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
@@ -34,22 +36,23 @@ import sage.combinat.subword as subword
import sage.combinat.choose_nk as choose_nk
import sage.misc.prandom as rnd
import __builtin__
+import copy
import itertools
-from combinat import CombinatorialClass
+from sage.structure.parent import Parent
+from sage.structure.element import Element
from sage.sets.set import Set_object_enumerated
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
-
+from combinat import CombinatorialClass
def Subsets(s, k=None, submultiset=False):
"""
- Returns the combinatorial class of the subsets of the finite set
- s. The set can be given as a list, Set or any iterable convertible
- to a set. It can alternatively be given a non-negative integer `n`
- which encode the set `\{1,2,\dots,n\}` (i.e. the Sage
- ``range(1,s+1)``).
+ Returns the combinatorial class of the subsets of the finite set ``s``. The
+ set can be given as a list, Set or any iterable convertible to a set. It can
+ alternatively be given a non-negative integer `n` which encode the set
+ `\{1,2,\dots,n\}` (i.e. the Sage ``range(1,s+1)``).
- A second optional parameter k can be given. In this case, Subsets returns
- the combinatorial class of subsets of s of size k.
+ A second optional parameter ``k`` can be given. In this case, Subsets
+ returns the combinatorial class of subsets of ``s`` of size ``k``.
Finally the option ``submultiset`` allows one to deal with sets with
repeated elements usually called multisets.
@@ -96,7 +99,7 @@ def Subsets(s, k=None, submultiset=False):
[['a', 'a'], ['a', 'b'], ['b', 'b']]
"""
if k is not None:
- k=Integer(k)
+ k = Integer(k)
if isinstance(s, (int, Integer)):
if s < 0:
@@ -117,11 +120,8 @@ def Subsets(s, k=None, submultiset=False):
else:
return Subsets_sk(s, k)
-
-
-
-
class Subsets_s(CombinatorialClass):
+ element_class = Set_object_enumerated
def __init__(self, s):
"""
TESTS::
@@ -141,14 +141,14 @@ class Subsets_s(CombinatorialClass):
sage: S = sage.sets.set.Set_object_enumerated([1,2])
sage: TestSuite(S).run() # todo: not implemented
"""
- CombinatorialClass.__init__(self, category=FiniteEnumeratedSets())
+ Parent.__init__(self, category=FiniteEnumeratedSets())
self.s = Set(s)
- def __repr__(self):
+ def _repr_(self):
"""
TESTS::
- sage: repr(Subsets([1,2,3]))
+ sage: repr(Subsets([1,2,3])) #indirect doctest
'Subsets of {1, 2, 3}'
"""
return "Subsets of %s"%self.s
@@ -186,7 +186,7 @@ class Subsets_s(CombinatorialClass):
sage: Subsets(3).cardinality()
8
"""
- return Integer(2**len(self.s))
+ return Integer(2**self.s.cardinality())
def first(self):
"""
@@ -216,7 +216,6 @@ class Subsets_s(CombinatorialClass):
"""
return self.s
-
def __iter__(self):
"""
Iterates through the subsets of s.
@@ -231,12 +230,9 @@ class Subsets_s(CombinatorialClass):
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
"""
- lset = __builtin__.list(self.s)
- #We use the iterator for the subwords of range(len(self.s))
- ind_set = lambda index_list: Set([lset[i] for i in index_list])
- it = itertools.imap(ind_set, subword.Subwords(range(len(lset))))
- for sub in it:
- yield sub
+ for k in xrange(self.s.cardinality()+1):
+ for ss in Subsets_sk(self.s, k):
+ yield ss
def random_element(self):
"""
@@ -251,7 +247,6 @@ class Subsets_s(CombinatorialClass):
{5}
"""
lset = __builtin__.list(self.s)
- n = len(self.s)
return Set(filter(lambda x: rnd.randint(0,1), lset))
def rank(self, sub):
@@ -310,6 +305,19 @@ class Subsets_s(CombinatorialClass):
else:
return Set([lset[i] for i in choose_nk.from_rank(r, n, k)])
+ def _element_constructor(self,X):
+ """
+ TESTS::
+
+ sage: S3 = Subsets(3); S3([1,2]) #indirect doctest
+ {1, 2}
+ sage: S3([0,1,2])
+ Traceback (most recent call last):
+ ...
+ ValueError: [0, 1, 2] not in Subsets of {1, 2, 3}
+ """
+ return Set(X)
+
def _an_element_(self):
"""
Returns an example of subset.
@@ -325,23 +333,8 @@ class Subsets_s(CombinatorialClass):
"""
return self.unrank(self.cardinality() // 2)
- def _element_constructor_(self, x):
- """
- TESTS::
-
- sage: S3 = Subsets(3); S3([1,2])
- {1, 2}
- sage: S3([0,1,2])
- Traceback (most recent call last):
- ...
- ValueError: [0, 1, 2] not in Subsets of {1, 2, 3}
- """
- return Set(x)
-
- element_class = Set_object_enumerated
-
-
-class Subsets_sk(CombinatorialClass):
+#TODO: remove inheritance
+class Subsets_sk(Subsets_s):
def __init__(self, s, k):
"""
TESTS::
@@ -358,18 +351,19 @@ class Subsets_sk(CombinatorialClass):
sage: S = Subsets(3,2)
sage: TestSuite(S).run(skip=["_test_elements"])
"""
- CombinatorialClass.__init__(self, category=FiniteEnumeratedSets())
- self.s = Set(s)
- self.k = k
+ Subsets_s.__init__(self,s)
+ self._k = Integer(k)
+ if self._k < 0:
+ raise ValueError, "the integer k (=%d) should be non-negative" %k
- def __repr__(self):
+ def _repr_(self):
"""
TESTS::
- sage: repr(Subsets(3,2))
+ sage: repr(Subsets(3,2)) #indirect doctest
'Subsets of {1, 2, 3} of size 2'
"""
- return "Subsets of %s of size %s"%(self.s, self.k)
+ return Subsets_s._repr_(self) + " of size %s"%(self._k)
def __contains__(self, value):
"""
@@ -382,13 +376,7 @@ class Subsets_sk(CombinatorialClass):
sage: Set([]) in S
False
"""
- value = Set(value)
- if len(value) != self.k:
- return False
- for v in value:
- if not v in self.s:
- return False
- return True
+ return len(value) == self._k and Subsets_s.__contains__(self,value)
def cardinality(self):
"""
@@ -411,11 +399,9 @@ class Subsets_sk(CombinatorialClass):
sage: Subsets(3,4).cardinality()
0
"""
- if self.k not in range(len(self.s)+1):
- return 0
- else:
- return binomial(len(self.s),self.k)
-
+ if self._k > self.s.cardinality():
+ return Integer(0)
+ return binomial(self.s.cardinality(),self._k)
def first(self):
"""
@@ -431,12 +417,10 @@ class Subsets_sk(CombinatorialClass):
{1, 2}
sage: Subsets(3,4).first()
"""
- if self.k not in range(len(self.s)+1):
+ if self._k < 0 or self._k > len(self.s):
return None
else:
- return Set(__builtin__.list(self.s)[:self.k])
-
-
+ return Set(__builtin__.list(self.s)[:self._k])
def last(self):
"""
@@ -452,13 +436,24 @@ class Subsets_sk(CombinatorialClass):
{2, 3}
sage: Subsets(3,4).last()
"""
- if self.k not in range(len(self.s)+1):
+ if self._k not in range(len(self.s)+1):
return None
else:
- return Set(__builtin__.list(self.s)[-self.k:])
+ return Set(__builtin__.list(self.s)[-self._k:])
+ def _fast_iterator(self):
+ r"""
+ Iterate through the subsets of size k if s.
+
+ Beware that this function yield tuples and not sets. If you need sets
+ use __iter__
+ EXAMPLES::
+ sage: list(Subsets(range(3), 2)._fast_iterator())
+ [(0, 1), (0, 2), (1, 2)]
+ """
+ return itertools.combinations(self.s,self._k)
def __iter__(self):
"""
@@ -466,23 +461,16 @@ class Subsets_sk(CombinatorialClass):
EXAMPLES::
- sage: [sub for sub in Subsets(Set([1,2,3]), 2)]
+ sage: Subsets(Set([1,2,3]), 2).list()
[{1, 2}, {1, 3}, {2, 3}]
- sage: [sub for sub in Subsets([1,2,3,3], 2)]
+ sage: Subsets([1,2,3,3], 2).list()
[{1, 2}, {1, 3}, {2, 3}]
- sage: [sub for sub in Subsets(3,2)]
+ sage: Subsets(3,2).list()
[{1, 2}, {1, 3}, {2, 3}]
+ sage: Subsets(3,3).list()
+ [{1, 2, 3}]
"""
- if self.k not in range(len(self.s)+1):
- return
-
- lset = __builtin__.list(self.s)
- #We use the iterator for the subwords of range(len(self.s))
- ind_set = lambda index_list: Set([lset[i] for i in index_list])
- for sub in choose_nk.ChooseNK(len(lset),self.k):
- yield ind_set(sub)
-
-
+ return itertools.imap(Set_object_enumerated, self._fast_iterator())
def random_element(self):
"""
@@ -499,10 +487,10 @@ class Subsets_sk(CombinatorialClass):
lset = __builtin__.list(self.s)
n = len(self.s)
- if self.k not in range(len(self.s)+1):
+ if self._k not in range(len(self.s)+1):
return None
else:
- return Set([lset[i] for i in choose_nk.ChooseNK(n, self.k).random_element()])
+ return Set([lset[i] for i in choose_nk.ChooseNK(n, self._k).random_element()])
def rank(self, sub):
"""
@@ -529,14 +517,13 @@ class Subsets_sk(CombinatorialClass):
n = len(self.s)
r = 0
- if self.k not in range(len(self.s)+1):
+ if self._k not in range(len(self.s)+1):
return None
- elif self.k != len(subset):
+ elif self._k != len(subset):
return None
else:
return choose_nk.rank(index_list,n)
-
def unrank(self, r):
"""
Returns the subset of s that has rank k.
@@ -552,12 +539,12 @@ class Subsets_sk(CombinatorialClass):
lset = __builtin__.list(self.s)
n = len(lset)
- if self.k not in range(len(self.s)+1):
+ if self._k not in range(len(self.s)+1):
return None
elif r >= self.cardinality() or r < 0:
return None
else:
- return Set([lset[i] for i in choose_nk.from_rank(r, n, self.k)])
+ return Set([lset[i] for i in choose_nk.from_rank(r, n, self._k)])
def _an_element_(self):
"""
@@ -578,7 +565,7 @@ class Subsets_sk(CombinatorialClass):
"""
TESTS::
- sage: S32 = Subsets(3,2); S32([1,2])
+ sage: S32 = Subsets(3,2); S32([1,2]) #indirect doctest
{1, 2}
sage: S32([0,1,2])
Traceback (most recent call last):
@@ -587,8 +574,42 @@ class Subsets_sk(CombinatorialClass):
"""
return Set(x)
- element_class = Set_object_enumerated
+#TODO: MultiSet data structure in Sage
+
+def dict_to_list(d):
+ r"""
+ Return a list whose elements are the elements of i of d repeated with
+ multiplicity d[i].
+
+ EXAMPLES::
+
+ sage: from sage.combinat.subset import dict_to_list
+ sage: dict_to_list({'a':1, 'b':3})
+ ['a', 'b', 'b', 'b']
+ """
+ l = []
+ for i,j in d.iteritems():
+ l.extend([i]*j)
+ return l
+
+def list_to_dict(l):
+ r"""
+ Return a dictionnary whose keys are the elements of l and values are the
+ multiplicity they appear in l.
+
+ EXAMPLES::
+
+ sage: from sage.combinat.subset import list_to_dict
+ sage: list_to_dict(['a', 'b', 'b', 'b'])
+ {'a': 1, 'b': 3}
+ """
+ d = {}
+ for elt in l:
+ if elt not in d:
+ d[elt] = 0
+ d[elt] += 1
+ return d
class SubMultiset_s(CombinatorialClass):
"""
@@ -597,21 +618,12 @@ class SubMultiset_s(CombinatorialClass):
EXAMPLES::
sage: S = Subsets([1,2,2,3], submultiset=True)
- sage: S._s
- [1, 2, 2, 3]
- The positions of the unique elements in s are stored in::
+ The positions of the unique elements in s are stored in the attribute
+ ``._d``::
- sage: S._indices
- [0, 1, 3]
-
- and their multiplicities in::
-
- sage: S._multiplicities
- [1, 2, 1]
- sage: Subsets([1,2,3,3], submultiset=True).cardinality()
- 12
- sage: TestSuite(S).run()
+ sage: S._d
+ {1: 1, 2: 2, 3: 1}
"""
def __init__(self, s):
"""
@@ -622,26 +634,22 @@ class SubMultiset_s(CombinatorialClass):
sage: S = Subsets([1,2,2,3], submultiset=True)
sage: Subsets([1,2,3,3], submultiset=True).cardinality()
12
+ sage: TestSuite(S).run()
"""
CombinatorialClass.__init__(self, category=FiniteEnumeratedSets())
- s = sorted(list(s))
- indices = list(sorted(Set([s.index(a) for a in s])))
- multiplicities = [len([a for a in s if a == s[i]])
- for i in indices]
+ self._d = s
+ if not isinstance(s, dict):
+ self._d = list_to_dict(s)
- self._s = s
- self._indices = indices
- self._multiplicities = multiplicities
-
- def __repr__(self):
+ def _repr_(self):
"""
TESTS::
- sage: S = Subsets([1, 2, 2, 3], submultiset=True); S
+ sage: S = Subsets([1, 2, 2, 3], submultiset=True); S #indirect doctest
SubMultiset of [1, 2, 2, 3]
"""
- return "SubMultiset of %s"%self._s
+ return "SubMultiset of %s"%dict_to_list(self._d)
def __contains__(self, s):
"""
@@ -661,11 +669,88 @@ class SubMultiset_s(CombinatorialClass):
sage: [4] in S
False
"""
- return sorted(s) in subword.Subwords(self._s)
+ dd = {}
+ for elt in s:
+ if elt in dd:
+ dd[elt] += 1
+ if dd[elt] > self._d[elt]:
+ return False
+ elif elt not in self._d:
+ return False
+ else:
+ dd[elt] = 1
+ return True
+
+ def cardinality(self):
+ r"""
+ Return the cardinality of self
+
+ EXAMPLES::
+
+ sage: S = Subsets([1,1,2,3],submultiset=True)
+ sage: S.cardinality()
+ 12
+ sage: len(S.list())
+ 12
+
+ sage: S = Subsets([1,1,2,2,3],submultiset=True)
+ sage: S.cardinality()
+ 18
+ sage: len(S.list())
+ 18
+
+ sage: S = Subsets([1,1,1,2,2,3],submultiset=True)
+ sage: S.cardinality()
+ 24
+ sage: len(S.list())
+ 24
+ """
+ from sage.all import prod
+ return Integer(prod(k+1 for k in self._d.values()))
+
+ def random_element(self):
+ r"""
+ Return a random element of self with uniform law
+
+ EXAMPLES::
+
+ sage: S = Subsets([1,1,2,3], submultiset=True)
+ sage: S.random_element()
+ [2]
+ """
+ l = []
+ for i in self._d:
+ l.extend([i]*rnd.randint(0,self._d[i]))
+ return l
+
+ def generating_serie(self,variable='x'):
+ r"""
+ Return the serie (here a polynom) associated to the counting of the
+ element of self weighted by the number of element they contain.
+
+ EXAMPLES::
+
+ sage: Subsets([1,1],submultiset=True).generating_serie()
+ x^2 + x + 1
+ sage: Subsets([1,1,2,3],submultiset=True).generating_serie()
+ x^4 + 3*x^3 + 4*x^2 + 3*x + 1
+ sage: Subsets([1,1,1,2,2,3,3,4],submultiset=True).generating_serie()
+ x^8 + 4*x^7 + 9*x^6 + 14*x^5 + 16*x^4 + 14*x^3 + 9*x^2 + 4*x + 1
+
+ sage: S = Subsets([1,1,1,2,2,3,3,4],submultiset=True)
+ sage: S.cardinality()
+ 72
+ sage: sum(S.generating_serie())
+ 72
+ """
+ from sage.rings.integer_ring import ZZ
+ from sage.all import prod
+ R = ZZ[variable]
+ return prod(R([1]*(n+1)) for n in self._d.values())
def __iter__(self):
"""
- Iterates through the subsets of the multiset ``self._s``. Note
+ Iterates through the subsets of the multiset ``self.s``. Note
that each subset is represented by a list of its elements rather than
a set since we can have multiplicities (no multiset data structure yet
in sage).
@@ -688,11 +773,10 @@ class SubMultiset_s(CombinatorialClass):
[1, 2, 2, 3]]
"""
- for k in range(len(self._s)+1):
- for s in SubMultiset_sk(self._s, k):
+ for k in range(sum(self._d.values())+1):
+ for s in SubMultiset_sk(self._d, k):
yield s
-
class SubMultiset_sk(SubMultiset_s):
"""
The combinatorial class of the subsets of size k of a multiset s. Note
@@ -702,7 +786,7 @@ class SubMultiset_sk(SubMultiset_s):
EXAMPLES::
- sage: S = Subsets([1,2,3,3],2, submultiset=True)
+ sage: S = Subsets([1,2,3,3],2,submultiset=True)
sage: S._k
2
sage: S.cardinality()
@@ -713,27 +797,74 @@ class SubMultiset_sk(SubMultiset_s):
[3, 3]
sage: [sub for sub in S]
[[1, 2], [1, 3], [2, 3], [3, 3]]
- sage: TestSuite(S).run()
"""
def __init__(self, s, k):
"""
- TEST::
+ TESTS::
- sage: S = Subsets([1,2,3,3],2, submultiset=True)
+ sage: S = Subsets([1,2,3,3],2,submultiset=True)
sage: [sub for sub in S]
[[1, 2], [1, 3], [2, 3], [3, 3]]
+ sage: TestSuite(S).run()
"""
SubMultiset_s.__init__(self, s)
+ self._l = dict_to_list(self._d)
self._k = k
- def __repr__(self):
+ def generating_serie(self,variable='x'):
+ r"""
+ Return the serie (this case a polynom) associated to the counting of the
+ element of self weighted by the number of element they contains
+
+ EXAMPLES::
+
+ sage: x = ZZ['x'].gen()
+ sage: l = [1,1,1,1,2,2,3]
+ sage: for k in xrange(len(l)):
+ ... S = Subsets(l,k,submultiset=True)
+ ... print S.generating_serie(x) == S.cardinality()*x**k
+ True
+ True
+ True
+ True
+ True
+ True
+ True
+ """
+ from sage.all import ZZ
+ x = ZZ[variable].gen()
+ P = SubMultiset_s.generating_serie(self)
+ return P[self._k] * (x**self._k)
+
+ def cardinality(self):
+ r"""
+ Return the cardinality of self
+
+ EXAMPLES::
+
+ sage: S = Subsets([1,2,2,3,3,3],4,submultiset=True)
+ sage: S.cardinality()
+ 5
+ sage: len(list(S))
+ 5
+
+ sage: S = Subsets([1,2,2,3,3,3],3,submultiset=True)
+ sage: S.cardinality()
+ 6
+ sage: len(list(S))
+ 6
+ """
+ return Integer(sum(1 for _ in self))
+
+ def _repr_(self):
"""
TESTS::
- sage: S = Subsets([1, 2, 2, 3], 3, submultiset=True); S
- SubMultiset of [1, 2, 2, 3] of size 3
+ sage: S = Subsets([1, 2, 2, 3], 3, submultiset=True)
+ sage: repr(S) #indirect doctest
+ 'SubMultiset of [1, 2, 2, 3] of size 3'
"""
- return "SubMultiset of %s of size %s"%(self._s, self._k)
+ return "%s of size %s"%(SubMultiset_s._repr_(self), self._k)
def __contains__(self, s):
"""
@@ -755,12 +886,25 @@ class SubMultiset_sk(SubMultiset_s):
sage: [3, 3] in S
False
"""
- return sorted(s) in subword.Subwords(self._s, self._k)
+ return len(s) == self._k and SubMultiset_s.__contains__(self, s)
+
+ def random_element(self):
+ r"""
+ Return a random submultiset of given length
+
+ EXAMPLES::
+
+ sage: Subsets(7,3).random_element()
+ {1, 4, 7}
+ sage: Subsets(7,5).random_element()
+ {1, 3, 4, 5, 7}
+ """
+ return rnd.sample(self._l, self._k)
def __iter__(self):
"""
Iterates through the subsets of size ``self._k`` of the multiset
- ``self._s``. Note that each subset is represented by a list of the
+ ``self.s``. Note that each subset is represented by a list of the
elements rather than a set since we can have multiplicities (no
multiset data structure yet in sage).
@@ -771,6 +915,7 @@ class SubMultiset_sk(SubMultiset_s):
[[1, 2], [1, 3], [2, 2], [2, 3]]
"""
from sage.combinat.integer_vector import IntegerVectors
- for iv in IntegerVectors(self._k, len(self._indices), outer=self._multiplicities):
- yield sum([ [self._s[self._indices[i]]]*iv[i] for i in range(len(iv))], [])
+ elts = self._d.keys()
+ for iv in IntegerVectors(self._k, len(self._d), outer=self._d.values()):
+ yield sum([ [elts[i]]*iv[i] for i in range(len(iv))], [])
diff --git a/src/sage/combinat/subword.py b/src/sage/combinat/subword.py
index 644a670..205cce9 100644
--- a/src/sage/combinat/subword.py
+++ b/src/sage/combinat/subword.py
@@ -1,7 +1,7 @@
r"""
Subwords
-A subword of a word $w$ is a word obtained by deleting the letters at some
+A subword of a word `w` is a word obtained by deleting the letters at some
(non necessarily adjacent) positions in `w`. It is not to be confused with the
notion of factor where one keeps adjacent positions in `w`. Sometimes it is
useful to allow repeated uses of the same letter of `w` in a "generalized"
@@ -21,7 +21,18 @@ For example:
- "nnu" is a subword with repetitions of "bonjour";
-A word can be given either as a string or as a list.
+A word can be given either as a string, as a list or as a tuple.
+
+
+As repetition can occur in the initial word, the subwords of a given words is
+not a set in general but an enumerated multiset!
+
+TODO:
+
+- implement subwords with repetitions
+
+- implement the category of EnumeratedMultiset and inheritate from when needed
+ (ie the initial word has repeated letters)
AUTHORS:
@@ -29,7 +40,8 @@ AUTHORS:
- Florent Hivert (2009/02/06): doc improvements + new methods + bug fixes
-
+- Vincent Delecroix (2011/10/03): link to itertools for faster generation,
+ documentation, random generation, improvements
"""
#*****************************************************************************
@@ -47,16 +59,19 @@ AUTHORS:
# http://www.gnu.org/licenses/
#*****************************************************************************
-import sage.combinat.combination as combination
-from sage.rings.arith import factorial
+from sage.structure.parent import Parent
+
+import sage.rings.arith as arith
+import sage.misc.prandom as prandom
+from sage.rings.integer import Integer
import itertools
+import choose_nk
from combinat import CombinatorialClass
-
def Subwords(w, k=None):
"""
- Returns the combinatorial class of subwords of w. The word w can be given
- by either a string or a list.
+ Returns the set of subwords of w. The word w can be given by either a
+ string, a list or a tuple.
If k is specified, then it returns the combinatorial class of
subwords of w of length k.
@@ -72,41 +87,99 @@ def Subwords(w, k=None):
sage: S.list()
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
- ::
+ The same example using string::
+
+ sage: S = Subwords('abc'); S
+ Subwords of abc
+ sage: S.first()
+ ''
+ sage: S.last()
+ 'abc'
+ sage: S.list()
+ ['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
+
+ The same example using tuple::
+
+ sage: S = Subwords((1,2,3)); S
+ Subwords of (1, 2, 3)
+ sage: S.first()
+ ()
+ sage: S.last()
+ (1, 2, 3)
+ sage: S.list()
+ [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
+
+ Using word with specified length::
sage: S = Subwords(['a','b','c'], 2); S
Subwords of ['a', 'b', 'c'] of length 2
sage: S.list()
[['a', 'b'], ['a', 'c'], ['b', 'c']]
"""
+ datatype = type(w) # 'datatype' is the type of w
+ if datatype not in [str, list, tuple]:
+ raise ValueError("datatype should be str, list or tuple")
+
+ build = datatype
+ # 'build' is a method to build an element with the same type as
+ # the one of w.
+ if datatype == str:
+ build = lambda x: ''.join(x)
+
if k is None:
return Subwords_w(w)
else:
- if k not in range(0, len(w)+1):
- raise ValueError("k must be between 0 and %s"%len(w))
+ if not isinstance(k, (int, Integer)):
+ raise ValueError("k should be an integer")
+ if k < 0 or k > len(w):
+ return FiniteEnumeratedSet([])
else:
- return Subwords_wk(w,k)
+ return Subwords_wk(w, k, build)
class Subwords_w(CombinatorialClass):
- def __init__(self, w):
+ r"""
+ Subwords of a given word
+ """
+ def __init__(self, w, build):
"""
TESTS::
sage: S = Subwords([1,2,3])
sage: S == loads(dumps(S))
True
+ sage: TestSuite(S).run()
+ """
+ CombinatorialClass.__init__(self)
+ self._w = w # the word
+ self._build = build # how to build an element with same type as w
+
+ def __reduce__(self):
+ r"""
+ Pickle (how to construct back the object)
+
+ TESTS::
+
+ sage: S = Subwords((1,2,3))
+ sage: S == loads(dumps(S))
+ True
+ sage: S = Subwords('123')
+ sage: S == loads(dumps(S))
+ True
+ sage: S = Subwords(('a',(1,2,3),('a','b'),'ir'))
+ sage: S == loads(dumps(S))
+ True
"""
- self.w = w
+ return (Subwords, (self._w,))
def __repr__(self):
"""
TESTS::
- sage: repr(Subwords([1,2,3]))
+ sage: repr(Subwords([1,2,3])) # indirect doctest
'Subwords of [1, 2, 3]'
"""
- return "Subwords of %s"%self.w
+ return "Subwords of %s" % str(self._w)
def __contains__(self, w):
"""
@@ -116,18 +189,18 @@ class Subwords_w(CombinatorialClass):
True
sage: [2,3,3,4] in Subwords([1,2,3,4,3,4,4])
True
- sage: [5, 5, 3] in Subwords([1, 3, 3, 5, 4, 5, 3, 5])
+ sage: [5,5,3] in Subwords([1,3,3,5,4,5,3,5])
True
- sage: [3, 5, 5, 3] in Subwords([1, 3, 3, 5, 4, 5, 3, 5])
+ sage: [3,5,5,3] in Subwords([1,3,3,5,4,5,3,5])
True
- sage: [3, 5, 5, 3, 4] in Subwords([1, 3, 3, 5, 4, 5, 3, 5])
+ sage: [3,5,5,3,4] in Subwords([1,3,3,5,4,5,3,5])
False
sage: [2,3,3,4] in Subwords([1,2,3,4,3,4,4])
True
sage: [2,3,3,1] in Subwords([1,2,3,4,3,4,4])
False
"""
- if smallest_positions(self.w, w) != False:
+ if smallest_positions(self._w, w) != False:
return True
return False
@@ -138,7 +211,7 @@ class Subwords_w(CombinatorialClass):
sage: Subwords([1,2,3]).cardinality()
8
"""
- return 2**len(self.w)
+ return Integer(2)**len(self._w)
def first(self):
"""
@@ -146,8 +219,12 @@ class Subwords_w(CombinatorialClass):
sage: Subwords([1,2,3]).first()
[]
+ sage: Subwords((1,2,3)).first()
+ ()
+ sage: Subwords('123').first()
+ ''
"""
- return []
+ return self._build([])
def last(self):
"""
@@ -155,42 +232,84 @@ class Subwords_w(CombinatorialClass):
sage: Subwords([1,2,3]).last()
[1, 2, 3]
+ sage: Subwords((1,2,3)).last()
+ (1, 2, 3)
+ sage: Subwords('123').last()
+ '123'
"""
- return self.w
+ return self._w
+
+ def random_element(self):
+ r"""
+ Return a random subword with uniform law
+
+ EXAMPLES::
+
+ sage: S1 = Subwords([1,2,3,2,1,3])
+ sage: S2 = Subwords([4,6,6,6,7,4,5,5])
+ sage: for i in xrange(100):
+ ... w = S1.random_element()
+ ... if w in S2:
+ ... assert(w == [])
+ sage: for i in xrange(100):
+ ... w = S2.random_element()
+ ... if w in S1:
+ ... assert(w == [])
+ """
+ return self._build(elt for elt in self._w if prandom.randint(0,1))
def __iter__(self):
r"""
EXAMPLES::
- sage: [sw for sw in Subwords([1,2,3])]
+ sage: Subwords([1,2,3]).list()
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
+ sage: Subwords((1,2,3)).list()
+ [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
+ sage: Subwords('123').list()
+ ['', '1', '2', '3', '12', '13', '23', '123']
"""
- #Case 1: recursively build a generator for all the subwords
- # length k and concatenate them together
- w = self.w
- return itertools.chain(*[Subwords_wk(w,i) for i in range(0,len(w)+1)])
-
+ return itertools.chain(*[Subwords_wk(self._w,i,self._build) for i in range(0,len(self._w)+1)])
-class Subwords_wk(CombinatorialClass):
- def __init__(self, w, k):
+class Subwords_wk(Subwords_w):
+ r"""
+ Subwords with fixed length of a given word
+ """
+ def __init__(self, w, k, build):
"""
TESTS::
sage: S = Subwords([1,2,3],2)
sage: S == loads(dumps(S))
True
+ sage: TestSuite(S).run()
"""
- self.w = w
- self.k = k
+ Subwords_w.__init__(self,w,build)
+ self._k = k
- def __repr__(self):
+ def __reduce__(self):
+ r"""
+ Pickle (how to construct back the object)
+
+ TESTS::
+
+ sage: S = Subwords('abc',2)
+ sage: S == loads(dumps(S))
+ True
+ sage: S = Subwords(('a',1,'45',(1,2)))
+ sage: S == loads(dumps(S))
+ True
+ """
+ return (Subwords,(self._w,self._k))
+
+ def _repr_(self):
"""
TESTS::
- sage: repr(Subwords([1,2,3],2))
+ sage: repr(Subwords([1,2,3],2)) # indirect doctest
'Subwords of [1, 2, 3] of length 2'
"""
- return "Subwords of %s of length %s"%(self.w, self.k)
+ return "%s of length %s" %(Subwords_w._repr_(self), self._k)
def __contains__(self, w):
"""
@@ -202,16 +321,12 @@ class Subwords_wk(CombinatorialClass):
True
sage: [2,3,3,4] in Subwords([1,2,3,4,3,4,4],3)
False
- sage: [5, 5, 3] in Subwords([1, 3, 3, 5, 4, 5, 3, 5],3)
+ sage: [5,5,3] in Subwords([1,3,3,5,4,5,3,5],3)
True
- sage: [5, 5, 3] in Subwords([1, 3, 3, 5, 4, 5, 3, 5],4)
+ sage: [5,5,3] in Subwords([1,3,3,5,4,5,3,5],4)
False
"""
- if len(w) != self.k:
- return False
- if smallest_positions(self.w, w) != False:
- return True
- return False
+ return len(w) == self._k and Subwords_w.__contains__(self,w)
def cardinality(self):
r"""
@@ -222,10 +337,7 @@ class Subwords_wk(CombinatorialClass):
sage: Subwords([1,2,3], 2).cardinality()
3
"""
- w = self.w
- k = self.k
- return factorial(len(w))/(factorial(k)*factorial(len(w)-k))
-
+ return arith.binomial(len(self._w),self._k)
def first(self):
r"""
@@ -235,8 +347,16 @@ class Subwords_wk(CombinatorialClass):
[1, 2]
sage: Subwords([1,2,3],0).first()
[]
+ sage: Subwords((1,2,3),2).first()
+ (1, 2)
+ sage: Subwords((1,2,3),0).first()
+ ()
+ sage: Subwords('123',2).first()
+ '12'
+ sage: Subwords('123',0).first()
+ ''
"""
- return self.w[:self.k]
+ return self._w[:self._k]
def last(self):
r"""
@@ -244,31 +364,72 @@ class Subwords_wk(CombinatorialClass):
sage: Subwords([1,2,3],2).last()
[2, 3]
+ sage: Subwords([1,2,3],0).last()
+ []
+ sage: Subwords((1,2,3),2).last()
+ (2, 3)
+ sage: Subwords((1,2,3),0).last()
+ ()
+ sage: Subwords('123',2).last()
+ '23'
+ sage: Subwords('123',0).last()
+ ''
+
+ TESTS::
+
+ sage: Subwords('123', 0).last() # trac 10534
+ ''
"""
+ if self._k:
+ return self._w[-self._k:]
+ return self.first()
- return self.w[-self.k:]
+ def random_element(self):
+ r"""
+ Return a random subword of given length with uniform law
+ EXAMPLES::
+ sage: S1 = Subwords([1,2,3,2,1],3)
+ sage: S2 = Subwords([4,4,5,5,4,5,4,4],3)
+ sage: for i in xrange(100):
+ ... w = S1.random_element()
+ ... if w in S2:
+ ... assert(w == [])
+ sage: for i in xrange(100):
+ ... w = S2.random_element()
+ ... if w in S1:
+ ... assert(w == [])
+ """
+ sample = prandom.sample(self._w, self._k)
+ if type(self._w) == list:
+ return sample
+ return self._build(sample)
def __iter__(self):
"""
EXAMPLES::
- sage: [sw for sw in Subwords([1,2,3],2)]
+ sage: Subwords([1,2,3],2).list()
[[1, 2], [1, 3], [2, 3]]
- sage: [sw for sw in Subwords([1,2,3],0)]
+ sage: Subwords([1,2,3],0).list()
[[]]
+ sage: Subwords((1,2,3),2).list()
+ [(1, 2), (1, 3), (2, 3)]
+ sage: Subwords((1,2,3),0).list()
+ [()]
+ sage: Subwords('abc',2).list()
+ ['ab', 'ac', 'bc']
+ sage: Subwords('abc',0).list()
+ ['']
"""
- w = self.w
- k = self.k
- #Case 1: k == 0
- if k == 0:
- return itertools.repeat([],1)
-
- #Case 2: build a generator for the subwords of length k
- gen = iter(combination.Combinations(range(len(w)), k))
- return itertools.imap(lambda subword: [w[x] for x in subword], gen)
-
+ if self._k > len(self._w):
+ return iter([])
+ iterator = itertools.combinations(self._w, self._k)
+ if type(self._w) == tuple:
+ return iterator
+ else:
+ return itertools.imap(self._build, iterator)
def smallest_positions(word, subword, pos = 0):
"""
@@ -315,8 +476,8 @@ def smallest_positions(word, subword, pos = 0):
"""
pos -= 1
res = [None] * len(subword)
- for i in range(len(subword)):
- for j in range(pos+1, len(word)+1):
+ for i in xrange(len(subword)):
+ for j in xrange(pos+1, len(word)+1):
if j == len(word):
return False
if word[j] == subword[i]: