# Iterables¶

## cartes¶

Returns the cartesian product of sequences as a generator.

Examples::
>>> from sympy.utilities.iterables import cartes
>>> list(cartes([1,2,3], 'ab'))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]


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


### Docstring¶

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.

Reference: TAOCP 4, section 7.2.1.5, problem 64

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]

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.dict_merge(*dicts)[source]

Merge dictionaries into a single dictionary.

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
>>> class MyOp(Basic):
...     pass
...
>>> flatten([MyOp(1, MyOp(2, 3))], cls=MyOp)
[1, 2, 3]

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

Generates the bell permutations.

In a Bell permutation, each cycle is a decreasing sequence of integers.

Reference: [1] Generating involutions, derangements, and relatives by ECO Vincent Vajnovszki, DMTCS vol 1 issue 12, 2010

Examples

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

sympy.utilities.iterables.generate_derangements(perm)[source]

Routine to generate derangements.

TODO: This will be rewritten to use the ECO operator approach once the permutations branch is in master.

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,3]))
[[1, 0, 3, 2], [1, 2, 3, 0], [1, 3, 0, 2], [2, 0, 3, 1],     [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 2, 0, 1],     [3, 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
>>> generate_involutions(3)
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 1, 0)]
>>> len(generate_involutions(4))
10

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.

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

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

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

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

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

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(list(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
>>> from sympy import Dict, Set

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

sympy.utilities.iterables.interactive_traversal(expr)[source]

Traverse a tree asking a user which branch to choose.

sympy.utilities.iterables.lazyDSU_sort(seq, keys, warn=False)[source]

Return sorted seq, breaking ties by applying keys only when needed.

If warn is True then an error will be raised if there were no keys remaining to break ties.

Notes

The decorated sort is one of the fastest ways to sort a sequence for which special item comparison is desired: the sequence is decorated, sorted on the basis of the decoration (e.g. making all letters lower case) and then undecorated. If one wants to break ties for items that have the same decorated value, a second key can be used. But if the second key is expensive to compute then it is inefficient to decorate all items with both keys: only those items having identical first key values need to be decorated. This function applies keys successively only when needed to break ties.

Examples

>>> from sympy.utilities.iterables import lazyDSU_sort, default_sort_key
>>> from sympy.abc import x, y


The count_ops is not sufficient to break ties in this list and the first two items appear in their original order: Python sorting is stable.

>>> lazyDSU_sort([y + 2, x + 2, x**2 + y + 3],
...    [lambda x: x.count_ops()], warn=False)
...
[y + 2, x + 2, x**2 + y + 3]


The use of default_sort_key allows the tie to be broken (and warn can be safely left False).

>>> lazyDSU_sort([y + 2, x + 2, x**2 + y + 3],
...    [lambda x: x.count_ops(),
...     default_sort_key])
...
[x + 2, y + 2, x**2 + y + 3]


Here, sequences are sorted by length, then sum:

>>> seq, keys = [[[1, 2, 1], [0, 3, 1], [1, 1, 3], [2], [1]], [
...    lambda x: len(x),
...    lambda x: sum(x)]]
...
>>> lazyDSU_sort(seq, keys, warn=False)
[[1], [2], [1, 2, 1], [0, 3, 1], [1, 1, 3]]


If warn is True, an error will be raised if there were not enough keys to break ties:

>>> lazyDSU_sort(seq, keys, warn=True)
Traceback (most recent call last):
...
ValueError: not enough keys to break ties

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

Return a tuple where the smallest element appears first; if directed is True (default) then the order is preserved, otherwise the sequence will be reversed if that gives a lexically smaller ordering.

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)

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

This is the algorithm for generating multiset partitions as described by Knuth in TAOCP Vol 4.

Given a multiset, this algorithm visits all of its m-partitions, that is, all partitions having exactly size m using auxiliary arrays as described in the book.

Examples

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

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

Generate an infinite stream of Symbols consisting of a prefix and increasing subscripts.

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. start : int, optional The start number. By default, it is 0. sym : Symbol The subscripted symbols.
sympy.utilities.iterables.partitions(n, m=None, k=None)[source]

Generate all partitions of integer n (>= 0).

‘m’ limits the number of parts in the partition, e.g. if m=2 then
partitions will contain no more than 2 numbers, while
‘k’ limits the numbers which may appear in the partition, e.g. k=2 will
return partitions with no element greater than 2.

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}: a single 4.

>>> from sympy.utilities.iterables import partitions


Maximum key (number in partition) limited with k (in this case, 2):

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


Maximum number of parts in partion limited with m (in this case, 2):

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


Note that the _same_ dictionary object is returned each time. This is for speed: generating each partition goes quickly, taking constant time independent of n.

>>> [p for p in partitions(6, k=2)]
[{1: 6}, {1: 6}, {1: 6}, {1: 6}]


If you want to build a list of the returned dictionaries then make a copy of them:

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

Reference:
modified from Tim Peter’s version to allow for k and m values: code.activestate.com/recipes/218332-generator-for-integer-partitions/
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.postorder_traversal(node, key=None)[source]

Do a postorder traversal of a tree.

This generator recursively yields nodes that it has visited in a postorder fashion. That is, it descends through the tree depth-first to yield all of a node’s children’s postorder traversal before yielding the node itself.

Parameters : node : sympy expression The expression to traverse. key : (default None) sort key The key used to sort args of Basic objects. When None, args of Basic objects are processed in arbitrary order. subtree : sympy expression All of the subtrees in the tree.

Examples

>>> from sympy import symbols, default_sort_key
>>> from sympy.utilities.iterables import postorder_traversal
>>> from sympy.abc import w, x, y, z


The nodes are returned in the order that they are encountered unless key is given.

>>> list(postorder_traversal(w + (x + y)*z))
[z, y, x, x + y, z*(x + y), w, w + z*(x + y)]
>>> list(postorder_traversal(w + (x + y)*z, key=default_sort_key))
[w, z, x, y, x + y, z*(x + y), w + z*(x + y)]

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

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]

Left 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.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(expr, keyfunc)[source]

Sift the arguments of expr into a dictionary according to keyfunc.

INPUT: expr may be an expression or iterable; if it is an expr then it is converted to a list of expr’s args or [expr] if there are no args.

OUTPUT: each element in expr is stored in a list keyed to the value of keyfunc for the element.

Note that for a SymPy expression, the order of the elements in the lists is dependent on the order in .args, which can be arbitrary.

lazyDSU_sort

Examples

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

>>> sift(list(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 won’t 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)]}


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

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

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

Remove repeated elements from an iterable, preserving order of first appearance.

Returns a sequence of the same type of the input, or a list if the input was not a sequence.

Examples

>>> from sympy.utilities.iterables import uniq
>>> uniq([1,4,1,5,4,2,1,2])
[1, 4, 5, 2]
>>> uniq((1,4,1,5,4,2,1,2))
(1, 4, 5, 2)
>>> uniq(x for x in (1,4,1,5,4,2,1,2))
[1, 4, 5, 2]

sympy.utilities.iterables.unrestricted_necklace(n, k)[source]

A routine to generate unrestriced necklaces.

Here n is the length of the necklace and k - 1 is the maximum permissible element in the generated necklaces.

Examples

>>> from sympy.utilities.iterables import unrestricted_necklace
>>> [i[:] for i in unrestricted_necklace(3, 2)]
[[0, 0, 0], [0, 1, 1]]
>>> [i[:] for i in unrestricted_necklace(4, 4)]
[[0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 2, 0], [0, 0, 3, 0],     [0, 1, 1, 1], [0, 1, 2, 1], [0, 1, 3, 1], [0, 2, 2, 2],     [0, 2, 3, 2], [0, 3, 3, 3]]

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;

sympy.core.compatibility.permutations

Examples

variations(seq, n) will return 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)]