18.24 Ordered Set Partitions

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

OrderedSetPartitions( 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

class OrderedSetPartitions_s

OrderedSetPartitions_s( self, s)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4])
sage: OS == loads(dumps(OS))
True

Functions: count, $\,$ iterator

count( 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

iterator( 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__

__contains__( self, x)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4])
sage: all([sp in OS for sp in OS])
True

__repr__( self)

TESTS:

sage: repr(OrderedSetPartitions([1,2,3,4]))
'Ordered set partitions of {1, 2, 3, 4}'

Class: OrderedSetPartitions_scomp

class OrderedSetPartitions_scomp

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

count( 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

iterator( 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__

__contains__( 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

__repr__( 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

class OrderedSetPartitions_sn

OrderedSetPartitions_sn( self, s, n)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], 2)
sage: OS == loads(dumps(OS))
True

Functions: count, $\,$ iterator

count( self)

sage: OrderedSetPartitions(4,2).count()
14
sage: OrderedSetPartitions(4,1).count()
1

iterator( 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__

__contains__( 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

__repr__( self)

TESTS:

sage: repr(OrderedSetPartitions([1,2,3,4], 2))
'Ordered set partitions of {1, 2, 3, 4} into 2 parts'

See About this document... for information on suggesting changes.