Module: sage.combinat.set_partition_ordered
Ordered Set Partitions
An ordered set partition p of a set s is a partition of s, into subsets called parts and represented as a list of sets. By extension, an ordered set partition of a nonnegative integer n is the set partition of the integers from 1 to n. The number of ordered set partitions of n is called the n-th ordered Bell number.
There is a natural integer composition associated with an ordered set partition, that is the sequence of sizes of all its parts in order.
There are 13 ordered set partitions of 1,2,3.
sage: OrderedSetPartitions(3).count() 13
Here is the list of them:
sage: OrderedSetPartitions(3).list() #random due to the sets [[{1}, {2}, {3}], [{1}, {3}, {2}], [{2}, {1}, {3}], [{3}, {1}, {2}], [{2}, {3}, {1}], [{3}, {2}, {1}], [{1}, {2, 3}], [{2}, {1, 3}], [{3}, {1, 2}], [{1, 2}, {3}], [{1, 3}, {2}], [{2, 3}, {1}], [{1, 2, 3}]]
There are 12 ordered set partitions of 1,2,3,4 whose underlying composition is [1,2,1].
sage: OrderedSetPartitions(4,[1,2,1]).list() #random due to the sets [[{1}, {2, 3}, {4}], [{1}, {2, 4}, {3}], [{1}, {3, 4}, {2}], [{2}, {1, 3}, {4}], [{2}, {1, 4}, {3}], [{3}, {1, 2}, {4}], [{4}, {1, 2}, {3}], [{3}, {1, 4}, {2}], [{4}, {1, 3}, {2}], [{2}, {3, 4}, {1}], [{3}, {2, 4}, {1}], [{4}, {2, 3}, {1}]]
Author: -Mike Hansen -MuPAD-Combinat developers (for algorithms and design inspiration)
Module-level Functions
s, [c=None]) |
Returns the combinatorial class of ordered set partitions of s.
sage: OS = OrderedSetPartitions([1,2,3,4]); OS Ordered set partitions of {1, 2, 3, 4} sage: OS.count() 75 sage: OS.first() [{1}, {2}, {3}, {4}] sage: OS.last() [{1, 2, 3, 4}] sage: OS.random_element() [{3}, {1}, {2}, {4}]
sage: OS = OrderedSetPartitions([1,2,3,4], [2,2]); OS Ordered set partitions of {1, 2, 3, 4} into parts of size [2, 2] sage: OS.count() 6 sage: OS.first() [{1, 2}, {3, 4}] sage: OS.last() [{3, 4}, {1, 2}] sage: OS.list() [[{1, 2}, {3, 4}], [{1, 3}, {2, 4}], [{1, 4}, {2, 3}], [{2, 3}, {1, 4}], [{2, 4}, {1, 3}], [{3, 4}, {1, 2}]]
sage: OS = OrderedSetPartitions("cat"); OS Ordered set partitions of ['c', 'a', 't'] sage: OS.list() [[{'a'}, {'c'}, {'t'}], [{'a'}, {'t'}, {'c'}], [{'c'}, {'a'}, {'t'}], [{'t'}, {'a'}, {'c'}], [{'c'}, {'t'}, {'a'}], [{'t'}, {'c'}, {'a'}], [{'a'}, {'c', 't'}], [{'c'}, {'a', 't'}], [{'t'}, {'a', 'c'}], [{'a', 'c'}, {'t'}], [{'a', 't'}, {'c'}], [{'c', 't'}, {'a'}], [{'a', 'c', 't'}]]
Class: OrderedSetPartitions_s
self, s) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4]) sage: OS == loads(dumps(OS)) True
Functions: count,
iterator
self) |
sage: OrderedSetPartitions(0).count() 1 sage: OrderedSetPartitions(1).count() 1 sage: OrderedSetPartitions(2).count() 3 sage: OrderedSetPartitions(3).count() 13 sage: OrderedSetPartitions([1,2,3]).count() 13 sage: OrderedSetPartitions(4).count() 75 sage: OrderedSetPartitions(5).count() 541
self) |
sage: OrderedSetPartitions([1,2,3]).list() # indirect doctest [[{1}, {2}, {3}], [{1}, {3}, {2}], [{2}, {1}, {3}], [{3}, {1}, {2}], [{2}, {3}, {1}], [{3}, {2}, {1}], [{1}, {2, 3}], [{2}, {1, 3}], [{3}, {1, 2}], [{1, 2}, {3}], [{1, 3}, {2}], [{2, 3}, {1}], [{1, 2, 3}]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4]) sage: all([sp in OS for sp in OS]) True
self) |
TESTS:
sage: repr(OrderedSetPartitions([1,2,3,4])) 'Ordered set partitions of {1, 2, 3, 4}'
Class: OrderedSetPartitions_scomp
self, s, comp) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1]) sage: OS == loads(dumps(OS)) True
Functions: count,
iterator
self) |
sage: OrderedSetPartitions(5,[2,3]).count() 10 sage: OrderedSetPartitions(0, []).count() 1 sage: OrderedSetPartitions(0, [0]).count() 1 sage: OrderedSetPartitions(0, [0,0]).count() 1 sage: OrderedSetPartitions(5, [2,0,3]).count() 10
self) |
TESTS:
sage: OrderedSetPartitions([1,2,3,4], [2,1,1]).list() # indirect doctest [[{1, 2}, {3}, {4}], [{1, 2}, {4}, {3}], [{1, 3}, {2}, {4}], [{1, 4}, {2}, {3}], [{1, 3}, {4}, {2}], [{1, 4}, {3}, {2}], [{2, 3}, {1}, {4}], [{2, 4}, {1}, {3}], [{3, 4}, {1}, {2}], [{2, 3}, {4}, {1}], [{2, 4}, {3}, {1}], [{3, 4}, {2}, {1}]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1]) sage: all([ sp in OS for sp in OS]) True sage: OS.count() 12 sage: len(filter(lambda x: x in OS, OrderedSetPartitions([1,2,3,4]))) 12
self) |
TESTS:
sage: repr(OrderedSetPartitions([1,2,3,4], [2,1,1])) 'Ordered set partitions of {1, 2, 3, 4} into parts of size [2, 1, 1]'
Class: OrderedSetPartitions_sn
self, s, n) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], 2) sage: OS == loads(dumps(OS)) True
Functions: count,
iterator
self) |
sage: OrderedSetPartitions(4,2).count() 14 sage: OrderedSetPartitions(4,1).count() 1
self) |
sage: OrderedSetPartitions([1,2,3,4], 2).list() # indirect doctest [[{1}, {2, 3, 4}], [{2}, {1, 3, 4}], [{3}, {1, 2, 4}], [{4}, {1, 2, 3}], [{1, 2}, {3, 4}], [{1, 3}, {2, 4}], [{1, 4}, {2, 3}], [{2, 3}, {1, 4}], [{2, 4}, {1, 3}], [{3, 4}, {1, 2}], [{1, 2, 3}, {4}], [{1, 2, 4}, {3}], [{1, 3, 4}, {2}], [{2, 3, 4}, {1}]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], 2) sage: all([sp in OS for sp in OS]) True sage: OS.count() 14 sage: len(filter(lambda x: x in OS, OrderedSetPartitions([1,2,3,4]))) 14
self) |
TESTS:
sage: repr(OrderedSetPartitions([1,2,3,4], 2)) 'Ordered set partitions of {1, 2, 3, 4} into 2 parts'