AUTHORS:
Bases: sage.structure.list_clone.ClonableArray
A partition of a set.
A set partition of a set
is a partition of
into subsets
called parts and represented as a set of sets. By extension, a set
partition of a nonnegative integer
is the set partition of the
integers from 1 to
. The number of set partitions of
is called
the
-th Bell number.
There is a natural integer partition associated with a set partition, namely the nonincreasing sequence of sizes of all its parts.
There is a classical lattice associated with all set partitions of
. 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
related to
if and only if they are in the same part in at least one of the set
partitions.
We will use terminology from partitions, in particular the length of
a set partition is the number of parts of
and is denoted by
. The size of
is the cardinality of
.
We will also sometimes use the notation
.
EXAMPLES:
There are 5 set partitions of the set :
sage: SetPartitions(3).cardinality()
5
Here is the list of them:
sage: SetPartitions(3).list()
[{{1, 2, 3}},
{{1}, {2, 3}},
{{1, 3}, {2}},
{{1, 2}, {3}},
{{1}, {2}, {3}}]
There are 6 set partitions of whose underlying partition is
:
sage: SetPartitions(4, [2,1,1]).list()
[{{1}, {2}, {3, 4}},
{{1}, {2, 4}, {3}},
{{1}, {2, 3}, {4}},
{{1, 4}, {2}, {3}},
{{1, 3}, {2}, {4}},
{{1, 2}, {3}, {4}}]
Since trac ticket #14140, we can create a set partition directly by SetPartition, which creates the base set by taking the union of the parts passed in:
sage: s = SetPartition([[1,3],[2,4]]); s
{{1, 3}, {2, 4}}
sage: s.parent()
Set partitions
Apply p to the underlying set of self.
INPUT:
EXAMPLES:
sage: x = SetPartition([[1,2], [3,5,4]])
sage: p = Permutation([2,1,4,5,3])
sage: x.apply_permutation(p)
{{1, 2}, {3, 4, 5}}
sage: q = Permutation([3,2,1,5,4])
sage: x.apply_permutation(q)
{{1, 4, 5}, {2, 3}}
Return the base set of self, which is the union of all parts of self.
EXAMPLES:
sage: SetPartition([[1], [2,3], [4]]).base_set()
{1, 2, 3, 4}
sage: SetPartition([[1,2,3,4]]).base_set()
{1, 2, 3, 4}
sage: SetPartition([]).base_set()
{}
Return the cardinality of the base set of self, which is the sum of the sizes of the parts of self.
This is also known as the size (sometimes the weight) of a set partition.
EXAMPLES:
sage: SetPartition([[1], [2,3], [4]]).base_set_cardinality()
4
sage: SetPartition([[1,2,3,4]]).base_set_cardinality()
4
Returns the len of self
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: len(IncreasingArrays()([1,2,3]))
3
Check that we are a valid ordered set partition.
EXAMPLES:
sage: OS = OrderedSetPartitions(4)
sage: s = OS([[1, 3], [2, 4]])
sage: s.check()
Return a list of coarsenings of self.
EXAMPLES:
sage: SetPartition([[1,3],[2,4]]).coarsenings()
[{{1, 2, 3, 4}}, {{1, 3}, {2, 4}}]
sage: SetPartition([[1],[2,4],[3]]).coarsenings()
[{{1, 2, 3, 4}},
{{1}, {2, 3, 4}},
{{1, 3}, {2, 4}},
{{1, 2, 4}, {3}},
{{1}, {2, 4}, {3}}]
sage: SetPartition([]).coarsenings()
[{}]
The product of the set partitions self and other.
The product of two set partitions and
is defined as the
set partition whose parts are the nonempty intersections between
each part of
and each part of
. This product is also
the infimum of
and
in the classical set partition
lattice (that is, the coarsest set partition which is finer than
each of
and
). Consequently, inf acts as an alias for
this method.
See also
EXAMPLES:
sage: x = SetPartition([ [1,2], [3,5,4] ])
sage: y = SetPartition(( (3,1,2), (5,4) ))
sage: x * y
{{1, 2}, {3}, {4, 5}}
sage: S = SetPartitions(4)
sage: sp1 = S([[2,3,4], [1]])
sage: sp2 = S([[1,3], [2,4]])
sage: s = S([[2,4], [3], [1]])
sage: sp1.inf(sp2) == s
True
TESTS:
Here is a different implementation of the __mul__ method (one that was formerly used for the inf method, before it was realized that the methods do the same thing):
sage: def mul2(s, t):
....: temp = [ss.intersection(ts) for ss in s for ts in t]
....: temp = filter(lambda x: x != Set([]), temp)
....: return s.__class__(s.parent(), temp)
Let us check that this gives the same as __mul__ on set
partitions of :
sage: all( all( mul2(s, t) == s * t for s in SetPartitions(4) )
....: for t in SetPartitions(4) )
True
Return if self is an atomic set partition.
A (standard) set partition can be split if there exist
such that
where
is ordered by minimal
elements. This means we can write
for some nonempty set
partitions
and
. We call a set partition atomic if it
cannot be split and is nonempty. Here, the pipe symbol
is as defined in method pipe().
EXAMPLES:
sage: SetPartition([[1,3], [2]]).is_atomic()
True
sage: SetPartition([[1,3], [2], [4]]).is_atomic()
False
sage: SetPartition([[1], [2,4], [3]]).is_atomic()
False
sage: SetPartition([[1,2,3,4]]).is_atomic()
True
sage: SetPartition([[1, 4], [2], [3]]).is_atomic()
True
sage: SetPartition([]).is_atomic()
False
Check if self is noncrossing.
EXAMPLES:
sage: x = SetPartition([[1,2],[3,4]])
sage: x.is_noncrossing()
True
sage: x = SetPartition([[1,3],[2,4]])
sage: x.is_noncrossing()
False
AUTHOR: Florent Hivert
Return the action of an ordered set partition s on self.
Let be a set partition of some
set
and
be an ordered set partition (i.e., set composition)
of a subset of
. Let
denote the standardization
of
, and
denote the sub-partition
for any subset
of
. We define the set
partition
by
where . Here, the pipe symbol
is as defined in method pipe().
This is in section 2.3 in [LM2011].
INPUT:
EXAMPLES:
sage: A = SetPartition([[1], [2,4], [3]])
sage: s = OrderedSetPartition([[1,3], [2]])
sage: A.ordered_set_partition_action(s)
{{1}, {2}, {3, 4}}
sage: s = OrderedSetPartition([[2,3], [1]])
sage: A.ordered_set_partition_action(s)
{{1, 3}, {2}, {4}}
We create Figure 1 in [LM2011] (we note that there is a typo in the lower-left corner of the table in the published version of the paper, whereas the arXiv version gives the correct partition):
sage: A = SetPartition([[1,3], [2,9], [4,5,8], [7]])
sage: B = SetPartition([[1,3], [2,8], [4,5,6], [7]])
sage: C = SetPartition([[1,5], [2,8], [3,4,6], [7]])
sage: s = OrderedSetPartition([[1,3], [2]])
sage: t = OrderedSetPartition([[2], [3,4]])
sage: u = OrderedSetPartition([[1], [2,3,4]])
sage: A.ordered_set_partition_action(s)
{{1, 2}, {3, 4, 5}, {6, 7}}
sage: A.ordered_set_partition_action(t)
{{1, 2}, {3, 4, 6}, {5}}
sage: A.ordered_set_partition_action(u)
{{1, 2}, {3, 8}, {4, 5, 7}, {6}}
sage: B.ordered_set_partition_action(s)
{{1, 2}, {3, 4, 5}, {6, 7}}
sage: B.ordered_set_partition_action(t)
{{1, 2}, {3, 4, 5}, {6}}
sage: B.ordered_set_partition_action(u)
{{1, 2}, {3, 8}, {4, 5, 6}, {7}}
sage: C.ordered_set_partition_action(s)
{{1, 4}, {2, 3, 5}, {6, 7}}
sage: C.ordered_set_partition_action(t)
{{1, 2}, {3, 4, 5}, {6}}
sage: C.ordered_set_partition_action(u)
{{1, 2}, {3, 8}, {4, 5, 6}, {7}}
REFERENCES:
[LM2011] | (1, 2) A. Lauve, M. Mastnak. The primitives and antipode in the Hopf algebra of symmetric functions in noncommuting variables. Advances in Applied Mathematics. 47 (2011). 536-544. Arxiv 1006.0367v3 doi:10.1016/j.aam.2011.01.002. |
Return the pipe of the set partitions self and other.
The pipe of two set partitions is defined as follows:
For any integer and any subset
of
, let
denote the subset of
obtained by adding
to every
element of
.
If and
are set partitions of
and
,
respectively, then the pipe of
and
is defined as the
set partition
of , where
and
. This pipe is denoted by
.
EXAMPLES:
sage: SetPartition([[1,3],[2,4]]).pipe(SetPartition([[1,3],[2]]))
{{1, 3}, {2, 4}, {5, 7}, {6}}
sage: SetPartition([]).pipe(SetPartition([[1,2],[3,5],[4]]))
{{1, 2}, {3, 5}, {4}}
sage: SetPartition([[1,2],[3,5],[4]]).pipe(SetPartition([]))
{{1, 2}, {3, 5}, {4}}
sage: SetPartition([[1,2],[3]]).pipe(SetPartition([[1]]))
{{1, 2}, {3}, {4}}
Return a list of refinements of self.
EXAMPLES:
sage: SetPartition([[1,3],[2,4]]).refinements()
[{{1, 3}, {2, 4}},
{{1, 3}, {2}, {4}},
{{1}, {2, 4}, {3}},
{{1}, {2}, {3}, {4}}]
sage: SetPartition([[1],[2,4],[3]]).refinements()
[{{1}, {2, 4}, {3}}, {{1}, {2}, {3}, {4}}]
sage: SetPartition([]).refinements()
[{}]
Return the restriction of self to a subset I (which is given as a set or list or any other iterable).
EXAMPLES:
sage: A = SetPartition([[1], [2,3]])
sage: A.restriction([1,2])
{{1}, {2}}
sage: A.restriction([2,3])
{{2, 3}}
sage: A.restriction([])
{}
sage: A.restriction([4])
{}
Return the integer partition whose parts are the sizes of the sets in self.
EXAMPLES:
sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
Return the integer partition whose parts are the sizes of the sets in self.
EXAMPLES:
sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
Return the cardinality of the base set of self, which is the sum of the sizes of the parts of self.
This is also known as the size (sometimes the weight) of a set partition.
EXAMPLES:
sage: SetPartition([[1], [2,3], [4]]).base_set_cardinality()
4
sage: SetPartition([[1,2,3,4]]).base_set_cardinality()
4
Return self as a list of lists.
This is not related to standard set partitions (which simply
means set partitions of for some
integer
) or standardization (standardization()).
EXAMPLES:
sage: [x.standard_form() for x in SetPartitions(4, [2,2])]
[[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[1, 4], [2, 3]]]
Return the standardization of self.
Given a set partition of an ordered
set
, the standardization of
is the set partition of
obtained by replacing the elements of
the parts of
by the integers
in such
a way that their relative order is preserved (i. e., the
smallest element in the whole set partition is replaced by
, the next-smallest by
, and so on).
EXAMPLES:
sage: SetPartition([[4], [1, 3]]).standardization()
{{1, 2}, {3}}
sage: SetPartition([[4], [6, 3]]).standardization()
{{1, 3}, {2}}
sage: SetPartition([]).standardization()
{}
Return all strict coarsenings of self.
Strict coarsening is the binary relation on set partitions
defined as the transitive-and-reflexive closure of the
relation defined as follows: For two set partitions
and
, we have
if there exist parts
of
such that
and
.
EXAMPLES:
sage: A = SetPartition([[1],[2,3],[4]])
sage: A.strict_coarsenings()
[{{1}, {2, 3}, {4}}, {{1, 2, 3}, {4}}, {{1, 4}, {2, 3}},
{{1}, {2, 3, 4}}, {{1, 2, 3, 4}}]
sage: SetPartition([[1],[2,4],[3]]).strict_coarsenings()
[{{1}, {2, 4}, {3}}, {{1, 2, 4}, {3}}, {{1, 3}, {2, 4}}]
sage: SetPartition([]).strict_coarsenings()
[{}]
Return the supremum of self and t in the classical set partition lattice.
The supremum of two set partitions and
is obtained as the
transitive closure of the relation which relates
to
if
and only if
and
are in the same part in at least
one of the set partitions
and
.
See also
__mul__()
EXAMPLES:
sage: S = SetPartitions(4)
sage: sp1 = S([[2,3,4], [1]])
sage: sp2 = S([[1,3], [2,4]])
sage: s = S([[1,2,3,4]])
sage: sp1.sup(sp2) == s
True
Return the integer partition whose parts are the sizes of the sets in self.
EXAMPLES:
sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
Convert self to a permutation by considering the partitions as cycles.
EXAMPLES:
sage: s = SetPartition([[1,3],[2,4]])
sage: s.to_permutation()
[3, 4, 1, 2]
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
An (unordered) partition of a set is a set of pairwise
disjoint nonempty subsets with union
, and is represented
by a sorted list of such subsets.
SetPartitions(s) returns the class of all set partitions of the set s, which can be given as a set or a string; if a string, each character is considered an element.
SetPartitions(n), where n is an integer, returns the class of
all set partitions of the set .
You may specify a second argument . If
is an integer,
SetPartitions returns the class of set partitions into
parts;
if it is an integer partition, SetPartitions returns the class of
set partitions whose block sizes correspond to that integer partition.
The Bell number , named in honor of Eric Temple Bell,
is the number of different partitions of a set with
elements.
EXAMPLES:
sage: S = [1,2,3,4]
sage: SetPartitions(S,2)
Set partitions of {1, 2, 3, 4} with 2 parts
sage: SetPartitions([1,2,3,4], [3,1]).list()
[{{1}, {2, 3, 4}}, {{1, 3, 4}, {2}}, {{1, 2, 4}, {3}}, {{1, 2, 3}, {4}}]
sage: SetPartitions(7, [3,3,1]).cardinality()
70
In strings, repeated letters are not considered distinct as of trac ticket #14140:
sage: SetPartitions('abcde').cardinality()
52
sage: SetPartitions('aabcd').cardinality()
15
REFERENCES:
alias of SetPartition
Check if in the refinement ordering on set partitions.
This means that is a refinement of
and satisfies
.
A set partition is said to be a refinement of a set
partition
of the same set if and only if each part of
is a subset of a part of
.
EXAMPLES:
sage: S = SetPartitions(4)
sage: s = S([[1,3],[2,4]])
sage: t = S([[1],[2],[3],[4]])
sage: S.is_less_than(t, s)
True
sage: S.is_less_than(s, t)
False
sage: S.is_less_than(s, s)
False
Return True if s is a strict refinement of t and
satisfies .
A set partition is said to be a strict refinement of a set
partition
of the same set if and only if one can obtain
from
by repeatedly combining pairs of parts whose
convex hulls don’t intersect (i. e., whenever we are combining
two parts, the maximum of each of them should be smaller than
the minimum of the other).
EXAMPLES:
sage: S = SetPartitions(4)
sage: s = S([[1],[2],[3],[4]])
sage: t = S([[1,3],[2,4]])
sage: u = S([[1,2,3,4]])
sage: S.is_strict_refinement(s, t)
True
sage: S.is_strict_refinement(t, u)
False
sage: A = SetPartition([[1,3],[2,4]])
sage: B = SetPartition([[1,2,3,4]])
sage: S.is_strict_refinement(s, A)
True
sage: S.is_strict_refinement(t, B)
False
Check if in the refinement ordering on set partitions.
This means that is a refinement of
and satisfies
.
A set partition is said to be a refinement of a set
partition
of the same set if and only if each part of
is a subset of a part of
.
EXAMPLES:
sage: S = SetPartitions(4)
sage: s = S([[1,3],[2,4]])
sage: t = S([[1],[2],[3],[4]])
sage: S.is_less_than(t, s)
True
sage: S.is_less_than(s, t)
False
sage: S.is_less_than(s, s)
False
Bases: sage.combinat.set_partition.SetPartitions
All set partitions.
Bases: sage.combinat.set_partition.SetPartitions
Set partitions of a fixed set .
Return the base set of self.
EXAMPLES:
sage: SetPartitions(3).base_set()
{1, 2, 3}
Return the cardinality of the base set of self.
EXAMPLES:
sage: SetPartitions(3).base_set_cardinality()
3
Return the number of set partitions of the set .
The cardinality is given by the -th Bell number where
is the
number of elements in the set
.
EXAMPLES:
sage: SetPartitions([1,2,3,4]).cardinality()
15
sage: SetPartitions(3).cardinality()
5
sage: SetPartitions(3,2).cardinality()
3
sage: SetPartitions([]).cardinality()
1
Bases: sage.combinat.set_partition.SetPartitions_set
TESTS:
sage: S = SetPartitions(5, 3)
sage: TestSuite(S).run()
The Stirling number of the second kind is the number of partitions
of a set of size into
blocks.
EXAMPLES:
sage: SetPartitions(5, 3).cardinality()
25
sage: stirling_number2(5,3)
25
Bases: sage.combinat.set_partition.SetPartitions_set
Class of all set partitions with fixed partition sizes corresponding to
an integer partition .
Return the cardinality of self.
This algorithm counts for each block of the partition the
number of ways to fill it using values from the set. Then,
for each distinct value of block size, we divide the result by
the number of ways to arrange the blocks of size
in the
set partition.
For example, if we want to count the number of set partitions
of size 13 having [3,3,3,2,2] as underlying partition we
compute the number of ways to fill each block of the
partition, which is and as we have three blocks of size
and two blocks of size
, we divide the result by
which gives us
.
EXAMPLES:
sage: SetPartitions(3, [2,1]).cardinality()
3
sage: SetPartitions(13, Partition([3,3,3,2,2])).cardinality()
600600
TESTS:
sage: all((len(SetPartitions(size, part)) == SetPartitions(size, part).cardinality() for size in range(8) for part in Partitions(size)))
True
sage: sum((SetPartitions(13, p).cardinality() for p in Partitions(13))) == SetPartitions(13).cardinality()
True
Returns all combinations of cyclic permutations of each cell of the set partition.
AUTHORS:
EXAMPLES:
sage: from sage.combinat.set_partition import cyclic_permutations_of_set_partition
sage: cyclic_permutations_of_set_partition([[1,2,3,4],[5,6,7]])
[[[1, 2, 3, 4], [5, 6, 7]],
[[1, 2, 4, 3], [5, 6, 7]],
[[1, 3, 2, 4], [5, 6, 7]],
[[1, 3, 4, 2], [5, 6, 7]],
[[1, 4, 2, 3], [5, 6, 7]],
[[1, 4, 3, 2], [5, 6, 7]],
[[1, 2, 3, 4], [5, 7, 6]],
[[1, 2, 4, 3], [5, 7, 6]],
[[1, 3, 2, 4], [5, 7, 6]],
[[1, 3, 4, 2], [5, 7, 6]],
[[1, 4, 2, 3], [5, 7, 6]],
[[1, 4, 3, 2], [5, 7, 6]]]
Iterates over all combinations of cyclic permutations of each cell of the set partition.
AUTHORS:
EXAMPLES:
sage: from sage.combinat.set_partition import cyclic_permutations_of_set_partition_iterator
sage: list(cyclic_permutations_of_set_partition_iterator([[1,2,3,4],[5,6,7]]))
[[[1, 2, 3, 4], [5, 6, 7]],
[[1, 2, 4, 3], [5, 6, 7]],
[[1, 3, 2, 4], [5, 6, 7]],
[[1, 3, 4, 2], [5, 6, 7]],
[[1, 4, 2, 3], [5, 6, 7]],
[[1, 4, 3, 2], [5, 6, 7]],
[[1, 2, 3, 4], [5, 7, 6]],
[[1, 2, 4, 3], [5, 7, 6]],
[[1, 3, 2, 4], [5, 7, 6]],
[[1, 3, 4, 2], [5, 7, 6]],
[[1, 4, 2, 3], [5, 7, 6]],
[[1, 4, 3, 2], [5, 7, 6]]]
Deprecated in trac ticket #14140. Use SetPartition.inf() instead.
EXAMPLES:
sage: sp1 = Set([Set([2,3,4]),Set([1])])
sage: sp2 = Set([Set([1,3]), Set([2,4])])
sage: s = Set([ Set([2,4]), Set([3]), Set([1])]) #{{2, 4}, {3}, {1}}
sage: sage.combinat.set_partition.inf(sp1, sp2) == s
doctest:...: DeprecationWarning: inf(s, t) is deprecated. Use s.inf(t) instead.
See http://trac.sagemath.org/14140 for details.
True
Deprecated in trac ticket #14140. Use SetPartitions.is_less_than() instead.
EXAMPLES:
sage: z = SetPartitions(3).list()
sage: sage.combinat.set_partition.less(z[0], z[1])
doctest:...: DeprecationWarning: less(s, t) is deprecated. Use SetPartitions.is_less_tan(s, t) instead.
See http://trac.sagemath.org/14140 for details.
False
Deprecated in trac ticket #14140. Use SetPartition.standard_form() instead.
EXAMPLES:
sage: map(sage.combinat.set_partition.standard_form, SetPartitions(4, [2,2]))
doctest:...: DeprecationWarning: standard_form(sp) is deprecated. Use sp.standard_form() instead.
See http://trac.sagemath.org/14140 for details.
[[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[1, 4], [2, 3]]]
Deprecated in trac ticket #14140. Use SetPartition.sup() instead.
EXAMPLES:
sage: sp1 = Set([Set([2,3,4]),Set([1])])
sage: sp2 = Set([Set([1,3]), Set([2,4])])
sage: s = Set([ Set([1,2,3,4]) ])
sage: sage.combinat.set_partition.sup(sp1, sp2) == s
doctest:...: DeprecationWarning: sup(s, t) is deprecated. Use s.sup(t) instead.
See http://trac.sagemath.org/14140 for details.
True