# source:sage/combinat/set_partition.py@8006:90d75762f161

Revision 8006:90d75762f161, 12.2 KB checked in by Mike Hansen <mhansen@…>, 5 years ago (diff)

Restructuring symmetric functions and misc. combinatorics updates ( #1685 )

Line
1r"""
2Set Partitions
3
4A set partition  s of a set set is a partition of set, into subsets called parts and represented as a set of sets. By extension, a set partition of a nonnegative integer n is the set partition of the integers from 1 to n. The number of set partitions of n is called the n-th Bell number.
5
6There is a natural integer partition associated with a set partition, that is the non-decreasing sequence of sizes of all its parts.
7
8There is a classical lattice associated with all set partitions of n. The infimum of two set partitions is the set partition obtained by intersecting all the parts of both set partitions. The supremum is obtained by transitive closure of the relation i related to j iff they are in the same part in at least one of the set partitions.
9
10EXAMPLES:
11  There are 5 set partitions of the set {1,2,3}.
12
13    sage: SetPartitions(3).count()
14    5
15
16  Here is the list of them:
17
18    sage: SetPartitions(3).list() #random due to the sets
19    [{{1, 2, 3}}, {{2, 3}, {1}}, {{1, 3}, {2}}, {{1, 2}, {3}}, {{2}, {3}, {1}}]
20
21  There are 6 set partitions of {1,2,3,4} whose underlying partition
22  is [2, 1, 1]:
23
24    sage: SetPartitions(4, [2,1,1]).list() #random due to the sets
25    [{{3, 4}, {2}, {1}},
26     {{2, 4}, {3}, {1}},
27     {{4}, {2, 3}, {1}},
28     {{1, 4}, {2}, {3}},
29     {{1, 3}, {4}, {2}},
30     {{1, 2}, {4}, {3}}]
31
32AUTHORS:
33    --Mike Hansen
34    --MuPAD-Combinat developers (for algorithms and design inspiration).
35
36"""
37#*****************************************************************************
38#       Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
39#
40#  Distributed under the terms of the GNU General Public License (GPL)
41#
42#    This code is distributed in the hope that it will be useful,
43#    but WITHOUT ANY WARRANTY; without even the implied warranty of
44#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
45#    General Public License for more details.
46#
47#  The full text of the GPL is available at:
48#
49#                  http://www.gnu.org/licenses/
50#*****************************************************************************
51
52from sage.sets.set import Set, EnumeratedSet, is_Set
53import sage.combinat.partition as partition
54import sage.rings.integer
55import __builtin__
56import itertools
57from cartesian_product import CartesianProduct
58import sage.combinat.subset as subset
59import sage.combinat.set_partition_ordered as set_partition_ordered
60import copy
61from combinat import CombinatorialClass, CombinatorialObject, bell_number, stirling_number2
62from subword import Subwords
63
64
65def SetPartitions(s, part=None):
66    """
67    An {\it unordered partition} of a set $S$ is a set of pairwise disjoint
68    nonempty subsets with union $S$ and is represented by a sorted
69    list of such subsets.
70
71    partitions_set returns the set of all unordered partitions of the
72    list $S$ of increasing positive integers into k pairwise disjoint
73    nonempty sets. If k is omitted then all partitions are returned.
74
75    The Bell number $B_n$, named in honor of Eric Temple Bell, is
76    the number of different partitions of a set with n elements.
77
78    EXAMPLES:
79        sage: S = [1,2,3,4]
80        sage: SetPartitions(S,2)
81        Set partitions of [1, 2, 3, 4] with 2 parts
82
83
84    REFERENCES:
85       http://en.wikipedia.org/wiki/Partition_of_a_set
86
87    """
88    if isinstance(s, (int, sage.rings.integer.Integer)):
89        set = range(1, s+1)
90    elif isinstance(s, str):
91        set = [x for x in s]
92    else:
93        set = s
94
95    if part is not None:
96        if isinstance(part, (int, sage.rings.integer.Integer)):
97            if len(set) < part:
98                raise ValueError, "part must be <= len(set)"
99            else:
100                return SetPartitions_setn(set,part)
101        else:
102            if part not in partition.Partitions(len(set)):
103                raise ValueError, "part must be a partition of %s"%len(set)
104            else:
105                return SetPartitions_setparts(set, [partition.Partition(part)])
106    else:
107        return SetPartitions_set(set)
108
109
110
111class SetPartitions_setparts(CombinatorialClass):
112    def __init__(self, set, parts):
113        """
114        TESTS:
115            sage: S = SetPartitions(4, [2,2])
116            sage: S == loads(dumps(S))
117            True
118        """
119        self.set = set
120        self.parts = parts
121
122    def __repr__(self):
123        """
124        TESTS:
125            sage: repr(SetPartitions(4, [2,2]))
126            'Set partitions of [1, 2, 3, 4] with sizes in [[2, 2]]'
127        """
128        return "Set partitions of %s with sizes in %s"%(self.set, self.parts)
129
130    def __contains__(self, x):
131        """
132        TESTS:
133            sage: S = SetPartitions(4, [2,2])
134            sage: all([sp in S for sp in S])
135            True
136        """
137        #x must be a set
138        if not is_Set(x):
139            return False
140
141        #Make sure that the number of elements match up
142        if sum(map(len, x)) != len(self.set):
143            return False
144
145        #Check to make sure each element of x
146        #is a set
147        u = Set([])
148        for s in x:
149            if not is_Set(s):
150                return False
151            u = u.union(s)
152
153        #Make sure that the union of all the
154        #sets is the original set
155        if u != Set(self.set):
156            return False
157
158        return True
159
160    def count(self):
161        """
162        Returns the number of set partitions of set.  This
163        number is given by the n-th Bell number where n is
164        the number of elements in the set.
165
166        If a partition or partition length is specified, then
167        count will generate all of the set partitions.
168
169        EXAMPLES:
170            sage: SetPartitions([1,2,3,4]).count()
171            15
172            sage: SetPartitions(3).count()
173            5
174            sage: SetPartitions(3,2).count()
175            3
176            sage: SetPartitions([]).count()
177            1
178        """
179        return len(self.list())
180
181
182    def __iterator_part(self, part):
183        set = self.set
184
185        nonzero = []
186        p = partition.Partition(part)
187        expo = p.to_exp()
188
189        for i in range(len(expo)):
190            if expo[i] != 0:
191                nonzero.append([i, expo[i]])
192
193        taillesblocs = map(lambda x: (x[0])*(x[1]), nonzero)
194
195        blocs = set_partition_ordered.OrderedSetPartitions(copy.copy(set), taillesblocs).list()
196
197        for b in blocs:
198            lb = [ _listbloc(nonzero[i][0], nonzero[i][1], b[i]) for i in range(len(nonzero)) ]
199            for x in itertools.imap(lambda x: _union(x), CartesianProduct( *lb )):
200                yield x
201
202
203
204    def iterator(self):
205        """
206        An iterator for all the set partitions of the set.
207
208        EXAMPLES:
209            sage: SetPartitions(3).list()
210            [{{1, 2, 3}}, {{2, 3}, {1}}, {{1, 3}, {2}}, {{1, 2}, {3}}, {{2}, {3}, {1}}]
211        """
212        for p in self.parts:
213            for sp in self.__iterator_part(p):
214                yield sp
215
216
217class SetPartitions_setn(SetPartitions_setparts):
218    def __init__(self, set, n):
219        """
220        TESTS:
221            sage: S = SetPartitions(5, 3)
222            sage: S == loads(dumps(S))
223            True
224        """
225        self.n = n
226        SetPartitions_setparts.__init__(self, set, partition.Partitions(len(set), length=n).list())
227
228    def __repr__(self):
229        """
230        TESTS:
231            sage: repr(SetPartitions(5, 3))
232            'Set partitions of [1, 2, 3, 4, 5] with 3 parts'
233        """
234        return "Set partitions of %s with %s parts"%(self.set,self.n)
235
236    def count(self):
237        """
238        The Stirling number of the second kind is the number
239        of partitions of a set of size n into k blocks.
240
241        EXAMPLES:
242            sage: SetPartitions(5, 3).count()
243            25
244            sage: stirling_number2(5,3)
245            25
246        """
247        return stirling_number2(len(self.set), self.n)
248
249class SetPartitions_set(SetPartitions_setparts):
250    def __init__(self, set):
251        """
252        TESTS:
253            sage: S = SetPartitions([1,2,3])
254            sage: S == loads(dumps(S))
255            True
256        """
257        SetPartitions_setparts.__init__(self, set, partition.Partitions(len(set)))
258
259    def __repr__(self):
260        """
261        TESTS:
262            sage: repr( SetPartitions([1,2,3]) )
263            'Set partitions of [1, 2, 3]'
264        """
265        return "Set partitions of %s"%(self.set)
266
267    def count(self):
268        """
269        EXAMPLES:
270            sage: SetPartitions(4).count()
271            15
272            sage: bell_number(4)
273            15
274        """
275        return bell_number(len(self.set))
276
277
278
279def _listbloc(n, nbrepets, listint=None):
280    """
281    listbloc decomposes a set of n*nbrepets integers (the list listint)
282    in nbrepets parts.
283
284    It is used in the algorithm to generate all set partitions.
285
286    Not to be called by the user.
287
288    EXAMPLES:
289        sage: sage.combinat.set_partition._listbloc(2,1)
290        [{{1, 2}}]
291        sage: l = [Set([Set([3, 4]), Set([1, 2])]), Set([Set([2, 4]), Set([1, 3])]), Set([Set([2, 3]), Set([1, 4])])]
292        sage: sage.combinat.set_partition._listbloc(2,2,[1,2,3,4]) == l
293        True
294
295
296    """
297    if isinstance(listint, (int, sage.rings.integer.Integer)) or listint is None:
298        listint = Set(range(1,n+1))
299
300
301    if nbrepets == 1:
302        return [Set([listint])]
303
304    l = __builtin__.list(listint)
305    l.sort()
306    smallest = Set(l[:1])
307    new_listint = Set(l[1:])
308
309    f = lambda u, v: u.union(_set_union([smallest,v]))
310    res = []
311
312    for ssens in subset.Subsets(new_listint, n-1):
313        for z in _listbloc(n, nbrepets-1, new_listint-ssens):
314            res.append(f(z,ssens))
315
316    return res
317
318def _union(s):
319    """
320    TESTS:
321        sage: s = Set([ Set([1,2]), Set([3,4]) ])
322        sage: sage.combinat.set_partition._union(s)
323        {1, 2, 3, 4}
324    """
325    result = Set([])
326    for ss in s:
327        result = result.union(ss)
328    return result
329
330def _set_union(s):
331    """
332    TESTS:
333        sage: s = Set([ Set([1,2]), Set([3,4]) ])
334        sage: sage.combinat.set_partition._set_union(s)
335        {{1, 2, 3, 4}}
336    """
337    result = Set([])
338    for ss in s:
339        result = result.union(ss)
340    return EnumeratedSet([result])
341
342def inf(s,t):
343    """
344    Returns the infimum of the two set partitions s and t.
345
346    EXAMPLES:
347        sage: sp1 = Set([Set([2,3,4]),Set([1])])
348        sage: sp2 = Set([Set([1,3]), Set([2,4])])
349        sage: s = Set([ Set([2,4]), Set([3]), Set([1])]) #{{2, 4}, {3}, {1}}
350        sage: sage.combinat.set_partition.inf(sp1, sp2) == s
351        True
352
353    """
354    temp = [ss.intersection(ts) for ss in s for ts in t]
355    temp = filter(lambda x: x != Set([]), temp)
356    return EnumeratedSet(temp)
357
358def sup(s,t):
359    """
360    Returns the supremum of the two set partitions s and t.
361
362    EXAMPLES:
363        sage: sp1 = Set([Set([2,3,4]),Set([1])])
364        sage: sp2 = Set([Set([1,3]), Set([2,4])])
365        sage: s = Set([ Set([1,2,3,4]) ])
366        sage: sage.combinat.set_partition.sup(sp1, sp2) == s
367        True
368
369    """
370    res = s
371    for p in t:
372        inters = Set(filter(lambda x: x.intersection(p) != Set([]), __builtin__.list(res)))
373        res = res.difference(inters).union(_set_union(inters))
374
375    return res
376
377
378def standard_form(sp):
379    """
380    Returns the set partition as a list of lists.
381
382    EXAMPLES:
383        sage: map(sage.combinat.set_partition.standard_form, SetPartitions(4, [2,2]))
384        [[[3, 4], [1, 2]], [[2, 4], [1, 3]], [[2, 3], [1, 4]]]
385    """
386
387    return [__builtin__.list(x) for x in sp]
388
389
390def less(s, t):
391    """
392    Returns True if s < t otherwise it returns False.
393
394    EXAMPLES:
395        sage: z = SetPartitions(3).list()
396        sage: sage.combinat.set_partition.less(z[0], z[1])
397        False
398        sage: sage.combinat.set_partition.less(z[4], z[1])
399        True
400        sage: sage.combinat.set_partition.less(z[4], z[0])
401        True
402        sage: sage.combinat.set_partition.less(z[3], z[0])
403        True
404        sage: sage.combinat.set_partition.less(z[2], z[0])
405        True
406        sage: sage.combinat.set_partition.less(z[1], z[0])
407        True
408        sage: sage.combinat.set_partition.less(z[0], z[0])
409        False
410    """
411
412    if _union(s) != _union(t):
413        raise ValueError, "cannont compare partitions of different sets"
414
415    if s == t:
416        return False
417
418    for p in s:
419        f = lambda z: z.intersection(p) != Set([])
420        if len(filter(f, __builtin__.list(t)) ) != 1:
421            return False
422
423    return True
424
Note: See TracBrowser for help on using the repository browser.