# Subsets¶

class diofant.combinatorics.subsets.Subset[source]

Represents a basic subset object.

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

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
['b']
>>> a.prev_binary().subset
['c']

classmethod bitlist_from_subset(subset, superset)[source]

Gets the bitlist corresponding to a subset.

Examples

>>> Subset.bitlist_from_subset(['c', 'd'], ['a', 'b', 'c', 'd'])
'0011'

property cardinality

Returns the number of all possible subsets.

Examples

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.cardinality
16

iterate_binary(k)[source]

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

Examples

>>> 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
[]

iterate_graycode(k)[source]

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

Examples

>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.iterate_graycode(3).subset
[1, 4]
>>> a.iterate_graycode(-2).subset
[1, 2, 4]

next_binary()[source]

Generates the next binary ordered subset.

Examples

>>> 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
[]

next_gray()[source]

Generates the next Gray code ordered subset.

Examples

>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.next_gray().subset
[1, 3]

next_lexicographic()[source]

Generates the next lexicographically ordered subset.

Examples

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
['d']
>>> a = Subset(['d'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
[]

prev_binary()[source]

Generates the previous binary ordered subset.

Examples

>>> 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']

prev_gray()[source]

Generates the previous Gray code ordered subset.

Examples

>>> a = Subset([2, 3, 4], [1, 2, 3, 4, 5])
>>> a.prev_gray().subset
[2, 3, 4, 5]

prev_lexicographic()[source]

Generates the previous lexicographically ordered subset.

Examples

>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['d']
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['c']

property rank_binary

Computes the binary ordered rank.

Examples

>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.rank_binary
0
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.rank_binary
3

property rank_gray

Computes the Gray code ranking of the subset.

Examples

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

property rank_lexicographic

Computes the lexicographic ranking of the subset.

Examples

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

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.size
2

property subset

Gets the subset represented by the current instance.

Examples

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.subset
['c', 'd']

classmethod subset_from_bitlist(super_set, bitlist)[source]

Gets the subset defined by the bitlist.

Examples

>>> Subset.subset_from_bitlist(['a', 'b', 'c', 'd'], '0011').subset
['c', 'd']

classmethod subset_indices(subset, superset)[source]

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

Examples

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

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset
['a', 'b', 'c', 'd']

property superset_size

Returns the size of the superset.

Examples

>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset_size
4

classmethod unrank_binary(rank, superset)[source]

Gets the binary ordered subset of the specified rank.

Examples

>>> Subset.unrank_binary(4, ['a', 'b', 'c', 'd']).subset
['b']

classmethod unrank_gray(rank, superset)[source]

Gets the Gray code ordered subset of the specified rank.

Examples

>>> Subset.unrank_gray(4, ['a', 'b', 'c']).subset
['a', 'b']
>>> Subset.unrank_gray(0, ['a', 'b', 'c']).subset
[]

subsets.ksubsets(k)

Finds the subsets of size k in lexicographic order.

This uses the itertools generator.

Examples

>>> 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)]