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 diofant.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 partitions.

partitions:

>>> from diofant.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 diofant.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 diofant.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

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

References

  • TAOCP 4, section 7.2.1.5, problem 64

Examples

>>> for i in binary_partitions(5):
...     print(i)
...
[4, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]
diofant.utilities.iterables.bracelets(n, k)[source]

Wrapper to necklaces to return a free (unrestricted) necklace.

diofant.utilities.iterables.cantor_product(*args)[source]

Breadth-first (diagonal) cartesian product of iterables.

Each iterable is advanced in turn in a round-robin fashion. As usual with breadth-first, this comes at the cost of memory consumption.

>>> from itertools import islice, count
>>> list(islice(cantor_product(count(), count()), 9))
[(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
diofant.utilities.iterables.capture(func)[source]

Return the printed output of func().

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

>>> def foo():
...     print('hello world!')
...
>>> 'hello' in capture(foo) # foo, not foo()
True
>>> capture(lambda: pprint(2/x, use_unicode=False))
'2\n-\nx\n'
diofant.utilities.iterables.common_prefix(*seqs)[source]

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

>>> 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]
diofant.utilities.iterables.common_suffix(*seqs)[source]

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

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

Merge dictionaries into a single dictionary.

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

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

Recursively denest iterable containers.

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

>>> class MyOp(Basic):
...     pass
...
>>> flatten([MyOp(1, MyOp(2, 3))], cls=MyOp)
[1, 2, 3]

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

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

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

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

Routine to generate unique derangements.

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

Examples

>>> 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]))
[]
diofant.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.

References

Examples

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

References

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

Examples

>>> 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]]
diofant.utilities.iterables.group(seq, multiple=True)[source]

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

Examples

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

diofant.utilities.iterables.has_dups(seq)[source]

Return True if there are any duplicate elements in seq.

Examples

>>> 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
diofant.utilities.iterables.has_variety(seq)[source]

Return True if there are any different elements in seq.

Examples

>>> has_variety((1, 2, 1))
True
>>> has_variety((1, 1, 1))
False
diofant.utilities.iterables.ibin(n, bits=0, 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

>>> ibin(2)
[1, 0]
>>> ibin(2, 4)
[0, 0, 1, 0]
>>> ibin(2, 4)[::-1]
[0, 1, 0, 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']
diofant.utilities.iterables.kbins(l, k, ordered=None)[source]

Return sequence l partitioned into k bins.

Examples

The default is to give the items in the same order, but grouped into k partitions without any reordering:

>>> for p in kbins(list(range(5)), 2):
...     print(p)
...
[[0], [1, 2, 3, 4]]
[[0, 1], [2, 3, 4]]
[[0, 1, 2], [3, 4]]
[[0, 1, 2, 3], [4]]

The ordered flag which is either None (to give the simple partition of the the elements) or is a 2 digit integer indicating whether the order of the bins and the order of the items in the bins matters. Given:

A = [[0], [1, 2]]
B = [[1, 2], [0]]
C = [[2, 1], [0]]
D = [[0], [2, 1]]

the following values for ordered have the shown meanings:

00 means A == B == C == D
01 means A == B
10 means A == D
11 means A == A
>>> for ordered in [None, 0, 1, 10, 11]:
...     print('ordered = %s' % ordered)
...     for p in kbins(list(range(3)), 2, ordered=ordered):
...         print('     %s' % p)
...
ordered = None
     [[0], [1, 2]]
     [[0, 1], [2]]
ordered = 0
     [[0, 1], [2]]
     [[0, 2], [1]]
     [[0], [1, 2]]
ordered = 1
     [[0], [1, 2]]
     [[0], [2, 1]]
     [[1], [0, 2]]
     [[1], [2, 0]]
     [[2], [0, 1]]
     [[2], [1, 0]]
ordered = 10
     [[0, 1], [2]]
     [[2], [0, 1]]
     [[0, 2], [1]]
     [[1], [0, 2]]
     [[0], [1, 2]]
     [[1, 2], [0]]
ordered = 11
     [[0], [1, 2]]
     [[0, 1], [2]]
     [[0], [2, 1]]
     [[0, 2], [1]]
     [[1], [0, 2]]
     [[1, 0], [2]]
     [[1], [2, 0]]
     [[1, 2], [0]]
     [[2], [0, 1]]
     [[2, 0], [1]]
     [[2], [1, 0]]
     [[2, 1], [0]]
diofant.utilities.iterables.minlex(seq, directed=True, is_set=False, small=None)[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 smaller ordering.

If every element appears only once then is_set can be set to True for more efficient processing.

If the smallest element is known at the time of calling, it can be passed and the calculation of the smallest element will be omitted.

Examples

>>> 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'
diofant.utilities.iterables.multiset(seq)[source]

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

Examples

>>> multiset('mississippi')
{'i': 4, 'm': 1, 'p': 2, 's': 4}

See also

group()

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

Return the unique combinations of size n from multiset m.

Examples

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

Counting

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

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

>>> def S2(n, k):
...     from diofant import Dummy, binomial, factorial, Sum
...     if k > n:
...         return 0
...     j = Dummy()
...     arg = (-1)**(k-j)*j**n*binomial(k,j)
...     return 1/factorial(k)*Sum(arg,(j,0,k)).doit()
...
>>> S2(5, 2) == len(list(multiset_partitions(5, 2))) == 15
True

These comments on counting apply to sets, not multisets.

Examples

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

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.

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

Return the unique permutations of multiset m.

Examples

>>> [''.join(i) for i in multiset_permutations('aab')]
['aab', 'aba', 'baa']
>>> factorial(len('banana'))
720
>>> len(list(multiset_permutations('banana')))
60
diofant.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

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

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

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

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

Generates ordered partitions of integer n.

Parameters:
  • ``m`` (int or None, optional) – By default (None) 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, optional) – Controls whether partitions are returned in sorted order (default) 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

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

diofant.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). Default value, None, gives partitions from 1 through n.
  • ``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

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

>>> from diofant.utilities.iterables import partitions
>>> for p in partitions(6, k=2):  # doctest: +SKIP
...     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:

>>> for p in partitions(6, m=2):  # doctest: +SKIP
...     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)]  # doctest: +SKIP
[{2: 3}, {1: 2, 2: 2}, {1: 4, 2: 1}, {1: 6}]
>>> [(M, p.copy()) for M, p in partitions(6, k=2, size=True)]  # doctest: +SKIP
[(3, {2: 3}), (4, {1: 2, 2: 2}), (5, {1: 4, 2: 1}), (6, {1: 6})]

References

Notes

Modified from Tim Peter’s version to allow for k and m values.

diofant.utilities.iterables.permute_signs(t)[source]

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

Examples

>>> list(permute_signs((0, 1, 2)))
[(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2)]
diofant.utilities.iterables.postfixes(seq)[source]

Generate all postfixes of a sequence.

Examples

>>> list(postfixes([1,2,3,4]))
[[4], [3, 4], [2, 3, 4], [1, 2, 3, 4]]
diofant.utilities.iterables.postorder_traversal(node, keys=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 (diofant expression) – The expression to traverse.
  • keys ((default None) sort key(s)) – The key(s) used to sort args of Basic objects. When None, args of Basic objects are processed in arbitrary order. If key is defined, it will be passed along to ordered() as the only key(s) to use to sort the arguments; if key is simply True then the default keys of ordered will be used (node count and default_sort_key).
Yields:

subtree (diofant expression) – All of the subtrees in the tree.

Examples

>>> from diofant.abc import w

The nodes are returned in the order that they are encountered unless key is given; simply passing key=True will guarantee that the traversal is unique.

>>> list(postorder_traversal(w + (x + y)*z, keys=True))
[w, z, x, y, x + y, z*(x + y), w + z*(x + y)]
diofant.utilities.iterables.prefixes(seq)[source]

Generate all prefixes of a sequence.

Examples

>>> list(prefixes([1,2,3,4]))
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
diofant.utilities.iterables.reshape(seq, how)[source]

Reshape the sequence according to the template in how.

Examples

>>> 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)]]
diofant.utilities.iterables.rotate_left(x, y)[source]

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

Examples

>>> a = [0, 1, 2]
>>> rotate_left(a, 1)
[1, 2, 0]
diofant.utilities.iterables.rotate_right(x, y)[source]

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

Examples

>>> a = [0, 1, 2]
>>> rotate_right(a, 1)
[2, 0, 1]
diofant.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 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]]
diofant.utilities.iterables.sift(seq, keyfunc)[source]

Sift the sequence, seq into a dictionary according to keyfunc.

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

Examples

>>> from collections import defaultdict
>>> sift(range(5), lambda x: x % 2) == defaultdict(int, {0: [0, 2, 4], 1: [1, 3]})
True

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

>>> dl = sift([x], lambda x: x.is_commutative)
>>> dl == defaultdict(list, {True: [x]})
True
>>> dl[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]) == defaultdict(list,
...      {E: [exp(x)], x: [sqrt(x)], y: [y**(2*x)]})
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 squence while sorting.

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

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

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

>>> from diofant.utilities.iterables import subsets
>>> 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)]
diofant.utilities.iterables.take(iter, n)[source]

Return n items from iter iterator.

diofant.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:

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

  • https//en.wikipedia.org/wiki/Topological_sorting
diofant.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.

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

Examples

>>> 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]]
diofant.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 N! / (N - n)! permutations without repetition of seq’s elements:

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