Subsets

class sympy.combinatorics.subsets.Subset(subset, superset)

Represents a basic subset object.

Explanation

We generate subsets using essentially two techniques, binary enumeration and lexicographic enumeration. The Subset class takes two arguments, the first one describes the initial subset to consider and the second describes the superset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
['b']
>>> a.prev_binary().subset
['c']

classmethod bitlist_from_subset(subset, superset)

Gets the bitlist corresponding to a subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> Subset.bitlist_from_subset(['c', 'd'], ['a', 'b', 'c', 'd'])
'0011'

See also

subset_from_bitlist

property cardinality

Returns the number of all possible subsets.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.cardinality
16

See also

subset, superset, size, superset_size

iterate_binary(k)

This is a helper function. It iterates over the binary subsets by k steps. This variable can be both positive or negative.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.iterate_binary(-2).subset
['d']
>>> a = Subset(['a', 'b', 'c'], ['a', 'b', 'c', 'd'])
>>> a.iterate_binary(2).subset
[]

See also

next_binary, prev_binary

iterate_graycode(k)

Helper function used for prev_gray and next_gray. It performs k step overs to get the respective Gray codes.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.iterate_graycode(3).subset
[1, 4]
>>> a.iterate_graycode(-2).subset
[1, 2, 4]

See also

next_gray, prev_gray

next_binary()

Generates the next binary ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
['b']
>>> a = Subset(['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
[]

See also

prev_binary, iterate_binary

next_gray()

Generates the next Gray code ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.next_gray().subset
[1, 3]

See also

iterate_graycode, prev_gray

next_lexicographic()

Generates the next lexicographically ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
['d']
>>> a = Subset(['d'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
[]

See also

prev_lexicographic

prev_binary()

Generates the previous binary ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.prev_binary().subset
['a', 'b', 'c', 'd']
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.prev_binary().subset
['c']

See also

next_binary, iterate_binary

prev_gray()

Generates the previous Gray code ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([2, 3, 4], [1, 2, 3, 4, 5])
>>> a.prev_gray().subset
[2, 3, 4, 5]

See also

iterate_graycode, next_gray

prev_lexicographic()

Generates the previous lexicographically ordered subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['d']
>>> a = Subset(['c','d'], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['c']

See also

next_lexicographic

property rank_binary

Computes the binary ordered rank.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset([], ['a','b','c','d'])
>>> a.rank_binary
0
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.rank_binary
3

See also

iterate_binary, unrank_binary

property rank_gray

Computes the Gray code ranking of the subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c','d'], ['a','b','c','d'])
>>> a.rank_gray
2
>>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
>>> a.rank_gray
27

See also

iterate_graycode, unrank_gray

property rank_lexicographic

Computes the lexicographic ranking of the subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.rank_lexicographic
14
>>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
>>> a.rank_lexicographic
43

property size

Gets the size of the subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.size
2

See also

subset, superset, superset_size, cardinality

property subset

Gets the subset represented by the current instance.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.subset
['c', 'd']

See also

superset, size, superset_size, cardinality

classmethod subset_from_bitlist(super_set, bitlist)

Gets the subset defined by the bitlist.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> Subset.subset_from_bitlist(['a', 'b', 'c', 'd'], '0011').subset
['c', 'd']

See also

bitlist_from_subset

classmethod subset_indices(subset, superset)

Return indices of subset in superset in a list; the list is empty if all elements of subset are not in superset.

Examples

>>> from sympy.combinatorics import Subset
>>> superset = [1, 3, 2, 5, 4]
>>> Subset.subset_indices([3, 2, 1], superset)
[1, 2, 0]
>>> Subset.subset_indices([1, 6], superset)
[]
>>> Subset.subset_indices([], superset)
[]

property superset

Gets the superset of the subset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset
['a', 'b', 'c', 'd']

See also

subset, size, superset_size, cardinality

property superset_size

Returns the size of the superset.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset_size
4

See also

subset, superset, size, cardinality

classmethod unrank_binary(rank, superset)

Gets the binary ordered subset of the specified rank.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> Subset.unrank_binary(4, ['a', 'b', 'c', 'd']).subset
['b']

See also

iterate_binary, rank_binary

classmethod unrank_gray(rank, superset)

Gets the Gray code ordered subset of the specified rank.

Examples

>>> from sympy.combinatorics.subsets import Subset
>>> Subset.unrank_gray(4, ['a', 'b', 'c']).subset
['a', 'b']
>>> Subset.unrank_gray(0, ['a', 'b', 'c']).subset
[]

See also

iterate_graycode, rank_gray

subsets.ksubsets(k)

Finds the subsets of size k in lexicographic order.

This uses the itertools generator.

Examples

>>> from sympy.combinatorics.subsets import ksubsets
>>> list(ksubsets([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]
>>> list(ksubsets([1, 2, 3, 4, 5], 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4),     (2, 5), (3, 4), (3, 5), (4, 5)]

See also

Subset