Iterables

variations

variations(seq, n) Returns all the variations of the list of size n.

Has an optional third argument. Must be a boolean value and makes the method return the variations with repetition if set to True, or the variations without repetition if set to False.

Examples::

>>> from sympy.utilities.iterables import variations
>>> list(variations([1,2,3], 2))
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
>>> list(variations([1,2,3], 2, True))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

partitions

Although the combinatorics module contains Partition and IntegerPartition classes for investigation and manipulation of partitions, there are a few functions to generate partitions that can be used as low-level tools for routines: partitions and multiset_partitions. The former gives integer partitions, and the latter gives enumerated partitions of elements. There is also a routine kbins that will give a variety of permutations of partions.

partitions:

>>> from sympy.utilities.iterables import partitions
>>> [p.copy() for s, p in partitions(7, m=2, size=True) if s == 2]
[{1: 1, 6: 1}, {2: 1, 5: 1}, {3: 1, 4: 1}]

multiset_partitions:

>>> from sympy.utilities.iterables import multiset_partitions
>>> [p for p in multiset_partitions(3, 2)]
[[[0, 1], [2]], [[0, 2], [1]], [[0], [1, 2]]]
>>> [p for p in multiset_partitions([1, 1, 1, 2], 2)]
[[[1, 1, 1], [2]], [[1, 1, 2], [1]], [[1, 1], [1, 2]]]

kbins:

>>> from sympy.utilities.iterables import kbins
>>> def show(k):
...     rv = []
...     for p in k:
...         rv.append(','.join([''.join(j) for j in p]))
...     return sorted(rv)
...
>>> show(kbins("ABCD", 2))
['A,BCD', 'AB,CD', 'ABC,D']
>>> show(kbins("ABC", 2))
['A,BC', 'AB,C']
>>> show(kbins("ABC", 2, ordered=0))  # same as multiset_partitions
['A,BC', 'AB,C', 'AC,B']
>>> show(kbins("ABC", 2, ordered=1))
['A,BC', 'A,CB',
 'B,AC', 'B,CA',
 'C,AB', 'C,BA']
>>> show(kbins("ABC", 2, ordered=10))
['A,BC', 'AB,C', 'AC,B',
 'B,AC', 'BC,A',
 'C,AB']
>>> show(kbins("ABC", 2, ordered=11))
['A,BC', 'A,CB', 'AB,C', 'AC,B',
 'B,AC', 'B,CA', 'BA,C', 'BC,A',
 'C,AB', 'C,BA', 'CA,B', 'CB,A']

Docstring

class sympy.utilities.iterables.NotIterable[source]: Use this as mixin when creating a class which is not supposed to return true when iterable() is called on its instances because calling list() on the instance, for example, would result in an infinite loop.

sympy.utilities.iterables.binary_partitions(n)[source]

Generates the binary partition of n.

A binary partition consists only of numbers that are powers of two. Each step reduces a \(2^{k+1}\) to \(2^k\) and \(2^k\). Thus 16 is converted to 8 and 8.

Examples

>>> from sympy.utilities.iterables import binary_partitions
>>> for i in binary_partitions(5):
...     print(i)
...
[4, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

References

R953: TAOCP 4, section 7.2.1.5, problem 64

sympy.utilities.iterables.bracelets(n, k)[source]: Wrapper to necklaces to return a free (unrestricted) necklace.

sympy.utilities.iterables.capture(func)[source]

Return the printed output of func().

func should be a function without arguments that produces output with print statements.

>>> from sympy.utilities.iterables import capture
>>> from sympy import pprint
>>> from sympy.abc import x
>>> def foo():
...     print('hello world!')
...
>>> 'hello' in capture(foo) # foo, not foo()
True
>>> capture(lambda: pprint(2/x))
'2\n-\nx\n'

sympy.utilities.iterables.common_prefix(*seqs)[source]

Return the subsequence that is a common start of sequences in seqs.

>>> from sympy.utilities.iterables import common_prefix
>>> common_prefix(list(range(3)))
[0, 1, 2]
>>> common_prefix(list(range(3)), list(range(4)))
[0, 1, 2]
>>> common_prefix([1, 2, 3], [1, 2, 5])
[1, 2]
>>> common_prefix([1, 2, 3], [1, 3, 5])
[1]

sympy.utilities.iterables.common_suffix(*seqs)[source]

Return the subsequence that is a common ending of sequences in seqs.

>>> from sympy.utilities.iterables import common_suffix
>>> common_suffix(list(range(3)))
[0, 1, 2]
>>> common_suffix(list(range(3)), list(range(4)))
[]
>>> common_suffix([1, 2, 3], [9, 2, 3])
[2, 3]
>>> common_suffix([1, 2, 3], [9, 7, 3])
[3]

sympy.utilities.iterables.connected_components(G)[source]

Connected components of an undirected graph or weakly connected components of a directed graph.

Parameters: graph : tuple[list, list[tuple[T, T]]

A tuple consisting of a list of vertices and a list of edges of a graph whose connected components are to be found.

Examples

Given an undirected graph:

graph {
    A -- B
    C -- D
}

We can find the connected components using this function if we include each edge in both directions:

>>> from sympy.utilities.iterables import connected_components

>>> V = ['A', 'B', 'C', 'D']
>>> E = [('A', 'B'), ('B', 'A'), ('C', 'D'), ('D', 'C')]
>>> connected_components((V, E))
[['A', 'B'], ['C', 'D']]

The weakly connected components of a directed graph can found the same way.

Notes

The vertices of the graph must be hashable for the data structures used. If the vertices are unhashable replace them with integer indices.

This function uses Tarjan’s algorithm to compute the connected components in \(O(|V|+|E|)\) (linear) time.

References

R954: https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
R955: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

sympy.utilities.iterables.dict_merge(*dicts)[source]: Merge dictionaries into a single dictionary.

sympy.utilities.iterables.filter_symbols(iterator, exclude)[source]

Only yield elements from \(iterator\) that do not occur in \(exclude\).

Parameters

iterator : iterable

iterator to take elements from

exclude : iterable

elements to exclude

Returns

iterator : iterator

filtered iterator

sympy.utilities.iterables.flatten(iterable, levels=None, cls=None)[source]

Recursively denest iterable containers.

>>> from sympy.utilities.iterables import flatten

>>> flatten([1, 2, 3])
[1, 2, 3]
>>> flatten([1, 2, [3]])
[1, 2, 3]
>>> flatten([1, [2, 3], [4, 5]])
[1, 2, 3, 4, 5]
>>> flatten([1.0, 2, (1, None)])
[1.0, 2, 1, None]

If you want to denest only a specified number of levels of nested containers, then set levels flag to the desired number of levels:

>>> ls = [[(-2, -1), (1, 2)], [(0, 0)]]

>>> flatten(ls, levels=1)
[(-2, -1), (1, 2), (0, 0)]

If cls argument is specified, it will only flatten instances of that class, for example:

>>> from sympy.core import Basic, S
>>> class MyOp(Basic):
...     pass
...
>>> flatten([MyOp(S(1), MyOp(S(2), S(3)))], cls=MyOp)
[1, 2, 3]

adapted from https://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks

sympy.utilities.iterables.generate_bell(n)[source]

Return permutations of [0, 1, …, n - 1] such that each permutation differs from the last by the exchange of a single pair of neighbors. The n! permutations are returned as an iterator. In order to obtain the next permutation from a random starting permutation, use the next_trotterjohnson method of the Permutation class (which generates the same sequence in a different manner).

Examples

>>> from itertools import permutations
>>> from sympy.utilities.iterables import generate_bell
>>> from sympy import zeros, Matrix

This is the sort of permutation used in the ringing of physical bells, and does not produce permutations in lexicographical order. Rather, the permutations differ from each other by exactly one inversion, and the position at which the swapping occurs varies periodically in a simple fashion. Consider the first few permutations of 4 elements generated by permutations and generate_bell:

>>> list(permutations(range(4)))[:5]
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2)]
>>> list(generate_bell(4))[:5]
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 3, 1, 2), (3, 0, 1, 2), (3, 0, 2, 1)]

Notice how the 2nd and 3rd lexicographical permutations have 3 elements out of place whereas each “bell” permutation always has only two elements out of place relative to the previous permutation (and so the signature (+/-1) of a permutation is opposite of the signature of the previous permutation).

How the position of inversion varies across the elements can be seen by tracing out where the largest number appears in the permutations:

>>> m = zeros(4, 24)
>>> for i, p in enumerate(generate_bell(4)):
...     m[:, i] = Matrix([j - 3 for j in list(p)])  # make largest zero
>>> m.print_nonzero('X')
[XXX  XXXXXX  XXXXXX  XXX]
[XX XX XXXX XX XXXX XX XX]
[X XXXX XX XXXX XX XXXX X]
[ XXXXXX  XXXXXX  XXXXXX ]

References

R956: https://en.wikipedia.org/wiki/Method_ringing
R957: https://stackoverflow.com/questions/4856615/recursive-permutation/4857018
R958: http://programminggeeks.com/bell-algorithm-for-permutation/
R959: https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm
R960: Generating involutions, derangements, and relatives by ECO Vincent Vajnovszki, DMTCS vol 1 issue 12, 2010

sympy.utilities.iterables.generate_derangements(s)[source]

Return unique derangements of the elements of iterable s.

Examples

>>> from sympy.utilities.iterables import generate_derangements
>>> list(generate_derangements([0, 1, 2]))
[[1, 2, 0], [2, 0, 1]]
>>> list(generate_derangements([0, 1, 2, 2]))
[[2, 2, 0, 1], [2, 2, 1, 0]]
>>> list(generate_derangements([0, 1, 1]))
[]

sympy.utilities.iterables.generate_involutions(n)[source]

Generates involutions.

An involution is a permutation that when multiplied by itself equals the identity permutation. In this implementation the involutions are generated using Fixed Points.

Alternatively, an involution can be considered as a permutation that does not contain any cycles with a length that is greater than two.

Examples

>>> from sympy.utilities.iterables import generate_involutions
>>> list(generate_involutions(3))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 1, 0)]
>>> len(list(generate_involutions(4)))
10

References

R961: http://mathworld.wolfram.com/PermutationInvolution.html

sympy.utilities.iterables.generate_oriented_forest(n)[source]

This algorithm generates oriented forests.

An oriented graph is a directed graph having no symmetric pair of directed edges. A forest is an acyclic graph, i.e., it has no cycles. A forest can also be described as a disjoint union of trees, which are graphs in which any two vertices are connected by exactly one simple path.

Examples

>>> from sympy.utilities.iterables import generate_oriented_forest
>>> list(generate_oriented_forest(4))
[[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0],     [0, 1, 1, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0]]

References

R962: T. Beyer and S.M. Hedetniemi: constant time generation of rooted trees, SIAM J. Computing Vol. 9, No. 4, November 1980
R963: https://stackoverflow.com/questions/1633833/oriented-forest-taocp-algorithm-in-python

sympy.utilities.iterables.group(seq, multiple=True)[source]

Splits a sequence into a list of lists of equal, adjacent elements.

Examples

>>> from sympy.utilities.iterables import group

>>> group([1, 1, 1, 2, 2, 3])
[[1, 1, 1], [2, 2], [3]]
>>> group([1, 1, 1, 2, 2, 3], multiple=False)
[(1, 3), (2, 2), (3, 1)]
>>> group([1, 1, 3, 2, 2, 1], multiple=False)
[(1, 2), (3, 1), (2, 2), (1, 1)]

See also

multiset

sympy.utilities.iterables.has_dups(seq)[source]

Return True if there are any duplicate elements in seq.

Examples

>>> from sympy.utilities.iterables import has_dups
>>> from sympy import Dict, Set

>>> has_dups((1, 2, 1))
True
>>> has_dups(range(3))
False
>>> all(has_dups(c) is False for c in (set(), Set(), dict(), Dict()))
True

sympy.utilities.iterables.has_variety(seq)[source]

Return True if there are any different elements in seq.

Examples

>>> from sympy.utilities.iterables import has_variety

>>> has_variety((1, 2, 1))
True
>>> has_variety((1, 1, 1))
False

sympy.utilities.iterables.ibin(n, bits=None, str=False)[source]

Return a list of length bits corresponding to the binary value of n with small bits to the right (last). If bits is omitted, the length will be the number required to represent n. If the bits are desired in reversed order, use the [::-1] slice of the returned list.

If a sequence of all bits-length lists starting from [0, 0,..., 0] through [1, 1, ..., 1] are desired, pass a non-integer for bits, e.g. 'all'.

If the bit string is desired pass str=True.

Examples

>>> from sympy.utilities.iterables import ibin
>>> ibin(2)
[1, 0]
>>> ibin(2, 4)
[0, 0, 1, 0]

If all lists corresponding to 0 to 2**n - 1, pass a non-integer for bits:

>>> bits = 2
>>> for i in ibin(2, 'all'):
...     print(i)
(0, 0)
(0, 1)
(1, 0)
(1, 1)

If a bit string is desired of a given length, use str=True:

>>> n = 123
>>> bits = 10
>>> ibin(n, bits, str=True)
'0001111011'
>>> ibin(n, bits, str=True)[::-1]  # small bits left
'1101111000'
>>> list(ibin(3, 'all', str=True))
['000', '001', '010', '011', '100', '101', '110', '111']

sympy.utilities.iterables.iproduct(*iterables)[source]

Cartesian product of iterables.

Generator of the cartesian product of iterables. This is analogous to itertools.product except that it works with infinite iterables and will yield any item from the infinite product eventually.

Examples

>>> from sympy.utilities.iterables import iproduct
>>> sorted(iproduct([1,2], [3,4]))
[(1, 3), (1, 4), (2, 3), (2, 4)]

With an infinite iterator:

>>> from sympy import S
>>> (3,) in iproduct(S.Integers)
True
>>> (3, 4) in iproduct(S.Integers, S.Integers)
True

See also

itertools.product

sympy.utilities.iterables.is_palindromic(s, i=0, j=None)[source]

return True if the sequence is the same from left to right as it is from right to left in the whole sequence (default) or in the Python slice s[i: j]; else False.

Examples

>>> from sympy.utilities.iterables import is_palindromic
>>> is_palindromic([1, 0, 1])
True
>>> is_palindromic('abcbb')
False
>>> is_palindromic('abcbb', 1)
False

Normal Python slicing is performed in place so there is no need to create a slice of the sequence for testing:

>>> is_palindromic('abcbb', 1, -1)
True
>>> is_palindromic('abcbb', -4, -1)
True

See also

sympy.ntheory.digits.is_palindromic: tests integers

sympy.utilities.iterables.is_sequence(i, include=None)[source]

Return a boolean indicating whether i is a sequence in the SymPy sense. If anything that fails the test below should be included as being a sequence for your application, set ‘include’ to that object’s type; multiple types should be passed as a tuple of types.

Note: although generators can generate a sequence, they often need special handling to make sure their elements are captured before the generator is exhausted, so these are not included by default in the definition of a sequence.

See also

partitions, multiset_partitions

sympy.utilities.iterables.least_rotation(x, key=None)[source]

Returns the number of steps of left rotation required to obtain lexicographically minimal string/list/tuple, etc.

Examples

>>> from sympy.utilities.iterables import least_rotation, rotate_left
>>> a = [3, 1, 5, 1, 2]
>>> least_rotation(a)
3
>>> rotate_left(a, _)
[1, 2, 3, 1, 5]

References

R964: https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation

sympy.utilities.iterables.minlex(seq, directed=True, key=None)[source]

Return the rotation of the sequence in which the lexically smallest elements appear first, e.g. \(cba \rightarrow acb\).

The sequence returned is a tuple, unless the input sequence is a string in which case a string is returned.

If directed is False then the smaller of the sequence and the reversed sequence is returned, e.g. \(cba \rightarrow abc\).

If key is not None then it is used to extract a comparison key from each element in iterable.

Examples

>>> from sympy.combinatorics.polyhedron import minlex
>>> minlex((1, 2, 0))
(0, 1, 2)
>>> minlex((1, 0, 2))
(0, 2, 1)
>>> minlex((1, 0, 2), directed=False)
(0, 1, 2)

>>> minlex('11010011000', directed=True)
'00011010011'
>>> minlex('11010011000', directed=False)
'00011001011'

>>> minlex(('bb', 'aaa', 'c', 'a'))
('a', 'bb', 'aaa', 'c')
>>> minlex(('bb', 'aaa', 'c', 'a'), key=len)
('c', 'a', 'bb', 'aaa')

sympy.utilities.iterables.multiset(seq)[source]

Return the hashable sequence in multiset form with values being the multiplicity of the item in the sequence.

Examples

>>> from sympy.utilities.iterables import multiset
>>> multiset('mississippi')
{'i': 4, 'm': 1, 'p': 2, 's': 4}

See also

group

sympy.utilities.iterables.multiset_combinations(m, n, g=None)[source]

Return the unique combinations of size n from multiset m.

Examples

>>> from sympy.utilities.iterables import multiset_combinations
>>> from itertools import combinations
>>> [''.join(i) for i in  multiset_combinations('baby', 3)]
['abb', 'aby', 'bby']

>>> def count(f, s): return len(list(f(s, 3)))

The number of combinations depends on the number of letters; the number of unique combinations depends on how the letters are repeated.

>>> s1 = 'abracadabra'
>>> s2 = 'banana tree'
>>> count(combinations, s1), count(multiset_combinations, s1)
(165, 23)
>>> count(combinations, s2), count(multiset_combinations, s2)
(165, 54)

sympy.utilities.iterables.multiset_derangements(s)[source]

Generate derangements of the elements of s in place.

Examples

>>> from sympy.utilities.iterables import multiset_derangements, uniq

Because the derangements of multisets (not sets) are generated in place, copies of the return value must be made if a collection of derangements is desired or else all values will be the same:

>>> list(uniq([i for i in multiset_derangements('1233')]))
[[None, None, None, None]]
>>> [i.copy() for i in multiset_derangements('1233')]
[['3', '3', '1', '2'], ['3', '3', '2', '1']]
>>> [''.join(i) for i in multiset_derangements('1233')]
['3312', '3321']

sympy.utilities.iterables.multiset_partitions(multiset, m=None)[source]

Return unique partitions of the given multiset (in list form). If m is None, all multisets will be returned, otherwise only partitions with m parts will be returned.

If multiset is an integer, a range [0, 1, …, multiset - 1] will be supplied.

Examples

>>> from sympy.utilities.iterables import multiset_partitions
>>> list(multiset_partitions([1, 2, 3, 4], 2))
[[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 2], [3, 4]],
[[1, 3, 4], [2]], [[1, 3], [2, 4]], [[1, 4], [2, 3]],
[[1], [2, 3, 4]]]
>>> list(multiset_partitions([1, 2, 3, 4], 1))
[[[1, 2, 3, 4]]]

Only unique partitions are returned and these will be returned in a canonical order regardless of the order of the input:

>>> a = [1, 2, 2, 1]
>>> ans = list(multiset_partitions(a, 2))
>>> a.sort()
>>> list(multiset_partitions(a, 2)) == ans
True
>>> a = range(3, 1, -1)
>>> (list(multiset_partitions(a)) ==
...  list(multiset_partitions(sorted(a))))
True

If m is omitted then all partitions will be returned:

>>> list(multiset_partitions([1, 1, 2]))
[[[1, 1, 2]], [[1, 1], [2]], [[1, 2], [1]], [[1], [1], [2]]]
>>> list(multiset_partitions([1]*3))
[[[1, 1, 1]], [[1], [1, 1]], [[1], [1], [1]]]

Counting

The number of partitions of a set is given by the bell number:

>>> from sympy import bell
>>> len(list(multiset_partitions(5))) == bell(5) == 52
True

The number of partitions of length k from a set of size n is given by the Stirling Number of the 2nd kind:

>>> from sympy.functions.combinatorial.numbers import stirling
>>> stirling(5, 2) == len(list(multiset_partitions(5, 2))) == 15
True

These comments on counting apply to sets, not multisets.

Notes

When all the elements are the same in the multiset, the order of the returned partitions is determined by the partitions routine. If one is counting partitions then it is better to use the nT function.

sympy.utilities.iterables.multiset_permutations(m, size=None, g=None)[source]

Return the unique permutations of multiset m.

Examples

>>> from sympy.utilities.iterables import multiset_permutations
>>> from sympy import factorial
>>> [''.join(i) for i in multiset_permutations('aab')]
['aab', 'aba', 'baa']
>>> factorial(len('banana'))
720
>>> len(list(multiset_permutations('banana')))
60

sympy.utilities.iterables.necklaces(n, k, free=False)[source]

A routine to generate necklaces that may (free=True) or may not (free=False) be turned over to be viewed. The “necklaces” returned are comprised of n integers (beads) with k different values (colors). Only unique necklaces are returned.

Examples

>>> from sympy.utilities.iterables import necklaces, bracelets
>>> def show(s, i):
...     return ''.join(s[j] for j in i)

The “unrestricted necklace” is sometimes also referred to as a “bracelet” (an object that can be turned over, a sequence that can be reversed) and the term “necklace” is used to imply a sequence that cannot be reversed. So ACB == ABC for a bracelet (rotate and reverse) while the two are different for a necklace since rotation alone cannot make the two sequences the same.

(mnemonic: Bracelets can be viewed Backwards, but Not Necklaces.)

>>> B = [show('ABC', i) for i in bracelets(3, 3)]
>>> N = [show('ABC', i) for i in necklaces(3, 3)]
>>> set(N) - set(B)
{'ACB'}

>>> list(necklaces(4, 2))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1),
 (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]

>>> [show('.o', i) for i in bracelets(4, 2)]
['....', '...o', '..oo', '.o.o', '.ooo', 'oooo']

References

R965: http://mathworld.wolfram.com/Necklace.html

sympy.utilities.iterables.numbered_symbols(prefix='x', cls=None, start=0, exclude=(), *args, **assumptions)[source]

Generate an infinite stream of Symbols consisting of a prefix and increasing subscripts provided that they do not occur in exclude.

Parameters

prefix : str, optional

The prefix to use. By default, this function will generate symbols of the form “x0”, “x1”, etc.

cls : class, optional

The class to use. By default, it uses Symbol, but you can also use Wild or Dummy.

start : int, optional

The start number. By default, it is 0.

Returns

sym : Symbol

The subscripted symbols.

sympy.utilities.iterables.ordered_partitions(n, m=None, sort=True)[source]

Generates ordered partitions of integer n.

Parameters

m : integer (default None)

The default value gives partitions of all sizes else only those with size m. In addition, if m is not None then partitions are generated in place (see examples).

sort : bool (default True)

Controls whether partitions are returned in sorted order when m is not None; when False, the partitions are returned as fast as possible with elements sorted, but when m|n the partitions will not be in ascending lexicographical order.

Examples

>>> from sympy.utilities.iterables import ordered_partitions

All partitions of 5 in ascending lexicographical:

>>> for p in ordered_partitions(5):
...     print(p)
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

Only partitions of 5 with two parts:

>>> for p in ordered_partitions(5, 2):
...     print(p)
[1, 4]
[2, 3]

When m is given, a given list objects will be used more than once for speed reasons so you will not see the correct partitions unless you make a copy of each as it is generated:

>>> [p for p in ordered_partitions(7, 3)]
[[1, 1, 1], [1, 1, 1], [1, 1, 1], [2, 2, 2]]
>>> [list(p) for p in ordered_partitions(7, 3)]
[[1, 1, 5], [1, 2, 4], [1, 3, 3], [2, 2, 3]]

When n is a multiple of m, the elements are still sorted but the partitions themselves will be unordered if sort is False; the default is to return them in ascending lexicographical order.

>>> for p in ordered_partitions(6, 2):
...     print(p)
[1, 5]
[2, 4]
[3, 3]

But if speed is more important than ordering, sort can be set to False:

>>> for p in ordered_partitions(6, 2, sort=False):
...     print(p)
[1, 5]
[3, 3]
[2, 4]

References

R966: Generating Integer Partitions, [online], Available: https://jeromekelleher.net/generating-integer-partitions.html
R967: Jerome Kelleher and Barry O’Sullivan, “Generating All Partitions: A Comparison Of Two Encodings”, [online], Available: https://arxiv.org/pdf/0909.2331v2.pdf

sympy.utilities.iterables.partitions(n, m=None, k=None, size=False)[source]

Generate all partitions of positive integer, n.

Parameters

m : integer (default gives partitions of all sizes)

limits number of parts in partition (mnemonic: m, maximum parts)

k : integer (default gives partitions number from 1 through n)

limits the numbers that are kept in the partition (mnemonic: k, keys)

size : bool (default False, only partition is returned)

when True then (M, P) is returned where M is the sum of the multiplicities and P is the generated partition.

Each partition is represented as a dictionary, mapping an integer

to the number of copies of that integer in the partition. For example,

the first partition of 4 returned is {4: 1}, “4: one of them”.

Examples

>>> from sympy.utilities.iterables import partitions

The numbers appearing in the partition (the key of the returned dict) are limited with k:

>>> for p in partitions(6, k=2):  
...     print(p)
{2: 3}
{1: 2, 2: 2}
{1: 4, 2: 1}
{1: 6}

The maximum number of parts in the partition (the sum of the values in the returned dict) are limited with m (default value, None, gives partitions from 1 through n):

>>> for p in partitions(6, m=2):  
...     print(p)
...
{6: 1}
{1: 1, 5: 1}
{2: 1, 4: 1}
{3: 2}

References

R968: modified from Tim Peter’s version to allow for k and m values: http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

sympy.utilities.iterables.permute_signs(t)[source]

Return iterator in which the signs of non-zero elements of t are permuted.

Examples

>>> from sympy.utilities.iterables import permute_signs
>>> list(permute_signs((0, 1, 2)))
[(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2)]

sympy.utilities.iterables.postfixes(seq)[source]

Generate all postfixes of a sequence.

Examples

>>> from sympy.utilities.iterables import postfixes

>>> list(postfixes([1,2,3,4]))
[[4], [3, 4], [2, 3, 4], [1, 2, 3, 4]]

sympy.utilities.iterables.prefixes(seq)[source]

Generate all prefixes of a sequence.

Examples

>>> from sympy.utilities.iterables import prefixes

>>> list(prefixes([1,2,3,4]))
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]

sympy.utilities.iterables.random_derangement(t, choice=None, strict=True)[source]

Return a list of elements in which none are in the same positions as they were originally. If an element fills more than half of the positions then an error will be raised since no derangement is possible. To obtain a derangement of as many items as possible–with some of the most numerous remaining in their original positions–pass \(strict=False\). To produce a pseudorandom derangment, pass a pseudorandom selector like \(choice\) (see below).

Examples

>>> from sympy.utilities.iterables import random_derangement
>>> t = 'SymPy: a CAS in pure Python'
>>> d = random_derangement(t)
>>> all(i != j for i, j in zip(d, t))
True

A predictable result can be obtained by using a pseudorandom generator for the choice:

>>> from sympy.core.random import seed, choice as c
>>> seed(1)
>>> d = [''.join(random_derangement(t, c)) for i in range(5)]
>>> assert len(set(d)) != 1  # we got different values

By reseeding, the same sequence can be obtained:

>>> seed(1)
>>> d2 = [''.join(random_derangement(t, c)) for i in range(5)]
>>> assert d == d2

sympy.utilities.iterables.reshape(seq, how)[source]

Reshape the sequence according to the template in how.

Examples

>>> from sympy.utilities import reshape
>>> seq = list(range(1, 9))

>>> reshape(seq, [4]) # lists of 4
[[1, 2, 3, 4], [5, 6, 7, 8]]

>>> reshape(seq, (4,)) # tuples of 4
[(1, 2, 3, 4), (5, 6, 7, 8)]

>>> reshape(seq, (2, 2)) # tuples of 4
[(1, 2, 3, 4), (5, 6, 7, 8)]

>>> reshape(seq, (2, [2])) # (i, i, [i, i])
[(1, 2, [3, 4]), (5, 6, [7, 8])]

>>> reshape(seq, ((2,), [2])) # etc....
[((1, 2), [3, 4]), ((5, 6), [7, 8])]

>>> reshape(seq, (1, [2], 1))
[(1, [2, 3], 4), (5, [6, 7], 8)]

>>> reshape(tuple(seq), ([[1], 1, (2,)],))
(([[1], 2, (3, 4)],), ([[5], 6, (7, 8)],))

>>> reshape(tuple(seq), ([1], 1, (2,)))
(([1], 2, (3, 4)), ([5], 6, (7, 8)))

>>> reshape(list(range(12)), [2, [3], {2}, (1, (3,), 1)])
[[0, 1, [2, 3, 4], {5, 6}, (7, (8, 9, 10), 11)]]

sympy.utilities.iterables.rotate_left(x, y)[source]

Left rotates a list x by the number of steps specified in y.

Examples

>>> from sympy.utilities.iterables import rotate_left
>>> a = [0, 1, 2]
>>> rotate_left(a, 1)
[1, 2, 0]

sympy.utilities.iterables.rotate_right(x, y)[source]

Right rotates a list x by the number of steps specified in y.

Examples

>>> from sympy.utilities.iterables import rotate_right
>>> a = [0, 1, 2]
>>> rotate_right(a, 1)
[2, 0, 1]

sympy.utilities.iterables.rotations(s, dir=1)[source]

Return a generator giving the items in s as list where each subsequent list has the items rotated to the left (default) or right (dir=-1) relative to the previous list.

Examples

>>> from sympy.utilities.iterables import rotations
>>> list(rotations([1,2,3]))
[[1, 2, 3], [2, 3, 1], [3, 1, 2]]
>>> list(rotations([1,2,3], -1))
[[1, 2, 3], [3, 1, 2], [2, 3, 1]]

sympy.utilities.iterables.roundrobin(*iterables)[source]

roundrobin recipe taken from itertools documentation: https://docs.python.org/2/library/itertools.html#recipes

roundrobin(‘ABC’, ‘D’, ‘EF’) –> A D E B F C

Recipe credited to George Sakkis

sympy.utilities.iterables.runs(seq, op=<built-in function gt>)[source]

Group the sequence into lists in which successive elements all compare the same with the comparison operator, op: op(seq[i + 1], seq[i]) is True from all elements in a run.

Examples

>>> from sympy.utilities.iterables import runs
>>> from operator import ge
>>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2])
[[0, 1, 2], [2], [1, 4], [3], [2], [2]]
>>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2], op=ge)
[[0, 1, 2, 2], [1, 4], [3], [2, 2]]

sympy.utilities.iterables.sift(seq, keyfunc, binary=False)[source]

Sift the sequence, seq according to keyfunc.

Returns

When binary is False (default), the output is a dictionary

where elements of seq are stored in a list keyed to the value

of keyfunc for that element. If binary is True then a tuple

with lists T and F are returned where T is a list

containing elements of seq for which keyfunc was True and

F containing those elements for which keyfunc was False;

a ValueError is raised if the keyfunc is not binary.

Examples

>>> from sympy.utilities import sift
>>> from sympy.abc import x, y
>>> from sympy import sqrt, exp, pi, Tuple

>>> sift(range(5), lambda x: x % 2)
{0: [0, 2, 4], 1: [1, 3]}

sift() returns a defaultdict() object, so any key that has no matches will give [].

>>> sift([x], lambda x: x.is_commutative)
{True: [x]}
>>> _[False]
[]

Sometimes you will not know how many keys you will get:

>>> sift([sqrt(x), exp(x), (y**x)**2],
...      lambda x: x.as_base_exp()[0])
{E: [exp(x)], x: [sqrt(x)], y: [y**(2*x)]}

Sometimes you expect the results to be binary; the results can be unpacked by setting binary to True:

>>> sift(range(4), lambda x: x % 2, binary=True)
([1, 3], [0, 2])
>>> sift(Tuple(1, pi), lambda x: x.is_rational, binary=True)
([1], [pi])

A ValueError is raised if the predicate was not actually binary (which is a good test for the logic where sifting is used and binary results were expected):

>>> unknown = exp(1) - pi  # the rationality of this is unknown
>>> args = Tuple(1, pi, unknown)
>>> sift(args, lambda x: x.is_rational, binary=True)
Traceback (most recent call last):
...
ValueError: keyfunc gave non-binary output

The non-binary sifting shows that there were 3 keys generated:

>>> set(sift(args, lambda x: x.is_rational).keys())
{None, False, True}

If you need to sort the sifted items it might be better to use ordered which can economically apply multiple sort keys to a sequence while sorting.

See also

ordered

sympy.utilities.iterables.signed_permutations(t)[source]

Return iterator in which the signs of non-zero elements of t and the order of the elements are permuted.

Examples

>>> from sympy.utilities.iterables import signed_permutations
>>> list(signed_permutations((0, 1, 2)))
[(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2), (0, 2, 1),
(0, -2, 1), (0, 2, -1), (0, -2, -1), (1, 0, 2), (-1, 0, 2),
(1, 0, -2), (-1, 0, -2), (1, 2, 0), (-1, 2, 0), (1, -2, 0),
(-1, -2, 0), (2, 0, 1), (-2, 0, 1), (2, 0, -1), (-2, 0, -1),
(2, 1, 0), (-2, 1, 0), (2, -1, 0), (-2, -1, 0)]

sympy.utilities.iterables.strongly_connected_components(G)[source]

Strongly connected components of a directed graph in reverse topological order.

Parameters: graph : tuple[list, list[tuple[T, T]]

A tuple consisting of a list of vertices and a list of edges of a graph whose strongly connected components are to be found.

Examples

Consider a directed graph (in dot notation):

digraph {
    A -> B
    A -> C
    B -> C
    C -> B
    B -> D
}

where vertices are the letters A, B, C and D. This graph can be encoded using Python’s elementary data structures as follows:

>>> V = ['A', 'B', 'C', 'D']
>>> E = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'B'), ('B', 'D')]

The strongly connected components of this graph can be computed as

>>> from sympy.utilities.iterables import strongly_connected_components

>>> strongly_connected_components((V, E))
[['D'], ['B', 'C'], ['A']]

This also gives the components in reverse topological order.

Since the subgraph containing B and C has a cycle they must be together in a strongly connected component. A and D are connected to the rest of the graph but not in a cyclic manner so they appear as their own strongly connected components.

Notes

The vertices of the graph must be hashable for the data structures used. If the vertices are unhashable replace them with integer indices.

This function uses Tarjan’s algorithm to compute the strongly connected components in \(O(|V|+|E|)\) (linear) time.

References

R969: https://en.wikipedia.org/wiki/Strongly_connected_component
R970: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

sympy.utilities.iterables.subsets(seq, k=None, repetition=False)[source]

Generates all \(k\)-subsets (combinations) from an \(n\)-element set, seq.

A \(k\)-subset of an \(n\)-element set is any subset of length exactly \(k\). The number of \(k\)-subsets of an \(n\)-element set is given by binomial(n, k), whereas there are \(2^n\) subsets all together. If \(k\) is None then all \(2^n\) subsets will be returned from shortest to longest.

Examples

>>> from sympy.utilities.iterables import subsets

subsets(seq, k) will return the \(\frac{n!}{k!(n - k)!}\) \(k\)-subsets (combinations) without repetition, i.e. once an item has been removed, it can no longer be “taken”:

>>> list(subsets([1, 2], 2))
[(1, 2)]
>>> list(subsets([1, 2]))
[(), (1,), (2,), (1, 2)]
>>> list(subsets([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]

subsets(seq, k, repetition=True) will return the \(\frac{(n - 1 + k)!}{k!(n - 1)!}\) combinations with repetition:

>>> list(subsets([1, 2], 2, repetition=True))
[(1, 1), (1, 2), (2, 2)]

If you ask for more items than are in the set you get the empty set unless you allow repetitions:

>>> list(subsets([0, 1], 3, repetition=False))
[]
>>> list(subsets([0, 1], 3, repetition=True))
[(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)]

sympy.utilities.iterables.take(iter, n)[source]: Return n items from iter iterator.

sympy.utilities.iterables.topological_sort(graph, key=None)[source]

Topological sort of graph’s vertices.

Parameters

graph : tuple[list, list[tuple[T, T]]

A tuple consisting of a list of vertices and a list of edges of a graph to be sorted topologically.

key : callable[T] (optional)

Ordering key for vertices on the same level. By default the natural (e.g. lexicographic) ordering is used (in this case the base type must implement ordering relations).

Examples

Consider a graph:

+---+     +---+     +---+
| 7 |\    | 5 |     | 3 |
+---+ \   +---+     +---+
  |   _\___/ ____   _/ |
  |  /  \___/    \ /   |
  V  V           V V   |
 +----+         +---+  |
 | 11 |         | 8 |  |
 +----+         +---+  |
  | | \____   ___/ _   |
  | \      \ /    / \  |
  V  \     V V   /  V  V
+---+ \   +---+ |  +----+
| 2 |  |  | 9 | |  | 10 |
+---+  |  +---+ |  +----+
       \________/

where vertices are integers. This graph can be encoded using elementary Python’s data structures as follows:

>>> V = [2, 3, 5, 7, 8, 9, 10, 11]
>>> E = [(7, 11), (7, 8), (5, 11), (3, 8), (3, 10),
...      (11, 2), (11, 9), (11, 10), (8, 9)]

To compute a topological sort for graph (V, E) issue:

>>> from sympy.utilities.iterables import topological_sort

>>> topological_sort((V, E))
[3, 5, 7, 8, 11, 2, 9, 10]

If specific tie breaking approach is needed, use key parameter:

>>> topological_sort((V, E), key=lambda v: -v)
[7, 5, 11, 3, 10, 8, 9, 2]

Only acyclic graphs can be sorted. If the input graph has a cycle, then ValueError will be raised:

>>> topological_sort((V, E + [(10, 7)]))
Traceback (most recent call last):
...
ValueError: cycle detected

References

R971: https://en.wikipedia.org/wiki/Topological_sorting

sympy.utilities.iterables.unflatten(iter, n=2)[source]: Group iter into tuples of length n. Raise an error if the length of iter is not a multiple of n.

sympy.utilities.iterables.uniq(seq, result=None)[source]

Yield unique elements from seq as an iterator. The second parameter result is used internally; it is not necessary to pass anything for this.

Note: changing the sequence during iteration will raise a RuntimeError if the size of the sequence is known; if you pass an iterator and advance the iterator you will change the output of this routine but there will be no warning.

Examples

>>> from sympy.utilities.iterables import uniq
>>> dat = [1, 4, 1, 5, 4, 2, 1, 2]
>>> type(uniq(dat)) in (list, tuple)
False

>>> list(uniq(dat))
[1, 4, 5, 2]
>>> list(uniq(x for x in dat))
[1, 4, 5, 2]
>>> list(uniq([[1], [2, 1], [1]]))
[[1], [2, 1]]

sympy.utilities.iterables.variations(seq, n, repetition=False)[source]

Returns a generator of the n-sized variations of seq (size N). repetition controls whether items in seq can appear more than once;

Examples

variations(seq, n) will return \(\frac{N!}{(N - n)!}\) permutations without repetition of seq’s elements:

>>> from sympy.utilities.iterables import variations
>>> list(variations([1, 2], 2))
[(1, 2), (2, 1)]

variations(seq, n, True) will return the \(N^n\) permutations obtained by allowing repetition of elements:

>>> list(variations([1, 2], 2, repetition=True))
[(1, 1), (1, 2), (2, 1), (2, 2)]

If you ask for more items than are in the set you get the empty set unless you allow repetitions:

>>> list(variations([0, 1], 3, repetition=False))
[]
>>> list(variations([0, 1], 3, repetition=True))[:4]
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1)]