Coverage for /usr/lib/python3/dist-packages/sympy/utilities/iterables.py: 18%
1007 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1from collections import Counter, defaultdict, OrderedDict
2from itertools import (
3 chain, combinations, combinations_with_replacement, cycle, islice,
4 permutations, product, groupby
5)
6# For backwards compatibility
7from itertools import product as cartes # noqa: F401
8from operator import gt
12# this is the logical location of these functions
13from sympy.utilities.enumerative import (
14 multiset_partitions_taocp, list_visitor, MultisetPartitionTraverser)
16from sympy.utilities.misc import as_int
17from sympy.utilities.decorator import deprecated
20def is_palindromic(s, i=0, j=None):
21 """
22 Return True if the sequence is the same from left to right as it
23 is from right to left in the whole sequence (default) or in the
24 Python slice ``s[i: j]``; else False.
26 Examples
27 ========
29 >>> from sympy.utilities.iterables import is_palindromic
30 >>> is_palindromic([1, 0, 1])
31 True
32 >>> is_palindromic('abcbb')
33 False
34 >>> is_palindromic('abcbb', 1)
35 False
37 Normal Python slicing is performed in place so there is no need to
38 create a slice of the sequence for testing:
40 >>> is_palindromic('abcbb', 1, -1)
41 True
42 >>> is_palindromic('abcbb', -4, -1)
43 True
45 See Also
46 ========
48 sympy.ntheory.digits.is_palindromic: tests integers
50 """
51 i, j, _ = slice(i, j).indices(len(s))
52 m = (j - i)//2
53 # if length is odd, middle element will be ignored
54 return all(s[i + k] == s[j - 1 - k] for k in range(m))
57def flatten(iterable, levels=None, cls=None): # noqa: F811
58 """
59 Recursively denest iterable containers.
61 >>> from sympy import flatten
63 >>> flatten([1, 2, 3])
64 [1, 2, 3]
65 >>> flatten([1, 2, [3]])
66 [1, 2, 3]
67 >>> flatten([1, [2, 3], [4, 5]])
68 [1, 2, 3, 4, 5]
69 >>> flatten([1.0, 2, (1, None)])
70 [1.0, 2, 1, None]
72 If you want to denest only a specified number of levels of
73 nested containers, then set ``levels`` flag to the desired
74 number of levels::
76 >>> ls = [[(-2, -1), (1, 2)], [(0, 0)]]
78 >>> flatten(ls, levels=1)
79 [(-2, -1), (1, 2), (0, 0)]
81 If cls argument is specified, it will only flatten instances of that
82 class, for example:
84 >>> from sympy import Basic, S
85 >>> class MyOp(Basic):
86 ... pass
87 ...
88 >>> flatten([MyOp(S(1), MyOp(S(2), S(3)))], cls=MyOp)
89 [1, 2, 3]
91 adapted from https://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks
92 """
93 from sympy.tensor.array import NDimArray
94 if levels is not None:
95 if not levels:
96 return iterable
97 elif levels > 0:
98 levels -= 1
99 else:
100 raise ValueError(
101 "expected non-negative number of levels, got %s" % levels)
103 if cls is None:
104 def reducible(x):
105 return is_sequence(x, set)
106 else:
107 def reducible(x):
108 return isinstance(x, cls)
110 result = []
112 for el in iterable:
113 if reducible(el):
114 if hasattr(el, 'args') and not isinstance(el, NDimArray):
115 el = el.args
116 result.extend(flatten(el, levels=levels, cls=cls))
117 else:
118 result.append(el)
120 return result
123def unflatten(iter, n=2):
124 """Group ``iter`` into tuples of length ``n``. Raise an error if
125 the length of ``iter`` is not a multiple of ``n``.
126 """
127 if n < 1 or len(iter) % n:
128 raise ValueError('iter length is not a multiple of %i' % n)
129 return list(zip(*(iter[i::n] for i in range(n))))
132def reshape(seq, how):
133 """Reshape the sequence according to the template in ``how``.
135 Examples
136 ========
138 >>> from sympy.utilities import reshape
139 >>> seq = list(range(1, 9))
141 >>> reshape(seq, [4]) # lists of 4
142 [[1, 2, 3, 4], [5, 6, 7, 8]]
144 >>> reshape(seq, (4,)) # tuples of 4
145 [(1, 2, 3, 4), (5, 6, 7, 8)]
147 >>> reshape(seq, (2, 2)) # tuples of 4
148 [(1, 2, 3, 4), (5, 6, 7, 8)]
150 >>> reshape(seq, (2, [2])) # (i, i, [i, i])
151 [(1, 2, [3, 4]), (5, 6, [7, 8])]
153 >>> reshape(seq, ((2,), [2])) # etc....
154 [((1, 2), [3, 4]), ((5, 6), [7, 8])]
156 >>> reshape(seq, (1, [2], 1))
157 [(1, [2, 3], 4), (5, [6, 7], 8)]
159 >>> reshape(tuple(seq), ([[1], 1, (2,)],))
160 (([[1], 2, (3, 4)],), ([[5], 6, (7, 8)],))
162 >>> reshape(tuple(seq), ([1], 1, (2,)))
163 (([1], 2, (3, 4)), ([5], 6, (7, 8)))
165 >>> reshape(list(range(12)), [2, [3], {2}, (1, (3,), 1)])
166 [[0, 1, [2, 3, 4], {5, 6}, (7, (8, 9, 10), 11)]]
168 """
169 m = sum(flatten(how))
170 n, rem = divmod(len(seq), m)
171 if m < 0 or rem:
172 raise ValueError('template must sum to positive number '
173 'that divides the length of the sequence')
174 i = 0
175 container = type(how)
176 rv = [None]*n
177 for k in range(len(rv)):
178 _rv = []
179 for hi in how:
180 if isinstance(hi, int):
181 _rv.extend(seq[i: i + hi])
182 i += hi
183 else:
184 n = sum(flatten(hi))
185 hi_type = type(hi)
186 _rv.append(hi_type(reshape(seq[i: i + n], hi)[0]))
187 i += n
188 rv[k] = container(_rv)
189 return type(seq)(rv)
192def group(seq, multiple=True):
193 """
194 Splits a sequence into a list of lists of equal, adjacent elements.
196 Examples
197 ========
199 >>> from sympy import group
201 >>> group([1, 1, 1, 2, 2, 3])
202 [[1, 1, 1], [2, 2], [3]]
203 >>> group([1, 1, 1, 2, 2, 3], multiple=False)
204 [(1, 3), (2, 2), (3, 1)]
205 >>> group([1, 1, 3, 2, 2, 1], multiple=False)
206 [(1, 2), (3, 1), (2, 2), (1, 1)]
208 See Also
209 ========
211 multiset
213 """
214 if multiple:
215 return [(list(g)) for _, g in groupby(seq)]
216 return [(k, len(list(g))) for k, g in groupby(seq)]
219def _iproduct2(iterable1, iterable2):
220 '''Cartesian product of two possibly infinite iterables'''
222 it1 = iter(iterable1)
223 it2 = iter(iterable2)
225 elems1 = []
226 elems2 = []
228 sentinel = object()
229 def append(it, elems):
230 e = next(it, sentinel)
231 if e is not sentinel:
232 elems.append(e)
234 n = 0
235 append(it1, elems1)
236 append(it2, elems2)
238 while n <= len(elems1) + len(elems2):
239 for m in range(n-len(elems1)+1, len(elems2)):
240 yield (elems1[n-m], elems2[m])
241 n += 1
242 append(it1, elems1)
243 append(it2, elems2)
246def iproduct(*iterables):
247 '''
248 Cartesian product of iterables.
250 Generator of the Cartesian product of iterables. This is analogous to
251 itertools.product except that it works with infinite iterables and will
252 yield any item from the infinite product eventually.
254 Examples
255 ========
257 >>> from sympy.utilities.iterables import iproduct
258 >>> sorted(iproduct([1,2], [3,4]))
259 [(1, 3), (1, 4), (2, 3), (2, 4)]
261 With an infinite iterator:
263 >>> from sympy import S
264 >>> (3,) in iproduct(S.Integers)
265 True
266 >>> (3, 4) in iproduct(S.Integers, S.Integers)
267 True
269 .. seealso::
271 `itertools.product
272 <https://docs.python.org/3/library/itertools.html#itertools.product>`_
273 '''
274 if len(iterables) == 0:
275 yield ()
276 return
277 elif len(iterables) == 1:
278 for e in iterables[0]:
279 yield (e,)
280 elif len(iterables) == 2:
281 yield from _iproduct2(*iterables)
282 else:
283 first, others = iterables[0], iterables[1:]
284 for ef, eo in _iproduct2(first, iproduct(*others)):
285 yield (ef,) + eo
288def multiset(seq):
289 """Return the hashable sequence in multiset form with values being the
290 multiplicity of the item in the sequence.
292 Examples
293 ========
295 >>> from sympy.utilities.iterables import multiset
296 >>> multiset('mississippi')
297 {'i': 4, 'm': 1, 'p': 2, 's': 4}
299 See Also
300 ========
302 group
304 """
305 return dict(Counter(seq).items())
310def ibin(n, bits=None, str=False):
311 """Return a list of length ``bits`` corresponding to the binary value
312 of ``n`` with small bits to the right (last). If bits is omitted, the
313 length will be the number required to represent ``n``. If the bits are
314 desired in reversed order, use the ``[::-1]`` slice of the returned list.
316 If a sequence of all bits-length lists starting from ``[0, 0,..., 0]``
317 through ``[1, 1, ..., 1]`` are desired, pass a non-integer for bits, e.g.
318 ``'all'``.
320 If the bit *string* is desired pass ``str=True``.
322 Examples
323 ========
325 >>> from sympy.utilities.iterables import ibin
326 >>> ibin(2)
327 [1, 0]
328 >>> ibin(2, 4)
329 [0, 0, 1, 0]
331 If all lists corresponding to 0 to 2**n - 1, pass a non-integer
332 for bits:
334 >>> bits = 2
335 >>> for i in ibin(2, 'all'):
336 ... print(i)
337 (0, 0)
338 (0, 1)
339 (1, 0)
340 (1, 1)
342 If a bit string is desired of a given length, use str=True:
344 >>> n = 123
345 >>> bits = 10
346 >>> ibin(n, bits, str=True)
347 '0001111011'
348 >>> ibin(n, bits, str=True)[::-1] # small bits left
349 '1101111000'
350 >>> list(ibin(3, 'all', str=True))
351 ['000', '001', '010', '011', '100', '101', '110', '111']
353 """
354 if n < 0:
355 raise ValueError("negative numbers are not allowed")
356 n = as_int(n)
358 if bits is None:
359 bits = 0
360 else:
361 try:
362 bits = as_int(bits)
363 except ValueError:
364 bits = -1
365 else:
366 if n.bit_length() > bits:
367 raise ValueError(
368 "`bits` must be >= {}".format(n.bit_length()))
370 if not str:
371 if bits >= 0:
372 return [1 if i == "1" else 0 for i in bin(n)[2:].rjust(bits, "0")]
373 else:
374 return variations(range(2), n, repetition=True)
375 else:
376 if bits >= 0:
377 return bin(n)[2:].rjust(bits, "0")
378 else:
379 return (bin(i)[2:].rjust(n, "0") for i in range(2**n))
382def variations(seq, n, repetition=False):
383 r"""Returns an iterator over the n-sized variations of ``seq`` (size N).
384 ``repetition`` controls whether items in ``seq`` can appear more than once;
386 Examples
387 ========
389 ``variations(seq, n)`` will return `\frac{N!}{(N - n)!}` permutations without
390 repetition of ``seq``'s elements:
392 >>> from sympy import variations
393 >>> list(variations([1, 2], 2))
394 [(1, 2), (2, 1)]
396 ``variations(seq, n, True)`` will return the `N^n` permutations obtained
397 by allowing repetition of elements:
399 >>> list(variations([1, 2], 2, repetition=True))
400 [(1, 1), (1, 2), (2, 1), (2, 2)]
402 If you ask for more items than are in the set you get the empty set unless
403 you allow repetitions:
405 >>> list(variations([0, 1], 3, repetition=False))
406 []
407 >>> list(variations([0, 1], 3, repetition=True))[:4]
408 [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1)]
410 .. seealso::
412 `itertools.permutations
413 <https://docs.python.org/3/library/itertools.html#itertools.permutations>`_,
414 `itertools.product
415 <https://docs.python.org/3/library/itertools.html#itertools.product>`_
416 """
417 if not repetition:
418 seq = tuple(seq)
419 if len(seq) < n:
420 return iter(()) # 0 length iterator
421 return permutations(seq, n)
422 else:
423 if n == 0:
424 return iter(((),)) # yields 1 empty tuple
425 else:
426 return product(seq, repeat=n)
429def subsets(seq, k=None, repetition=False):
430 r"""Generates all `k`-subsets (combinations) from an `n`-element set, ``seq``.
432 A `k`-subset of an `n`-element set is any subset of length exactly `k`. The
433 number of `k`-subsets of an `n`-element set is given by ``binomial(n, k)``,
434 whereas there are `2^n` subsets all together. If `k` is ``None`` then all
435 `2^n` subsets will be returned from shortest to longest.
437 Examples
438 ========
440 >>> from sympy import subsets
442 ``subsets(seq, k)`` will return the
443 `\frac{n!}{k!(n - k)!}` `k`-subsets (combinations)
444 without repetition, i.e. once an item has been removed, it can no
445 longer be "taken":
447 >>> list(subsets([1, 2], 2))
448 [(1, 2)]
449 >>> list(subsets([1, 2]))
450 [(), (1,), (2,), (1, 2)]
451 >>> list(subsets([1, 2, 3], 2))
452 [(1, 2), (1, 3), (2, 3)]
455 ``subsets(seq, k, repetition=True)`` will return the
456 `\frac{(n - 1 + k)!}{k!(n - 1)!}`
457 combinations *with* repetition:
459 >>> list(subsets([1, 2], 2, repetition=True))
460 [(1, 1), (1, 2), (2, 2)]
462 If you ask for more items than are in the set you get the empty set unless
463 you allow repetitions:
465 >>> list(subsets([0, 1], 3, repetition=False))
466 []
467 >>> list(subsets([0, 1], 3, repetition=True))
468 [(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)]
470 """
471 if k is None:
472 if not repetition:
473 return chain.from_iterable((combinations(seq, k)
474 for k in range(len(seq) + 1)))
475 else:
476 return chain.from_iterable((combinations_with_replacement(seq, k)
477 for k in range(len(seq) + 1)))
478 else:
479 if not repetition:
480 return combinations(seq, k)
481 else:
482 return combinations_with_replacement(seq, k)
485def filter_symbols(iterator, exclude):
486 """
487 Only yield elements from `iterator` that do not occur in `exclude`.
489 Parameters
490 ==========
492 iterator : iterable
493 iterator to take elements from
495 exclude : iterable
496 elements to exclude
498 Returns
499 =======
501 iterator : iterator
502 filtered iterator
503 """
504 exclude = set(exclude)
505 for s in iterator:
506 if s not in exclude:
507 yield s
509def numbered_symbols(prefix='x', cls=None, start=0, exclude=(), *args, **assumptions):
510 """
511 Generate an infinite stream of Symbols consisting of a prefix and
512 increasing subscripts provided that they do not occur in ``exclude``.
514 Parameters
515 ==========
517 prefix : str, optional
518 The prefix to use. By default, this function will generate symbols of
519 the form "x0", "x1", etc.
521 cls : class, optional
522 The class to use. By default, it uses ``Symbol``, but you can also use ``Wild``
523 or ``Dummy``.
525 start : int, optional
526 The start number. By default, it is 0.
528 Returns
529 =======
531 sym : Symbol
532 The subscripted symbols.
533 """
534 exclude = set(exclude or [])
535 if cls is None:
536 # We can't just make the default cls=Symbol because it isn't
537 # imported yet.
538 from sympy.core import Symbol
539 cls = Symbol
541 while True:
542 name = '%s%s' % (prefix, start)
543 s = cls(name, *args, **assumptions)
544 if s not in exclude:
545 yield s
546 start += 1
549def capture(func):
550 """Return the printed output of func().
552 ``func`` should be a function without arguments that produces output with
553 print statements.
555 >>> from sympy.utilities.iterables import capture
556 >>> from sympy import pprint
557 >>> from sympy.abc import x
558 >>> def foo():
559 ... print('hello world!')
560 ...
561 >>> 'hello' in capture(foo) # foo, not foo()
562 True
563 >>> capture(lambda: pprint(2/x))
564 '2\\n-\\nx\\n'
566 """
567 from io import StringIO
568 import sys
570 stdout = sys.stdout
571 sys.stdout = file = StringIO()
572 try:
573 func()
574 finally:
575 sys.stdout = stdout
576 return file.getvalue()
579def sift(seq, keyfunc, binary=False):
580 """
581 Sift the sequence, ``seq`` according to ``keyfunc``.
583 Returns
584 =======
586 When ``binary`` is ``False`` (default), the output is a dictionary
587 where elements of ``seq`` are stored in a list keyed to the value
588 of keyfunc for that element. If ``binary`` is True then a tuple
589 with lists ``T`` and ``F`` are returned where ``T`` is a list
590 containing elements of seq for which ``keyfunc`` was ``True`` and
591 ``F`` containing those elements for which ``keyfunc`` was ``False``;
592 a ValueError is raised if the ``keyfunc`` is not binary.
594 Examples
595 ========
597 >>> from sympy.utilities import sift
598 >>> from sympy.abc import x, y
599 >>> from sympy import sqrt, exp, pi, Tuple
601 >>> sift(range(5), lambda x: x % 2)
602 {0: [0, 2, 4], 1: [1, 3]}
604 sift() returns a defaultdict() object, so any key that has no matches will
605 give [].
607 >>> sift([x], lambda x: x.is_commutative)
608 {True: [x]}
609 >>> _[False]
610 []
612 Sometimes you will not know how many keys you will get:
614 >>> sift([sqrt(x), exp(x), (y**x)**2],
615 ... lambda x: x.as_base_exp()[0])
616 {E: [exp(x)], x: [sqrt(x)], y: [y**(2*x)]}
618 Sometimes you expect the results to be binary; the
619 results can be unpacked by setting ``binary`` to True:
621 >>> sift(range(4), lambda x: x % 2, binary=True)
622 ([1, 3], [0, 2])
623 >>> sift(Tuple(1, pi), lambda x: x.is_rational, binary=True)
624 ([1], [pi])
626 A ValueError is raised if the predicate was not actually binary
627 (which is a good test for the logic where sifting is used and
628 binary results were expected):
630 >>> unknown = exp(1) - pi # the rationality of this is unknown
631 >>> args = Tuple(1, pi, unknown)
632 >>> sift(args, lambda x: x.is_rational, binary=True)
633 Traceback (most recent call last):
634 ...
635 ValueError: keyfunc gave non-binary output
637 The non-binary sifting shows that there were 3 keys generated:
639 >>> set(sift(args, lambda x: x.is_rational).keys())
640 {None, False, True}
642 If you need to sort the sifted items it might be better to use
643 ``ordered`` which can economically apply multiple sort keys
644 to a sequence while sorting.
646 See Also
647 ========
649 ordered
651 """
652 if not binary:
653 m = defaultdict(list)
654 for i in seq:
655 m[keyfunc(i)].append(i)
656 return m
657 sift = F, T = [], []
658 for i in seq:
659 try:
660 sift[keyfunc(i)].append(i)
661 except (IndexError, TypeError):
662 raise ValueError('keyfunc gave non-binary output')
663 return T, F
666def take(iter, n):
667 """Return ``n`` items from ``iter`` iterator. """
668 return [ value for _, value in zip(range(n), iter) ]
671def dict_merge(*dicts):
672 """Merge dictionaries into a single dictionary. """
673 merged = {}
675 for dict in dicts:
676 merged.update(dict)
678 return merged
681def common_prefix(*seqs):
682 """Return the subsequence that is a common start of sequences in ``seqs``.
684 >>> from sympy.utilities.iterables import common_prefix
685 >>> common_prefix(list(range(3)))
686 [0, 1, 2]
687 >>> common_prefix(list(range(3)), list(range(4)))
688 [0, 1, 2]
689 >>> common_prefix([1, 2, 3], [1, 2, 5])
690 [1, 2]
691 >>> common_prefix([1, 2, 3], [1, 3, 5])
692 [1]
693 """
694 if not all(seqs):
695 return []
696 elif len(seqs) == 1:
697 return seqs[0]
698 i = 0
699 for i in range(min(len(s) for s in seqs)):
700 if not all(seqs[j][i] == seqs[0][i] for j in range(len(seqs))):
701 break
702 else:
703 i += 1
704 return seqs[0][:i]
707def common_suffix(*seqs):
708 """Return the subsequence that is a common ending of sequences in ``seqs``.
710 >>> from sympy.utilities.iterables import common_suffix
711 >>> common_suffix(list(range(3)))
712 [0, 1, 2]
713 >>> common_suffix(list(range(3)), list(range(4)))
714 []
715 >>> common_suffix([1, 2, 3], [9, 2, 3])
716 [2, 3]
717 >>> common_suffix([1, 2, 3], [9, 7, 3])
718 [3]
719 """
721 if not all(seqs):
722 return []
723 elif len(seqs) == 1:
724 return seqs[0]
725 i = 0
726 for i in range(-1, -min(len(s) for s in seqs) - 1, -1):
727 if not all(seqs[j][i] == seqs[0][i] for j in range(len(seqs))):
728 break
729 else:
730 i -= 1
731 if i == -1:
732 return []
733 else:
734 return seqs[0][i + 1:]
737def prefixes(seq):
738 """
739 Generate all prefixes of a sequence.
741 Examples
742 ========
744 >>> from sympy.utilities.iterables import prefixes
746 >>> list(prefixes([1,2,3,4]))
747 [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
749 """
750 n = len(seq)
752 for i in range(n):
753 yield seq[:i + 1]
756def postfixes(seq):
757 """
758 Generate all postfixes of a sequence.
760 Examples
761 ========
763 >>> from sympy.utilities.iterables import postfixes
765 >>> list(postfixes([1,2,3,4]))
766 [[4], [3, 4], [2, 3, 4], [1, 2, 3, 4]]
768 """
769 n = len(seq)
771 for i in range(n):
772 yield seq[n - i - 1:]
775def topological_sort(graph, key=None):
776 r"""
777 Topological sort of graph's vertices.
779 Parameters
780 ==========
782 graph : tuple[list, list[tuple[T, T]]
783 A tuple consisting of a list of vertices and a list of edges of
784 a graph to be sorted topologically.
786 key : callable[T] (optional)
787 Ordering key for vertices on the same level. By default the natural
788 (e.g. lexicographic) ordering is used (in this case the base type
789 must implement ordering relations).
791 Examples
792 ========
794 Consider a graph::
796 +---+ +---+ +---+
797 | 7 |\ | 5 | | 3 |
798 +---+ \ +---+ +---+
799 | _\___/ ____ _/ |
800 | / \___/ \ / |
801 V V V V |
802 +----+ +---+ |
803 | 11 | | 8 | |
804 +----+ +---+ |
805 | | \____ ___/ _ |
806 | \ \ / / \ |
807 V \ V V / V V
808 +---+ \ +---+ | +----+
809 | 2 | | | 9 | | | 10 |
810 +---+ | +---+ | +----+
811 \________/
813 where vertices are integers. This graph can be encoded using
814 elementary Python's data structures as follows::
816 >>> V = [2, 3, 5, 7, 8, 9, 10, 11]
817 >>> E = [(7, 11), (7, 8), (5, 11), (3, 8), (3, 10),
818 ... (11, 2), (11, 9), (11, 10), (8, 9)]
820 To compute a topological sort for graph ``(V, E)`` issue::
822 >>> from sympy.utilities.iterables import topological_sort
824 >>> topological_sort((V, E))
825 [3, 5, 7, 8, 11, 2, 9, 10]
827 If specific tie breaking approach is needed, use ``key`` parameter::
829 >>> topological_sort((V, E), key=lambda v: -v)
830 [7, 5, 11, 3, 10, 8, 9, 2]
832 Only acyclic graphs can be sorted. If the input graph has a cycle,
833 then ``ValueError`` will be raised::
835 >>> topological_sort((V, E + [(10, 7)]))
836 Traceback (most recent call last):
837 ...
838 ValueError: cycle detected
840 References
841 ==========
843 .. [1] https://en.wikipedia.org/wiki/Topological_sorting
845 """
846 V, E = graph
848 L = []
849 S = set(V)
850 E = list(E)
852 for v, u in E:
853 S.discard(u)
855 if key is None:
856 def key(value):
857 return value
859 S = sorted(S, key=key, reverse=True)
861 while S:
862 node = S.pop()
863 L.append(node)
865 for u, v in list(E):
866 if u == node:
867 E.remove((u, v))
869 for _u, _v in E:
870 if v == _v:
871 break
872 else:
873 kv = key(v)
875 for i, s in enumerate(S):
876 ks = key(s)
878 if kv > ks:
879 S.insert(i, v)
880 break
881 else:
882 S.append(v)
884 if E:
885 raise ValueError("cycle detected")
886 else:
887 return L
890def strongly_connected_components(G):
891 r"""
892 Strongly connected components of a directed graph in reverse topological
893 order.
896 Parameters
897 ==========
899 graph : tuple[list, list[tuple[T, T]]
900 A tuple consisting of a list of vertices and a list of edges of
901 a graph whose strongly connected components are to be found.
904 Examples
905 ========
907 Consider a directed graph (in dot notation)::
909 digraph {
910 A -> B
911 A -> C
912 B -> C
913 C -> B
914 B -> D
915 }
917 .. graphviz::
919 digraph {
920 A -> B
921 A -> C
922 B -> C
923 C -> B
924 B -> D
925 }
927 where vertices are the letters A, B, C and D. This graph can be encoded
928 using Python's elementary data structures as follows::
930 >>> V = ['A', 'B', 'C', 'D']
931 >>> E = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'B'), ('B', 'D')]
933 The strongly connected components of this graph can be computed as
935 >>> from sympy.utilities.iterables import strongly_connected_components
937 >>> strongly_connected_components((V, E))
938 [['D'], ['B', 'C'], ['A']]
940 This also gives the components in reverse topological order.
942 Since the subgraph containing B and C has a cycle they must be together in
943 a strongly connected component. A and D are connected to the rest of the
944 graph but not in a cyclic manner so they appear as their own strongly
945 connected components.
948 Notes
949 =====
951 The vertices of the graph must be hashable for the data structures used.
952 If the vertices are unhashable replace them with integer indices.
954 This function uses Tarjan's algorithm to compute the strongly connected
955 components in `O(|V|+|E|)` (linear) time.
958 References
959 ==========
961 .. [1] https://en.wikipedia.org/wiki/Strongly_connected_component
962 .. [2] https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
965 See Also
966 ========
968 sympy.utilities.iterables.connected_components
970 """
971 # Map from a vertex to its neighbours
972 V, E = G
973 Gmap = {vi: [] for vi in V}
974 for v1, v2 in E:
975 Gmap[v1].append(v2)
976 return _strongly_connected_components(V, Gmap)
979def _strongly_connected_components(V, Gmap):
980 """More efficient internal routine for strongly_connected_components"""
981 #
982 # Here V is an iterable of vertices and Gmap is a dict mapping each vertex
983 # to a list of neighbours e.g.:
984 #
985 # V = [0, 1, 2, 3]
986 # Gmap = {0: [2, 3], 1: [0]}
987 #
988 # For a large graph these data structures can often be created more
989 # efficiently then those expected by strongly_connected_components() which
990 # in this case would be
991 #
992 # V = [0, 1, 2, 3]
993 # Gmap = [(0, 2), (0, 3), (1, 0)]
994 #
995 # XXX: Maybe this should be the recommended function to use instead...
996 #
998 # Non-recursive Tarjan's algorithm:
999 lowlink = {}
1000 indices = {}
1001 stack = OrderedDict()
1002 callstack = []
1003 components = []
1004 nomore = object()
1006 def start(v):
1007 index = len(stack)
1008 indices[v] = lowlink[v] = index
1009 stack[v] = None
1010 callstack.append((v, iter(Gmap[v])))
1012 def finish(v1):
1013 # Finished a component?
1014 if lowlink[v1] == indices[v1]:
1015 component = [stack.popitem()[0]]
1016 while component[-1] is not v1:
1017 component.append(stack.popitem()[0])
1018 components.append(component[::-1])
1019 v2, _ = callstack.pop()
1020 if callstack:
1021 v1, _ = callstack[-1]
1022 lowlink[v1] = min(lowlink[v1], lowlink[v2])
1024 for v in V:
1025 if v in indices:
1026 continue
1027 start(v)
1028 while callstack:
1029 v1, it1 = callstack[-1]
1030 v2 = next(it1, nomore)
1031 # Finished children of v1?
1032 if v2 is nomore:
1033 finish(v1)
1034 # Recurse on v2
1035 elif v2 not in indices:
1036 start(v2)
1037 elif v2 in stack:
1038 lowlink[v1] = min(lowlink[v1], indices[v2])
1040 # Reverse topological sort order:
1041 return components
1044def connected_components(G):
1045 r"""
1046 Connected components of an undirected graph or weakly connected components
1047 of a directed graph.
1050 Parameters
1051 ==========
1053 graph : tuple[list, list[tuple[T, T]]
1054 A tuple consisting of a list of vertices and a list of edges of
1055 a graph whose connected components are to be found.
1058 Examples
1059 ========
1062 Given an undirected graph::
1064 graph {
1065 A -- B
1066 C -- D
1067 }
1069 .. graphviz::
1071 graph {
1072 A -- B
1073 C -- D
1074 }
1076 We can find the connected components using this function if we include
1077 each edge in both directions::
1079 >>> from sympy.utilities.iterables import connected_components
1081 >>> V = ['A', 'B', 'C', 'D']
1082 >>> E = [('A', 'B'), ('B', 'A'), ('C', 'D'), ('D', 'C')]
1083 >>> connected_components((V, E))
1084 [['A', 'B'], ['C', 'D']]
1086 The weakly connected components of a directed graph can found the same
1087 way.
1090 Notes
1091 =====
1093 The vertices of the graph must be hashable for the data structures used.
1094 If the vertices are unhashable replace them with integer indices.
1096 This function uses Tarjan's algorithm to compute the connected components
1097 in `O(|V|+|E|)` (linear) time.
1100 References
1101 ==========
1103 .. [1] https://en.wikipedia.org/wiki/Component_%28graph_theory%29
1104 .. [2] https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
1107 See Also
1108 ========
1110 sympy.utilities.iterables.strongly_connected_components
1112 """
1113 # Duplicate edges both ways so that the graph is effectively undirected
1114 # and return the strongly connected components:
1115 V, E = G
1116 E_undirected = []
1117 for v1, v2 in E:
1118 E_undirected.extend([(v1, v2), (v2, v1)])
1119 return strongly_connected_components((V, E_undirected))
1122def rotate_left(x, y):
1123 """
1124 Left rotates a list x by the number of steps specified
1125 in y.
1127 Examples
1128 ========
1130 >>> from sympy.utilities.iterables import rotate_left
1131 >>> a = [0, 1, 2]
1132 >>> rotate_left(a, 1)
1133 [1, 2, 0]
1134 """
1135 if len(x) == 0:
1136 return []
1137 y = y % len(x)
1138 return x[y:] + x[:y]
1141def rotate_right(x, y):
1142 """
1143 Right rotates a list x by the number of steps specified
1144 in y.
1146 Examples
1147 ========
1149 >>> from sympy.utilities.iterables import rotate_right
1150 >>> a = [0, 1, 2]
1151 >>> rotate_right(a, 1)
1152 [2, 0, 1]
1153 """
1154 if len(x) == 0:
1155 return []
1156 y = len(x) - y % len(x)
1157 return x[y:] + x[:y]
1160def least_rotation(x, key=None):
1161 '''
1162 Returns the number of steps of left rotation required to
1163 obtain lexicographically minimal string/list/tuple, etc.
1165 Examples
1166 ========
1168 >>> from sympy.utilities.iterables import least_rotation, rotate_left
1169 >>> a = [3, 1, 5, 1, 2]
1170 >>> least_rotation(a)
1171 3
1172 >>> rotate_left(a, _)
1173 [1, 2, 3, 1, 5]
1175 References
1176 ==========
1178 .. [1] https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
1180 '''
1181 from sympy.functions.elementary.miscellaneous import Id
1182 if key is None: key = Id
1183 S = x + x # Concatenate string to it self to avoid modular arithmetic
1184 f = [-1] * len(S) # Failure function
1185 k = 0 # Least rotation of string found so far
1186 for j in range(1,len(S)):
1187 sj = S[j]
1188 i = f[j-k-1]
1189 while i != -1 and sj != S[k+i+1]:
1190 if key(sj) < key(S[k+i+1]):
1191 k = j-i-1
1192 i = f[i]
1193 if sj != S[k+i+1]:
1194 if key(sj) < key(S[k]):
1195 k = j
1196 f[j-k] = -1
1197 else:
1198 f[j-k] = i+1
1199 return k
1202def multiset_combinations(m, n, g=None):
1203 """
1204 Return the unique combinations of size ``n`` from multiset ``m``.
1206 Examples
1207 ========
1209 >>> from sympy.utilities.iterables import multiset_combinations
1210 >>> from itertools import combinations
1211 >>> [''.join(i) for i in multiset_combinations('baby', 3)]
1212 ['abb', 'aby', 'bby']
1214 >>> def count(f, s): return len(list(f(s, 3)))
1216 The number of combinations depends on the number of letters; the
1217 number of unique combinations depends on how the letters are
1218 repeated.
1220 >>> s1 = 'abracadabra'
1221 >>> s2 = 'banana tree'
1222 >>> count(combinations, s1), count(multiset_combinations, s1)
1223 (165, 23)
1224 >>> count(combinations, s2), count(multiset_combinations, s2)
1225 (165, 54)
1227 """
1228 from sympy.core.sorting import ordered
1229 if g is None:
1230 if isinstance(m, dict):
1231 if any(as_int(v) < 0 for v in m.values()):
1232 raise ValueError('counts cannot be negative')
1233 N = sum(m.values())
1234 if n > N:
1235 return
1236 g = [[k, m[k]] for k in ordered(m)]
1237 else:
1238 m = list(m)
1239 N = len(m)
1240 if n > N:
1241 return
1242 try:
1243 m = multiset(m)
1244 g = [(k, m[k]) for k in ordered(m)]
1245 except TypeError:
1246 m = list(ordered(m))
1247 g = [list(i) for i in group(m, multiple=False)]
1248 del m
1249 else:
1250 # not checking counts since g is intended for internal use
1251 N = sum(v for k, v in g)
1252 if n > N or not n:
1253 yield []
1254 else:
1255 for i, (k, v) in enumerate(g):
1256 if v >= n:
1257 yield [k]*n
1258 v = n - 1
1259 for v in range(min(n, v), 0, -1):
1260 for j in multiset_combinations(None, n - v, g[i + 1:]):
1261 rv = [k]*v + j
1262 if len(rv) == n:
1263 yield rv
1265def multiset_permutations(m, size=None, g=None):
1266 """
1267 Return the unique permutations of multiset ``m``.
1269 Examples
1270 ========
1272 >>> from sympy.utilities.iterables import multiset_permutations
1273 >>> from sympy import factorial
1274 >>> [''.join(i) for i in multiset_permutations('aab')]
1275 ['aab', 'aba', 'baa']
1276 >>> factorial(len('banana'))
1277 720
1278 >>> len(list(multiset_permutations('banana')))
1279 60
1280 """
1281 from sympy.core.sorting import ordered
1282 if g is None:
1283 if isinstance(m, dict):
1284 if any(as_int(v) < 0 for v in m.values()):
1285 raise ValueError('counts cannot be negative')
1286 g = [[k, m[k]] for k in ordered(m)]
1287 else:
1288 m = list(ordered(m))
1289 g = [list(i) for i in group(m, multiple=False)]
1290 del m
1291 do = [gi for gi in g if gi[1] > 0]
1292 SUM = sum([gi[1] for gi in do])
1293 if not do or size is not None and (size > SUM or size < 1):
1294 if not do and size is None or size == 0:
1295 yield []
1296 return
1297 elif size == 1:
1298 for k, v in do:
1299 yield [k]
1300 elif len(do) == 1:
1301 k, v = do[0]
1302 v = v if size is None else (size if size <= v else 0)
1303 yield [k for i in range(v)]
1304 elif all(v == 1 for k, v in do):
1305 for p in permutations([k for k, v in do], size):
1306 yield list(p)
1307 else:
1308 size = size if size is not None else SUM
1309 for i, (k, v) in enumerate(do):
1310 do[i][1] -= 1
1311 for j in multiset_permutations(None, size - 1, do):
1312 if j:
1313 yield [k] + j
1314 do[i][1] += 1
1317def _partition(seq, vector, m=None):
1318 """
1319 Return the partition of seq as specified by the partition vector.
1321 Examples
1322 ========
1324 >>> from sympy.utilities.iterables import _partition
1325 >>> _partition('abcde', [1, 0, 1, 2, 0])
1326 [['b', 'e'], ['a', 'c'], ['d']]
1328 Specifying the number of bins in the partition is optional:
1330 >>> _partition('abcde', [1, 0, 1, 2, 0], 3)
1331 [['b', 'e'], ['a', 'c'], ['d']]
1333 The output of _set_partitions can be passed as follows:
1335 >>> output = (3, [1, 0, 1, 2, 0])
1336 >>> _partition('abcde', *output)
1337 [['b', 'e'], ['a', 'c'], ['d']]
1339 See Also
1340 ========
1342 combinatorics.partitions.Partition.from_rgs
1344 """
1345 if m is None:
1346 m = max(vector) + 1
1347 elif isinstance(vector, int): # entered as m, vector
1348 vector, m = m, vector
1349 p = [[] for i in range(m)]
1350 for i, v in enumerate(vector):
1351 p[v].append(seq[i])
1352 return p
1355def _set_partitions(n):
1356 """Cycle through all partitions of n elements, yielding the
1357 current number of partitions, ``m``, and a mutable list, ``q``
1358 such that ``element[i]`` is in part ``q[i]`` of the partition.
1360 NOTE: ``q`` is modified in place and generally should not be changed
1361 between function calls.
1363 Examples
1364 ========
1366 >>> from sympy.utilities.iterables import _set_partitions, _partition
1367 >>> for m, q in _set_partitions(3):
1368 ... print('%s %s %s' % (m, q, _partition('abc', q, m)))
1369 1 [0, 0, 0] [['a', 'b', 'c']]
1370 2 [0, 0, 1] [['a', 'b'], ['c']]
1371 2 [0, 1, 0] [['a', 'c'], ['b']]
1372 2 [0, 1, 1] [['a'], ['b', 'c']]
1373 3 [0, 1, 2] [['a'], ['b'], ['c']]
1375 Notes
1376 =====
1378 This algorithm is similar to, and solves the same problem as,
1379 Algorithm 7.2.1.5H, from volume 4A of Knuth's The Art of Computer
1380 Programming. Knuth uses the term "restricted growth string" where
1381 this code refers to a "partition vector". In each case, the meaning is
1382 the same: the value in the ith element of the vector specifies to
1383 which part the ith set element is to be assigned.
1385 At the lowest level, this code implements an n-digit big-endian
1386 counter (stored in the array q) which is incremented (with carries) to
1387 get the next partition in the sequence. A special twist is that a
1388 digit is constrained to be at most one greater than the maximum of all
1389 the digits to the left of it. The array p maintains this maximum, so
1390 that the code can efficiently decide when a digit can be incremented
1391 in place or whether it needs to be reset to 0 and trigger a carry to
1392 the next digit. The enumeration starts with all the digits 0 (which
1393 corresponds to all the set elements being assigned to the same 0th
1394 part), and ends with 0123...n, which corresponds to each set element
1395 being assigned to a different, singleton, part.
1397 This routine was rewritten to use 0-based lists while trying to
1398 preserve the beauty and efficiency of the original algorithm.
1400 References
1401 ==========
1403 .. [1] Nijenhuis, Albert and Wilf, Herbert. (1978) Combinatorial Algorithms,
1404 2nd Ed, p 91, algorithm "nexequ". Available online from
1405 https://www.math.upenn.edu/~wilf/website/CombAlgDownld.html (viewed
1406 November 17, 2012).
1408 """
1409 p = [0]*n
1410 q = [0]*n
1411 nc = 1
1412 yield nc, q
1413 while nc != n:
1414 m = n
1415 while 1:
1416 m -= 1
1417 i = q[m]
1418 if p[i] != 1:
1419 break
1420 q[m] = 0
1421 i += 1
1422 q[m] = i
1423 m += 1
1424 nc += m - n
1425 p[0] += n - m
1426 if i == nc:
1427 p[nc] = 0
1428 nc += 1
1429 p[i - 1] -= 1
1430 p[i] += 1
1431 yield nc, q
1434def multiset_partitions(multiset, m=None):
1435 """
1436 Return unique partitions of the given multiset (in list form).
1437 If ``m`` is None, all multisets will be returned, otherwise only
1438 partitions with ``m`` parts will be returned.
1440 If ``multiset`` is an integer, a range [0, 1, ..., multiset - 1]
1441 will be supplied.
1443 Examples
1444 ========
1446 >>> from sympy.utilities.iterables import multiset_partitions
1447 >>> list(multiset_partitions([1, 2, 3, 4], 2))
1448 [[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 2], [3, 4]],
1449 [[1, 3, 4], [2]], [[1, 3], [2, 4]], [[1, 4], [2, 3]],
1450 [[1], [2, 3, 4]]]
1451 >>> list(multiset_partitions([1, 2, 3, 4], 1))
1452 [[[1, 2, 3, 4]]]
1454 Only unique partitions are returned and these will be returned in a
1455 canonical order regardless of the order of the input:
1457 >>> a = [1, 2, 2, 1]
1458 >>> ans = list(multiset_partitions(a, 2))
1459 >>> a.sort()
1460 >>> list(multiset_partitions(a, 2)) == ans
1461 True
1462 >>> a = range(3, 1, -1)
1463 >>> (list(multiset_partitions(a)) ==
1464 ... list(multiset_partitions(sorted(a))))
1465 True
1467 If m is omitted then all partitions will be returned:
1469 >>> list(multiset_partitions([1, 1, 2]))
1470 [[[1, 1, 2]], [[1, 1], [2]], [[1, 2], [1]], [[1], [1], [2]]]
1471 >>> list(multiset_partitions([1]*3))
1472 [[[1, 1, 1]], [[1], [1, 1]], [[1], [1], [1]]]
1474 Counting
1475 ========
1477 The number of partitions of a set is given by the bell number:
1479 >>> from sympy import bell
1480 >>> len(list(multiset_partitions(5))) == bell(5) == 52
1481 True
1483 The number of partitions of length k from a set of size n is given by the
1484 Stirling Number of the 2nd kind:
1486 >>> from sympy.functions.combinatorial.numbers import stirling
1487 >>> stirling(5, 2) == len(list(multiset_partitions(5, 2))) == 15
1488 True
1490 These comments on counting apply to *sets*, not multisets.
1492 Notes
1493 =====
1495 When all the elements are the same in the multiset, the order
1496 of the returned partitions is determined by the ``partitions``
1497 routine. If one is counting partitions then it is better to use
1498 the ``nT`` function.
1500 See Also
1501 ========
1503 partitions
1504 sympy.combinatorics.partitions.Partition
1505 sympy.combinatorics.partitions.IntegerPartition
1506 sympy.functions.combinatorial.numbers.nT
1508 """
1509 # This function looks at the supplied input and dispatches to
1510 # several special-case routines as they apply.
1511 if isinstance(multiset, int):
1512 n = multiset
1513 if m and m > n:
1514 return
1515 multiset = list(range(n))
1516 if m == 1:
1517 yield [multiset[:]]
1518 return
1520 # If m is not None, it can sometimes be faster to use
1521 # MultisetPartitionTraverser.enum_range() even for inputs
1522 # which are sets. Since the _set_partitions code is quite
1523 # fast, this is only advantageous when the overall set
1524 # partitions outnumber those with the desired number of parts
1525 # by a large factor. (At least 60.) Such a switch is not
1526 # currently implemented.
1527 for nc, q in _set_partitions(n):
1528 if m is None or nc == m:
1529 rv = [[] for i in range(nc)]
1530 for i in range(n):
1531 rv[q[i]].append(multiset[i])
1532 yield rv
1533 return
1535 if len(multiset) == 1 and isinstance(multiset, str):
1536 multiset = [multiset]
1538 if not has_variety(multiset):
1539 # Only one component, repeated n times. The resulting
1540 # partitions correspond to partitions of integer n.
1541 n = len(multiset)
1542 if m and m > n:
1543 return
1544 if m == 1:
1545 yield [multiset[:]]
1546 return
1547 x = multiset[:1]
1548 for size, p in partitions(n, m, size=True):
1549 if m is None or size == m:
1550 rv = []
1551 for k in sorted(p):
1552 rv.extend([x*k]*p[k])
1553 yield rv
1554 else:
1555 from sympy.core.sorting import ordered
1556 multiset = list(ordered(multiset))
1557 n = len(multiset)
1558 if m and m > n:
1559 return
1560 if m == 1:
1561 yield [multiset[:]]
1562 return
1564 # Split the information of the multiset into two lists -
1565 # one of the elements themselves, and one (of the same length)
1566 # giving the number of repeats for the corresponding element.
1567 elements, multiplicities = zip(*group(multiset, False))
1569 if len(elements) < len(multiset):
1570 # General case - multiset with more than one distinct element
1571 # and at least one element repeated more than once.
1572 if m:
1573 mpt = MultisetPartitionTraverser()
1574 for state in mpt.enum_range(multiplicities, m-1, m):
1575 yield list_visitor(state, elements)
1576 else:
1577 for state in multiset_partitions_taocp(multiplicities):
1578 yield list_visitor(state, elements)
1579 else:
1580 # Set partitions case - no repeated elements. Pretty much
1581 # same as int argument case above, with same possible, but
1582 # currently unimplemented optimization for some cases when
1583 # m is not None
1584 for nc, q in _set_partitions(n):
1585 if m is None or nc == m:
1586 rv = [[] for i in range(nc)]
1587 for i in range(n):
1588 rv[q[i]].append(i)
1589 yield [[multiset[j] for j in i] for i in rv]
1592def partitions(n, m=None, k=None, size=False):
1593 """Generate all partitions of positive integer, n.
1595 Parameters
1596 ==========
1598 m : integer (default gives partitions of all sizes)
1599 limits number of parts in partition (mnemonic: m, maximum parts)
1600 k : integer (default gives partitions number from 1 through n)
1601 limits the numbers that are kept in the partition (mnemonic: k, keys)
1602 size : bool (default False, only partition is returned)
1603 when ``True`` then (M, P) is returned where M is the sum of the
1604 multiplicities and P is the generated partition.
1606 Each partition is represented as a dictionary, mapping an integer
1607 to the number of copies of that integer in the partition. For example,
1608 the first partition of 4 returned is {4: 1}, "4: one of them".
1610 Examples
1611 ========
1613 >>> from sympy.utilities.iterables import partitions
1615 The numbers appearing in the partition (the key of the returned dict)
1616 are limited with k:
1618 >>> for p in partitions(6, k=2): # doctest: +SKIP
1619 ... print(p)
1620 {2: 3}
1621 {1: 2, 2: 2}
1622 {1: 4, 2: 1}
1623 {1: 6}
1625 The maximum number of parts in the partition (the sum of the values in
1626 the returned dict) are limited with m (default value, None, gives
1627 partitions from 1 through n):
1629 >>> for p in partitions(6, m=2): # doctest: +SKIP
1630 ... print(p)
1631 ...
1632 {6: 1}
1633 {1: 1, 5: 1}
1634 {2: 1, 4: 1}
1635 {3: 2}
1637 References
1638 ==========
1640 .. [1] modified from Tim Peter's version to allow for k and m values:
1641 https://code.activestate.com/recipes/218332-generator-for-integer-partitions/
1643 See Also
1644 ========
1646 sympy.combinatorics.partitions.Partition
1647 sympy.combinatorics.partitions.IntegerPartition
1649 """
1650 if (n <= 0 or
1651 m is not None and m < 1 or
1652 k is not None and k < 1 or
1653 m and k and m*k < n):
1654 # the empty set is the only way to handle these inputs
1655 # and returning {} to represent it is consistent with
1656 # the counting convention, e.g. nT(0) == 1.
1657 if size:
1658 yield 0, {}
1659 else:
1660 yield {}
1661 return
1663 if m is None:
1664 m = n
1665 else:
1666 m = min(m, n)
1667 k = min(k or n, n)
1669 n, m, k = as_int(n), as_int(m), as_int(k)
1670 q, r = divmod(n, k)
1671 ms = {k: q}
1672 keys = [k] # ms.keys(), from largest to smallest
1673 if r:
1674 ms[r] = 1
1675 keys.append(r)
1676 room = m - q - bool(r)
1677 if size:
1678 yield sum(ms.values()), ms.copy()
1679 else:
1680 yield ms.copy()
1682 while keys != [1]:
1683 # Reuse any 1's.
1684 if keys[-1] == 1:
1685 del keys[-1]
1686 reuse = ms.pop(1)
1687 room += reuse
1688 else:
1689 reuse = 0
1691 while 1:
1692 # Let i be the smallest key larger than 1. Reuse one
1693 # instance of i.
1694 i = keys[-1]
1695 newcount = ms[i] = ms[i] - 1
1696 reuse += i
1697 if newcount == 0:
1698 del keys[-1], ms[i]
1699 room += 1
1701 # Break the remainder into pieces of size i-1.
1702 i -= 1
1703 q, r = divmod(reuse, i)
1704 need = q + bool(r)
1705 if need > room:
1706 if not keys:
1707 return
1708 continue
1710 ms[i] = q
1711 keys.append(i)
1712 if r:
1713 ms[r] = 1
1714 keys.append(r)
1715 break
1716 room -= need
1717 if size:
1718 yield sum(ms.values()), ms.copy()
1719 else:
1720 yield ms.copy()
1723def ordered_partitions(n, m=None, sort=True):
1724 """Generates ordered partitions of integer ``n``.
1726 Parameters
1727 ==========
1729 m : integer (default None)
1730 The default value gives partitions of all sizes else only
1731 those with size m. In addition, if ``m`` is not None then
1732 partitions are generated *in place* (see examples).
1733 sort : bool (default True)
1734 Controls whether partitions are
1735 returned in sorted order when ``m`` is not None; when False,
1736 the partitions are returned as fast as possible with elements
1737 sorted, but when m|n the partitions will not be in
1738 ascending lexicographical order.
1740 Examples
1741 ========
1743 >>> from sympy.utilities.iterables import ordered_partitions
1745 All partitions of 5 in ascending lexicographical:
1747 >>> for p in ordered_partitions(5):
1748 ... print(p)
1749 [1, 1, 1, 1, 1]
1750 [1, 1, 1, 2]
1751 [1, 1, 3]
1752 [1, 2, 2]
1753 [1, 4]
1754 [2, 3]
1755 [5]
1757 Only partitions of 5 with two parts:
1759 >>> for p in ordered_partitions(5, 2):
1760 ... print(p)
1761 [1, 4]
1762 [2, 3]
1764 When ``m`` is given, a given list objects will be used more than
1765 once for speed reasons so you will not see the correct partitions
1766 unless you make a copy of each as it is generated:
1768 >>> [p for p in ordered_partitions(7, 3)]
1769 [[1, 1, 1], [1, 1, 1], [1, 1, 1], [2, 2, 2]]
1770 >>> [list(p) for p in ordered_partitions(7, 3)]
1771 [[1, 1, 5], [1, 2, 4], [1, 3, 3], [2, 2, 3]]
1773 When ``n`` is a multiple of ``m``, the elements are still sorted
1774 but the partitions themselves will be *unordered* if sort is False;
1775 the default is to return them in ascending lexicographical order.
1777 >>> for p in ordered_partitions(6, 2):
1778 ... print(p)
1779 [1, 5]
1780 [2, 4]
1781 [3, 3]
1783 But if speed is more important than ordering, sort can be set to
1784 False:
1786 >>> for p in ordered_partitions(6, 2, sort=False):
1787 ... print(p)
1788 [1, 5]
1789 [3, 3]
1790 [2, 4]
1792 References
1793 ==========
1795 .. [1] Generating Integer Partitions, [online],
1796 Available: https://jeromekelleher.net/generating-integer-partitions.html
1797 .. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
1798 Partitions: A Comparison Of Two Encodings", [online],
1799 Available: https://arxiv.org/pdf/0909.2331v2.pdf
1800 """
1801 if n < 1 or m is not None and m < 1:
1802 # the empty set is the only way to handle these inputs
1803 # and returning {} to represent it is consistent with
1804 # the counting convention, e.g. nT(0) == 1.
1805 yield []
1806 return
1808 if m is None:
1809 # The list `a`'s leading elements contain the partition in which
1810 # y is the biggest element and x is either the same as y or the
1811 # 2nd largest element; v and w are adjacent element indices
1812 # to which x and y are being assigned, respectively.
1813 a = [1]*n
1814 y = -1
1815 v = n
1816 while v > 0:
1817 v -= 1
1818 x = a[v] + 1
1819 while y >= 2 * x:
1820 a[v] = x
1821 y -= x
1822 v += 1
1823 w = v + 1
1824 while x <= y:
1825 a[v] = x
1826 a[w] = y
1827 yield a[:w + 1]
1828 x += 1
1829 y -= 1
1830 a[v] = x + y
1831 y = a[v] - 1
1832 yield a[:w]
1833 elif m == 1:
1834 yield [n]
1835 elif n == m:
1836 yield [1]*n
1837 else:
1838 # recursively generate partitions of size m
1839 for b in range(1, n//m + 1):
1840 a = [b]*m
1841 x = n - b*m
1842 if not x:
1843 if sort:
1844 yield a
1845 elif not sort and x <= m:
1846 for ax in ordered_partitions(x, sort=False):
1847 mi = len(ax)
1848 a[-mi:] = [i + b for i in ax]
1849 yield a
1850 a[-mi:] = [b]*mi
1851 else:
1852 for mi in range(1, m):
1853 for ax in ordered_partitions(x, mi, sort=True):
1854 a[-mi:] = [i + b for i in ax]
1855 yield a
1856 a[-mi:] = [b]*mi
1859def binary_partitions(n):
1860 """
1861 Generates the binary partition of n.
1863 A binary partition consists only of numbers that are
1864 powers of two. Each step reduces a `2^{k+1}` to `2^k` and
1865 `2^k`. Thus 16 is converted to 8 and 8.
1867 Examples
1868 ========
1870 >>> from sympy.utilities.iterables import binary_partitions
1871 >>> for i in binary_partitions(5):
1872 ... print(i)
1873 ...
1874 [4, 1]
1875 [2, 2, 1]
1876 [2, 1, 1, 1]
1877 [1, 1, 1, 1, 1]
1879 References
1880 ==========
1882 .. [1] TAOCP 4, section 7.2.1.5, problem 64
1884 """
1885 from math import ceil, log
1886 power = int(2**(ceil(log(n, 2))))
1887 acc = 0
1888 partition = []
1889 while power:
1890 if acc + power <= n:
1891 partition.append(power)
1892 acc += power
1893 power >>= 1
1895 last_num = len(partition) - 1 - (n & 1)
1896 while last_num >= 0:
1897 yield partition
1898 if partition[last_num] == 2:
1899 partition[last_num] = 1
1900 partition.append(1)
1901 last_num -= 1
1902 continue
1903 partition.append(1)
1904 partition[last_num] >>= 1
1905 x = partition[last_num + 1] = partition[last_num]
1906 last_num += 1
1907 while x > 1:
1908 if x <= len(partition) - last_num - 1:
1909 del partition[-x + 1:]
1910 last_num += 1
1911 partition[last_num] = x
1912 else:
1913 x >>= 1
1914 yield [1]*n
1917def has_dups(seq):
1918 """Return True if there are any duplicate elements in ``seq``.
1920 Examples
1921 ========
1923 >>> from sympy import has_dups, Dict, Set
1924 >>> has_dups((1, 2, 1))
1925 True
1926 >>> has_dups(range(3))
1927 False
1928 >>> all(has_dups(c) is False for c in (set(), Set(), dict(), Dict()))
1929 True
1930 """
1931 from sympy.core.containers import Dict
1932 from sympy.sets.sets import Set
1933 if isinstance(seq, (dict, set, Dict, Set)):
1934 return False
1935 unique = set()
1936 try:
1937 return any(True for s in seq if s in unique or unique.add(s))
1938 except TypeError:
1939 return len(seq) != len(list(uniq(seq)))
1942def has_variety(seq):
1943 """Return True if there are any different elements in ``seq``.
1945 Examples
1946 ========
1948 >>> from sympy import has_variety
1950 >>> has_variety((1, 2, 1))
1951 True
1952 >>> has_variety((1, 1, 1))
1953 False
1954 """
1955 for i, s in enumerate(seq):
1956 if i == 0:
1957 sentinel = s
1958 else:
1959 if s != sentinel:
1960 return True
1961 return False
1964def uniq(seq, result=None):
1965 """
1966 Yield unique elements from ``seq`` as an iterator. The second
1967 parameter ``result`` is used internally; it is not necessary
1968 to pass anything for this.
1970 Note: changing the sequence during iteration will raise a
1971 RuntimeError if the size of the sequence is known; if you pass
1972 an iterator and advance the iterator you will change the
1973 output of this routine but there will be no warning.
1975 Examples
1976 ========
1978 >>> from sympy.utilities.iterables import uniq
1979 >>> dat = [1, 4, 1, 5, 4, 2, 1, 2]
1980 >>> type(uniq(dat)) in (list, tuple)
1981 False
1983 >>> list(uniq(dat))
1984 [1, 4, 5, 2]
1985 >>> list(uniq(x for x in dat))
1986 [1, 4, 5, 2]
1987 >>> list(uniq([[1], [2, 1], [1]]))
1988 [[1], [2, 1]]
1989 """
1990 try:
1991 n = len(seq)
1992 except TypeError:
1993 n = None
1994 def check():
1995 # check that size of seq did not change during iteration;
1996 # if n == None the object won't support size changing, e.g.
1997 # an iterator can't be changed
1998 if n is not None and len(seq) != n:
1999 raise RuntimeError('sequence changed size during iteration')
2000 try:
2001 seen = set()
2002 result = result or []
2003 for i, s in enumerate(seq):
2004 if not (s in seen or seen.add(s)):
2005 yield s
2006 check()
2007 except TypeError:
2008 if s not in result:
2009 yield s
2010 check()
2011 result.append(s)
2012 if hasattr(seq, '__getitem__'):
2013 yield from uniq(seq[i + 1:], result)
2014 else:
2015 yield from uniq(seq, result)
2018def generate_bell(n):
2019 """Return permutations of [0, 1, ..., n - 1] such that each permutation
2020 differs from the last by the exchange of a single pair of neighbors.
2021 The ``n!`` permutations are returned as an iterator. In order to obtain
2022 the next permutation from a random starting permutation, use the
2023 ``next_trotterjohnson`` method of the Permutation class (which generates
2024 the same sequence in a different manner).
2026 Examples
2027 ========
2029 >>> from itertools import permutations
2030 >>> from sympy.utilities.iterables import generate_bell
2031 >>> from sympy import zeros, Matrix
2033 This is the sort of permutation used in the ringing of physical bells,
2034 and does not produce permutations in lexicographical order. Rather, the
2035 permutations differ from each other by exactly one inversion, and the
2036 position at which the swapping occurs varies periodically in a simple
2037 fashion. Consider the first few permutations of 4 elements generated
2038 by ``permutations`` and ``generate_bell``:
2040 >>> list(permutations(range(4)))[:5]
2041 [(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2)]
2042 >>> list(generate_bell(4))[:5]
2043 [(0, 1, 2, 3), (0, 1, 3, 2), (0, 3, 1, 2), (3, 0, 1, 2), (3, 0, 2, 1)]
2045 Notice how the 2nd and 3rd lexicographical permutations have 3 elements
2046 out of place whereas each "bell" permutation always has only two
2047 elements out of place relative to the previous permutation (and so the
2048 signature (+/-1) of a permutation is opposite of the signature of the
2049 previous permutation).
2051 How the position of inversion varies across the elements can be seen
2052 by tracing out where the largest number appears in the permutations:
2054 >>> m = zeros(4, 24)
2055 >>> for i, p in enumerate(generate_bell(4)):
2056 ... m[:, i] = Matrix([j - 3 for j in list(p)]) # make largest zero
2057 >>> m.print_nonzero('X')
2058 [XXX XXXXXX XXXXXX XXX]
2059 [XX XX XXXX XX XXXX XX XX]
2060 [X XXXX XX XXXX XX XXXX X]
2061 [ XXXXXX XXXXXX XXXXXX ]
2063 See Also
2064 ========
2066 sympy.combinatorics.permutations.Permutation.next_trotterjohnson
2068 References
2069 ==========
2071 .. [1] https://en.wikipedia.org/wiki/Method_ringing
2073 .. [2] https://stackoverflow.com/questions/4856615/recursive-permutation/4857018
2075 .. [3] https://web.archive.org/web/20160313023044/http://programminggeeks.com/bell-algorithm-for-permutation/
2077 .. [4] https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm
2079 .. [5] Generating involutions, derangements, and relatives by ECO
2080 Vincent Vajnovszki, DMTCS vol 1 issue 12, 2010
2082 """
2083 n = as_int(n)
2084 if n < 1:
2085 raise ValueError('n must be a positive integer')
2086 if n == 1:
2087 yield (0,)
2088 elif n == 2:
2089 yield (0, 1)
2090 yield (1, 0)
2091 elif n == 3:
2092 yield from [(0, 1, 2), (0, 2, 1), (2, 0, 1), (2, 1, 0), (1, 2, 0), (1, 0, 2)]
2093 else:
2094 m = n - 1
2095 op = [0] + [-1]*m
2096 l = list(range(n))
2097 while True:
2098 yield tuple(l)
2099 # find biggest element with op
2100 big = None, -1 # idx, value
2101 for i in range(n):
2102 if op[i] and l[i] > big[1]:
2103 big = i, l[i]
2104 i, _ = big
2105 if i is None:
2106 break # there are no ops left
2107 # swap it with neighbor in the indicated direction
2108 j = i + op[i]
2109 l[i], l[j] = l[j], l[i]
2110 op[i], op[j] = op[j], op[i]
2111 # if it landed at the end or if the neighbor in the same
2112 # direction is bigger then turn off op
2113 if j == 0 or j == m or l[j + op[j]] > l[j]:
2114 op[j] = 0
2115 # any element bigger to the left gets +1 op
2116 for i in range(j):
2117 if l[i] > l[j]:
2118 op[i] = 1
2119 # any element bigger to the right gets -1 op
2120 for i in range(j + 1, n):
2121 if l[i] > l[j]:
2122 op[i] = -1
2125def generate_involutions(n):
2126 """
2127 Generates involutions.
2129 An involution is a permutation that when multiplied
2130 by itself equals the identity permutation. In this
2131 implementation the involutions are generated using
2132 Fixed Points.
2134 Alternatively, an involution can be considered as
2135 a permutation that does not contain any cycles with
2136 a length that is greater than two.
2138 Examples
2139 ========
2141 >>> from sympy.utilities.iterables import generate_involutions
2142 >>> list(generate_involutions(3))
2143 [(0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 1, 0)]
2144 >>> len(list(generate_involutions(4)))
2145 10
2147 References
2148 ==========
2150 .. [1] https://mathworld.wolfram.com/PermutationInvolution.html
2152 """
2153 idx = list(range(n))
2154 for p in permutations(idx):
2155 for i in idx:
2156 if p[p[i]] != i:
2157 break
2158 else:
2159 yield p
2162def multiset_derangements(s):
2163 """Generate derangements of the elements of s *in place*.
2165 Examples
2166 ========
2168 >>> from sympy.utilities.iterables import multiset_derangements, uniq
2170 Because the derangements of multisets (not sets) are generated
2171 in place, copies of the return value must be made if a collection
2172 of derangements is desired or else all values will be the same:
2174 >>> list(uniq([i for i in multiset_derangements('1233')]))
2175 [[None, None, None, None]]
2176 >>> [i.copy() for i in multiset_derangements('1233')]
2177 [['3', '3', '1', '2'], ['3', '3', '2', '1']]
2178 >>> [''.join(i) for i in multiset_derangements('1233')]
2179 ['3312', '3321']
2180 """
2181 from sympy.core.sorting import ordered
2182 # create multiset dictionary of hashable elements or else
2183 # remap elements to integers
2184 try:
2185 ms = multiset(s)
2186 except TypeError:
2187 # give each element a canonical integer value
2188 key = dict(enumerate(ordered(uniq(s))))
2189 h = []
2190 for si in s:
2191 for k in key:
2192 if key[k] == si:
2193 h.append(k)
2194 break
2195 for i in multiset_derangements(h):
2196 yield [key[j] for j in i]
2197 return
2199 mx = max(ms.values()) # max repetition of any element
2200 n = len(s) # the number of elements
2202 ## special cases
2204 # 1) one element has more than half the total cardinality of s: no
2205 # derangements are possible.
2206 if mx*2 > n:
2207 return
2209 # 2) all elements appear once: singletons
2210 if len(ms) == n:
2211 yield from _set_derangements(s)
2212 return
2214 # find the first element that is repeated the most to place
2215 # in the following two special cases where the selection
2216 # is unambiguous: either there are two elements with multiplicity
2217 # of mx or else there is only one with multiplicity mx
2218 for M in ms:
2219 if ms[M] == mx:
2220 break
2222 inonM = [i for i in range(n) if s[i] != M] # location of non-M
2223 iM = [i for i in range(n) if s[i] == M] # locations of M
2224 rv = [None]*n
2226 # 3) half are the same
2227 if 2*mx == n:
2228 # M goes into non-M locations
2229 for i in inonM:
2230 rv[i] = M
2231 # permutations of non-M go to M locations
2232 for p in multiset_permutations([s[i] for i in inonM]):
2233 for i, pi in zip(iM, p):
2234 rv[i] = pi
2235 yield rv
2236 # clean-up (and encourages proper use of routine)
2237 rv[:] = [None]*n
2238 return
2240 # 4) single repeat covers all but 1 of the non-repeats:
2241 # if there is one repeat then the multiset of the values
2242 # of ms would be {mx: 1, 1: n - mx}, i.e. there would
2243 # be n - mx + 1 values with the condition that n - 2*mx = 1
2244 if n - 2*mx == 1 and len(ms.values()) == n - mx + 1:
2245 for i, i1 in enumerate(inonM):
2246 ifill = inonM[:i] + inonM[i+1:]
2247 for j in ifill:
2248 rv[j] = M
2249 for p in permutations([s[j] for j in ifill]):
2250 rv[i1] = s[i1]
2251 for j, pi in zip(iM, p):
2252 rv[j] = pi
2253 k = i1
2254 for j in iM:
2255 rv[j], rv[k] = rv[k], rv[j]
2256 yield rv
2257 k = j
2258 # clean-up (and encourages proper use of routine)
2259 rv[:] = [None]*n
2260 return
2262 ## general case is handled with 3 helpers:
2263 # 1) `finish_derangements` will place the last two elements
2264 # which have arbitrary multiplicities, e.g. for multiset
2265 # {c: 3, a: 2, b: 2}, the last two elements are a and b
2266 # 2) `iopen` will tell where a given element can be placed
2267 # 3) `do` will recursively place elements into subsets of
2268 # valid locations
2270 def finish_derangements():
2271 """Place the last two elements into the partially completed
2272 derangement, and yield the results.
2273 """
2275 a = take[1][0] # penultimate element
2276 a_ct = take[1][1]
2277 b = take[0][0] # last element to be placed
2278 b_ct = take[0][1]
2280 # split the indexes of the not-already-assigned elements of rv into
2281 # three categories
2282 forced_a = [] # positions which must have an a
2283 forced_b = [] # positions which must have a b
2284 open_free = [] # positions which could take either
2285 for i in range(len(s)):
2286 if rv[i] is None:
2287 if s[i] == a:
2288 forced_b.append(i)
2289 elif s[i] == b:
2290 forced_a.append(i)
2291 else:
2292 open_free.append(i)
2294 if len(forced_a) > a_ct or len(forced_b) > b_ct:
2295 # No derangement possible
2296 return
2298 for i in forced_a:
2299 rv[i] = a
2300 for i in forced_b:
2301 rv[i] = b
2302 for a_place in combinations(open_free, a_ct - len(forced_a)):
2303 for a_pos in a_place:
2304 rv[a_pos] = a
2305 for i in open_free:
2306 if rv[i] is None: # anything not in the subset is set to b
2307 rv[i] = b
2308 yield rv
2309 # Clean up/undo the final placements
2310 for i in open_free:
2311 rv[i] = None
2313 # additional cleanup - clear forced_a, forced_b
2314 for i in forced_a:
2315 rv[i] = None
2316 for i in forced_b:
2317 rv[i] = None
2319 def iopen(v):
2320 # return indices at which element v can be placed in rv:
2321 # locations which are not already occupied if that location
2322 # does not already contain v in the same location of s
2323 return [i for i in range(n) if rv[i] is None and s[i] != v]
2325 def do(j):
2326 if j == 1:
2327 # handle the last two elements (regardless of multiplicity)
2328 # with a special method
2329 yield from finish_derangements()
2330 else:
2331 # place the mx elements of M into a subset of places
2332 # into which it can be replaced
2333 M, mx = take[j]
2334 for i in combinations(iopen(M), mx):
2335 # place M
2336 for ii in i:
2337 rv[ii] = M
2338 # recursively place the next element
2339 yield from do(j - 1)
2340 # mark positions where M was placed as once again
2341 # open for placement of other elements
2342 for ii in i:
2343 rv[ii] = None
2345 # process elements in order of canonically decreasing multiplicity
2346 take = sorted(ms.items(), key=lambda x:(x[1], x[0]))
2347 yield from do(len(take) - 1)
2348 rv[:] = [None]*n
2351def random_derangement(t, choice=None, strict=True):
2352 """Return a list of elements in which none are in the same positions
2353 as they were originally. If an element fills more than half of the positions
2354 then an error will be raised since no derangement is possible. To obtain
2355 a derangement of as many items as possible--with some of the most numerous
2356 remaining in their original positions--pass `strict=False`. To produce a
2357 pseudorandom derangment, pass a pseudorandom selector like `choice` (see
2358 below).
2360 Examples
2361 ========
2363 >>> from sympy.utilities.iterables import random_derangement
2364 >>> t = 'SymPy: a CAS in pure Python'
2365 >>> d = random_derangement(t)
2366 >>> all(i != j for i, j in zip(d, t))
2367 True
2369 A predictable result can be obtained by using a pseudorandom
2370 generator for the choice:
2372 >>> from sympy.core.random import seed, choice as c
2373 >>> seed(1)
2374 >>> d = [''.join(random_derangement(t, c)) for i in range(5)]
2375 >>> assert len(set(d)) != 1 # we got different values
2377 By reseeding, the same sequence can be obtained:
2379 >>> seed(1)
2380 >>> d2 = [''.join(random_derangement(t, c)) for i in range(5)]
2381 >>> assert d == d2
2382 """
2383 if choice is None:
2384 import secrets
2385 choice = secrets.choice
2386 def shuffle(rv):
2387 '''Knuth shuffle'''
2388 for i in range(len(rv) - 1, 0, -1):
2389 x = choice(rv[:i + 1])
2390 j = rv.index(x)
2391 rv[i], rv[j] = rv[j], rv[i]
2392 def pick(rv, n):
2393 '''shuffle rv and return the first n values
2394 '''
2395 shuffle(rv)
2396 return rv[:n]
2397 ms = multiset(t)
2398 tot = len(t)
2399 ms = sorted(ms.items(), key=lambda x: x[1])
2400 # if there are not enough spaces for the most
2401 # plentiful element to move to then some of them
2402 # will have to stay in place
2403 M, mx = ms[-1]
2404 n = len(t)
2405 xs = 2*mx - tot
2406 if xs > 0:
2407 if strict:
2408 raise ValueError('no derangement possible')
2409 opts = [i for (i, c) in enumerate(t) if c == ms[-1][0]]
2410 pick(opts, xs)
2411 stay = sorted(opts[:xs])
2412 rv = list(t)
2413 for i in reversed(stay):
2414 rv.pop(i)
2415 rv = random_derangement(rv, choice)
2416 for i in stay:
2417 rv.insert(i, ms[-1][0])
2418 return ''.join(rv) if type(t) is str else rv
2419 # the normal derangement calculated from here
2420 if n == len(ms):
2421 # approx 1/3 will succeed
2422 rv = list(t)
2423 while True:
2424 shuffle(rv)
2425 if all(i != j for i,j in zip(rv, t)):
2426 break
2427 else:
2428 # general case
2429 rv = [None]*n
2430 while True:
2431 j = 0
2432 while j > -len(ms): # do most numerous first
2433 j -= 1
2434 e, c = ms[j]
2435 opts = [i for i in range(n) if rv[i] is None and t[i] != e]
2436 if len(opts) < c:
2437 for i in range(n):
2438 rv[i] = None
2439 break # try again
2440 pick(opts, c)
2441 for i in range(c):
2442 rv[opts[i]] = e
2443 else:
2444 return rv
2445 return rv
2448def _set_derangements(s):
2449 """
2450 yield derangements of items in ``s`` which are assumed to contain
2451 no repeated elements
2452 """
2453 if len(s) < 2:
2454 return
2455 if len(s) == 2:
2456 yield [s[1], s[0]]
2457 return
2458 if len(s) == 3:
2459 yield [s[1], s[2], s[0]]
2460 yield [s[2], s[0], s[1]]
2461 return
2462 for p in permutations(s):
2463 if not any(i == j for i, j in zip(p, s)):
2464 yield list(p)
2467def generate_derangements(s):
2468 """
2469 Return unique derangements of the elements of iterable ``s``.
2471 Examples
2472 ========
2474 >>> from sympy.utilities.iterables import generate_derangements
2475 >>> list(generate_derangements([0, 1, 2]))
2476 [[1, 2, 0], [2, 0, 1]]
2477 >>> list(generate_derangements([0, 1, 2, 2]))
2478 [[2, 2, 0, 1], [2, 2, 1, 0]]
2479 >>> list(generate_derangements([0, 1, 1]))
2480 []
2482 See Also
2483 ========
2485 sympy.functions.combinatorial.factorials.subfactorial
2487 """
2488 if not has_dups(s):
2489 yield from _set_derangements(s)
2490 else:
2491 for p in multiset_derangements(s):
2492 yield list(p)
2495def necklaces(n, k, free=False):
2496 """
2497 A routine to generate necklaces that may (free=True) or may not
2498 (free=False) be turned over to be viewed. The "necklaces" returned
2499 are comprised of ``n`` integers (beads) with ``k`` different
2500 values (colors). Only unique necklaces are returned.
2502 Examples
2503 ========
2505 >>> from sympy.utilities.iterables import necklaces, bracelets
2506 >>> def show(s, i):
2507 ... return ''.join(s[j] for j in i)
2509 The "unrestricted necklace" is sometimes also referred to as a
2510 "bracelet" (an object that can be turned over, a sequence that can
2511 be reversed) and the term "necklace" is used to imply a sequence
2512 that cannot be reversed. So ACB == ABC for a bracelet (rotate and
2513 reverse) while the two are different for a necklace since rotation
2514 alone cannot make the two sequences the same.
2516 (mnemonic: Bracelets can be viewed Backwards, but Not Necklaces.)
2518 >>> B = [show('ABC', i) for i in bracelets(3, 3)]
2519 >>> N = [show('ABC', i) for i in necklaces(3, 3)]
2520 >>> set(N) - set(B)
2521 {'ACB'}
2523 >>> list(necklaces(4, 2))
2524 [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1),
2525 (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]
2527 >>> [show('.o', i) for i in bracelets(4, 2)]
2528 ['....', '...o', '..oo', '.o.o', '.ooo', 'oooo']
2530 References
2531 ==========
2533 .. [1] https://mathworld.wolfram.com/Necklace.html
2535 .. [2] Frank Ruskey, Carla Savage, and Terry Min Yih Wang,
2536 Generating necklaces, Journal of Algorithms 13 (1992), 414-430;
2537 https://doi.org/10.1016/0196-6774(92)90047-G
2539 """
2540 # The FKM algorithm
2541 if k == 0 and n > 0:
2542 return
2543 a = [0]*n
2544 yield tuple(a)
2545 if n == 0:
2546 return
2547 while True:
2548 i = n - 1
2549 while a[i] == k - 1:
2550 i -= 1
2551 if i == -1:
2552 return
2553 a[i] += 1
2554 for j in range(n - i - 1):
2555 a[j + i + 1] = a[j]
2556 if n % (i + 1) == 0 and (not free or all(a <= a[j::-1] + a[-1:j:-1] for j in range(n - 1))):
2557 # No need to test j = n - 1.
2558 yield tuple(a)
2561def bracelets(n, k):
2562 """Wrapper to necklaces to return a free (unrestricted) necklace."""
2563 return necklaces(n, k, free=True)
2566def generate_oriented_forest(n):
2567 """
2568 This algorithm generates oriented forests.
2570 An oriented graph is a directed graph having no symmetric pair of directed
2571 edges. A forest is an acyclic graph, i.e., it has no cycles. A forest can
2572 also be described as a disjoint union of trees, which are graphs in which
2573 any two vertices are connected by exactly one simple path.
2575 Examples
2576 ========
2578 >>> from sympy.utilities.iterables import generate_oriented_forest
2579 >>> list(generate_oriented_forest(4))
2580 [[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0], \
2581 [0, 1, 1, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
2583 References
2584 ==========
2586 .. [1] T. Beyer and S.M. Hedetniemi: constant time generation of
2587 rooted trees, SIAM J. Computing Vol. 9, No. 4, November 1980
2589 .. [2] https://stackoverflow.com/questions/1633833/oriented-forest-taocp-algorithm-in-python
2591 """
2592 P = list(range(-1, n))
2593 while True:
2594 yield P[1:]
2595 if P[n] > 0:
2596 P[n] = P[P[n]]
2597 else:
2598 for p in range(n - 1, 0, -1):
2599 if P[p] != 0:
2600 target = P[p] - 1
2601 for q in range(p - 1, 0, -1):
2602 if P[q] == target:
2603 break
2604 offset = p - q
2605 for i in range(p, n + 1):
2606 P[i] = P[i - offset]
2607 break
2608 else:
2609 break
2612def minlex(seq, directed=True, key=None):
2613 r"""
2614 Return the rotation of the sequence in which the lexically smallest
2615 elements appear first, e.g. `cba \rightarrow acb`.
2617 The sequence returned is a tuple, unless the input sequence is a string
2618 in which case a string is returned.
2620 If ``directed`` is False then the smaller of the sequence and the
2621 reversed sequence is returned, e.g. `cba \rightarrow abc`.
2623 If ``key`` is not None then it is used to extract a comparison key from each element in iterable.
2625 Examples
2626 ========
2628 >>> from sympy.combinatorics.polyhedron import minlex
2629 >>> minlex((1, 2, 0))
2630 (0, 1, 2)
2631 >>> minlex((1, 0, 2))
2632 (0, 2, 1)
2633 >>> minlex((1, 0, 2), directed=False)
2634 (0, 1, 2)
2636 >>> minlex('11010011000', directed=True)
2637 '00011010011'
2638 >>> minlex('11010011000', directed=False)
2639 '00011001011'
2641 >>> minlex(('bb', 'aaa', 'c', 'a'))
2642 ('a', 'bb', 'aaa', 'c')
2643 >>> minlex(('bb', 'aaa', 'c', 'a'), key=len)
2644 ('c', 'a', 'bb', 'aaa')
2646 """
2647 from sympy.functions.elementary.miscellaneous import Id
2648 if key is None: key = Id
2649 best = rotate_left(seq, least_rotation(seq, key=key))
2650 if not directed:
2651 rseq = seq[::-1]
2652 rbest = rotate_left(rseq, least_rotation(rseq, key=key))
2653 best = min(best, rbest, key=key)
2655 # Convert to tuple, unless we started with a string.
2656 return tuple(best) if not isinstance(seq, str) else best
2659def runs(seq, op=gt):
2660 """Group the sequence into lists in which successive elements
2661 all compare the same with the comparison operator, ``op``:
2662 op(seq[i + 1], seq[i]) is True from all elements in a run.
2664 Examples
2665 ========
2667 >>> from sympy.utilities.iterables import runs
2668 >>> from operator import ge
2669 >>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2])
2670 [[0, 1, 2], [2], [1, 4], [3], [2], [2]]
2671 >>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2], op=ge)
2672 [[0, 1, 2, 2], [1, 4], [3], [2, 2]]
2673 """
2674 cycles = []
2675 seq = iter(seq)
2676 try:
2677 run = [next(seq)]
2678 except StopIteration:
2679 return []
2680 while True:
2681 try:
2682 ei = next(seq)
2683 except StopIteration:
2684 break
2685 if op(ei, run[-1]):
2686 run.append(ei)
2687 continue
2688 else:
2689 cycles.append(run)
2690 run = [ei]
2691 if run:
2692 cycles.append(run)
2693 return cycles
2696def sequence_partitions(l, n, /):
2697 r"""Returns the partition of sequence $l$ into $n$ bins
2699 Explanation
2700 ===========
2702 Given the sequence $l_1 \cdots l_m \in V^+$ where
2703 $V^+$ is the Kleene plus of $V$
2705 The set of $n$ partitions of $l$ is defined as:
2707 .. math::
2708 \{(s_1, \cdots, s_n) | s_1 \in V^+, \cdots, s_n \in V^+,
2709 s_1 \cdots s_n = l_1 \cdots l_m\}
2711 Parameters
2712 ==========
2714 l : Sequence[T]
2715 A nonempty sequence of any Python objects
2717 n : int
2718 A positive integer
2720 Yields
2721 ======
2723 out : list[Sequence[T]]
2724 A list of sequences with concatenation equals $l$.
2725 This should conform with the type of $l$.
2727 Examples
2728 ========
2730 >>> from sympy.utilities.iterables import sequence_partitions
2731 >>> for out in sequence_partitions([1, 2, 3, 4], 2):
2732 ... print(out)
2733 [[1], [2, 3, 4]]
2734 [[1, 2], [3, 4]]
2735 [[1, 2, 3], [4]]
2737 Notes
2738 =====
2740 This is modified version of EnricoGiampieri's partition generator
2741 from https://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily
2743 See Also
2744 ========
2746 sequence_partitions_empty
2747 """
2748 # Asserting l is nonempty is done only for sanity check
2749 if n == 1 and l:
2750 yield [l]
2751 return
2752 for i in range(1, len(l)):
2753 for part in sequence_partitions(l[i:], n - 1):
2754 yield [l[:i]] + part
2757def sequence_partitions_empty(l, n, /):
2758 r"""Returns the partition of sequence $l$ into $n$ bins with
2759 empty sequence
2761 Explanation
2762 ===========
2764 Given the sequence $l_1 \cdots l_m \in V^*$ where
2765 $V^*$ is the Kleene star of $V$
2767 The set of $n$ partitions of $l$ is defined as:
2769 .. math::
2770 \{(s_1, \cdots, s_n) | s_1 \in V^*, \cdots, s_n \in V^*,
2771 s_1 \cdots s_n = l_1 \cdots l_m\}
2773 There are more combinations than :func:`sequence_partitions` because
2774 empty sequence can fill everywhere, so we try to provide different
2775 utility for this.
2777 Parameters
2778 ==========
2780 l : Sequence[T]
2781 A sequence of any Python objects (can be possibly empty)
2783 n : int
2784 A positive integer
2786 Yields
2787 ======
2789 out : list[Sequence[T]]
2790 A list of sequences with concatenation equals $l$.
2791 This should conform with the type of $l$.
2793 Examples
2794 ========
2796 >>> from sympy.utilities.iterables import sequence_partitions_empty
2797 >>> for out in sequence_partitions_empty([1, 2, 3, 4], 2):
2798 ... print(out)
2799 [[], [1, 2, 3, 4]]
2800 [[1], [2, 3, 4]]
2801 [[1, 2], [3, 4]]
2802 [[1, 2, 3], [4]]
2803 [[1, 2, 3, 4], []]
2805 See Also
2806 ========
2808 sequence_partitions
2809 """
2810 if n < 1:
2811 return
2812 if n == 1:
2813 yield [l]
2814 return
2815 for i in range(0, len(l) + 1):
2816 for part in sequence_partitions_empty(l[i:], n - 1):
2817 yield [l[:i]] + part
2820def kbins(l, k, ordered=None):
2821 """
2822 Return sequence ``l`` partitioned into ``k`` bins.
2824 Examples
2825 ========
2827 The default is to give the items in the same order, but grouped
2828 into k partitions without any reordering:
2830 >>> from sympy.utilities.iterables import kbins
2831 >>> for p in kbins(list(range(5)), 2):
2832 ... print(p)
2833 ...
2834 [[0], [1, 2, 3, 4]]
2835 [[0, 1], [2, 3, 4]]
2836 [[0, 1, 2], [3, 4]]
2837 [[0, 1, 2, 3], [4]]
2839 The ``ordered`` flag is either None (to give the simple partition
2840 of the elements) or is a 2 digit integer indicating whether the order of
2841 the bins and the order of the items in the bins matters. Given::
2843 A = [[0], [1, 2]]
2844 B = [[1, 2], [0]]
2845 C = [[2, 1], [0]]
2846 D = [[0], [2, 1]]
2848 the following values for ``ordered`` have the shown meanings::
2850 00 means A == B == C == D
2851 01 means A == B
2852 10 means A == D
2853 11 means A == A
2855 >>> for ordered_flag in [None, 0, 1, 10, 11]:
2856 ... print('ordered = %s' % ordered_flag)
2857 ... for p in kbins(list(range(3)), 2, ordered=ordered_flag):
2858 ... print(' %s' % p)
2859 ...
2860 ordered = None
2861 [[0], [1, 2]]
2862 [[0, 1], [2]]
2863 ordered = 0
2864 [[0, 1], [2]]
2865 [[0, 2], [1]]
2866 [[0], [1, 2]]
2867 ordered = 1
2868 [[0], [1, 2]]
2869 [[0], [2, 1]]
2870 [[1], [0, 2]]
2871 [[1], [2, 0]]
2872 [[2], [0, 1]]
2873 [[2], [1, 0]]
2874 ordered = 10
2875 [[0, 1], [2]]
2876 [[2], [0, 1]]
2877 [[0, 2], [1]]
2878 [[1], [0, 2]]
2879 [[0], [1, 2]]
2880 [[1, 2], [0]]
2881 ordered = 11
2882 [[0], [1, 2]]
2883 [[0, 1], [2]]
2884 [[0], [2, 1]]
2885 [[0, 2], [1]]
2886 [[1], [0, 2]]
2887 [[1, 0], [2]]
2888 [[1], [2, 0]]
2889 [[1, 2], [0]]
2890 [[2], [0, 1]]
2891 [[2, 0], [1]]
2892 [[2], [1, 0]]
2893 [[2, 1], [0]]
2895 See Also
2896 ========
2898 partitions, multiset_partitions
2900 """
2901 if ordered is None:
2902 yield from sequence_partitions(l, k)
2903 elif ordered == 11:
2904 for pl in multiset_permutations(l):
2905 pl = list(pl)
2906 yield from sequence_partitions(pl, k)
2907 elif ordered == 00:
2908 yield from multiset_partitions(l, k)
2909 elif ordered == 10:
2910 for p in multiset_partitions(l, k):
2911 for perm in permutations(p):
2912 yield list(perm)
2913 elif ordered == 1:
2914 for kgot, p in partitions(len(l), k, size=True):
2915 if kgot != k:
2916 continue
2917 for li in multiset_permutations(l):
2918 rv = []
2919 i = j = 0
2920 li = list(li)
2921 for size, multiplicity in sorted(p.items()):
2922 for m in range(multiplicity):
2923 j = i + size
2924 rv.append(li[i: j])
2925 i = j
2926 yield rv
2927 else:
2928 raise ValueError(
2929 'ordered must be one of 00, 01, 10 or 11, not %s' % ordered)
2932def permute_signs(t):
2933 """Return iterator in which the signs of non-zero elements
2934 of t are permuted.
2936 Examples
2937 ========
2939 >>> from sympy.utilities.iterables import permute_signs
2940 >>> list(permute_signs((0, 1, 2)))
2941 [(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2)]
2942 """
2943 for signs in product(*[(1, -1)]*(len(t) - t.count(0))):
2944 signs = list(signs)
2945 yield type(t)([i*signs.pop() if i else i for i in t])
2948def signed_permutations(t):
2949 """Return iterator in which the signs of non-zero elements
2950 of t and the order of the elements are permuted.
2952 Examples
2953 ========
2955 >>> from sympy.utilities.iterables import signed_permutations
2956 >>> list(signed_permutations((0, 1, 2)))
2957 [(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2), (0, 2, 1),
2958 (0, -2, 1), (0, 2, -1), (0, -2, -1), (1, 0, 2), (-1, 0, 2),
2959 (1, 0, -2), (-1, 0, -2), (1, 2, 0), (-1, 2, 0), (1, -2, 0),
2960 (-1, -2, 0), (2, 0, 1), (-2, 0, 1), (2, 0, -1), (-2, 0, -1),
2961 (2, 1, 0), (-2, 1, 0), (2, -1, 0), (-2, -1, 0)]
2962 """
2963 return (type(t)(i) for j in permutations(t)
2964 for i in permute_signs(j))
2967def rotations(s, dir=1):
2968 """Return a generator giving the items in s as list where
2969 each subsequent list has the items rotated to the left (default)
2970 or right (``dir=-1``) relative to the previous list.
2972 Examples
2973 ========
2975 >>> from sympy import rotations
2976 >>> list(rotations([1,2,3]))
2977 [[1, 2, 3], [2, 3, 1], [3, 1, 2]]
2978 >>> list(rotations([1,2,3], -1))
2979 [[1, 2, 3], [3, 1, 2], [2, 3, 1]]
2980 """
2981 seq = list(s)
2982 for i in range(len(seq)):
2983 yield seq
2984 seq = rotate_left(seq, dir)
2987def roundrobin(*iterables):
2988 """roundrobin recipe taken from itertools documentation:
2989 https://docs.python.org/3/library/itertools.html#itertools-recipes
2991 roundrobin('ABC', 'D', 'EF') --> A D E B F C
2993 Recipe credited to George Sakkis
2994 """
2995 nexts = cycle(iter(it).__next__ for it in iterables)
2997 pending = len(iterables)
2998 while pending:
2999 try:
3000 for nxt in nexts:
3001 yield nxt()
3002 except StopIteration:
3003 pending -= 1
3004 nexts = cycle(islice(nexts, pending))
3008class NotIterable:
3009 """
3010 Use this as mixin when creating a class which is not supposed to
3011 return true when iterable() is called on its instances because
3012 calling list() on the instance, for example, would result in
3013 an infinite loop.
3014 """
3015 pass
3018def iterable(i, exclude=(str, dict, NotIterable)):
3019 """
3020 Return a boolean indicating whether ``i`` is SymPy iterable.
3021 True also indicates that the iterator is finite, e.g. you can
3022 call list(...) on the instance.
3024 When SymPy is working with iterables, it is almost always assuming
3025 that the iterable is not a string or a mapping, so those are excluded
3026 by default. If you want a pure Python definition, make exclude=None. To
3027 exclude multiple items, pass them as a tuple.
3029 You can also set the _iterable attribute to True or False on your class,
3030 which will override the checks here, including the exclude test.
3032 As a rule of thumb, some SymPy functions use this to check if they should
3033 recursively map over an object. If an object is technically iterable in
3034 the Python sense but does not desire this behavior (e.g., because its
3035 iteration is not finite, or because iteration might induce an unwanted
3036 computation), it should disable it by setting the _iterable attribute to False.
3038 See also: is_sequence
3040 Examples
3041 ========
3043 >>> from sympy.utilities.iterables import iterable
3044 >>> from sympy import Tuple
3045 >>> things = [[1], (1,), set([1]), Tuple(1), (j for j in [1, 2]), {1:2}, '1', 1]
3046 >>> for i in things:
3047 ... print('%s %s' % (iterable(i), type(i)))
3048 True <... 'list'>
3049 True <... 'tuple'>
3050 True <... 'set'>
3051 True <class 'sympy.core.containers.Tuple'>
3052 True <... 'generator'>
3053 False <... 'dict'>
3054 False <... 'str'>
3055 False <... 'int'>
3057 >>> iterable({}, exclude=None)
3058 True
3059 >>> iterable({}, exclude=str)
3060 True
3061 >>> iterable("no", exclude=str)
3062 False
3064 """
3065 if hasattr(i, '_iterable'):
3066 return i._iterable
3067 try:
3068 iter(i)
3069 except TypeError:
3070 return False
3071 if exclude:
3072 return not isinstance(i, exclude)
3073 return True
3076def is_sequence(i, include=None):
3077 """
3078 Return a boolean indicating whether ``i`` is a sequence in the SymPy
3079 sense. If anything that fails the test below should be included as
3080 being a sequence for your application, set 'include' to that object's
3081 type; multiple types should be passed as a tuple of types.
3083 Note: although generators can generate a sequence, they often need special
3084 handling to make sure their elements are captured before the generator is
3085 exhausted, so these are not included by default in the definition of a
3086 sequence.
3088 See also: iterable
3090 Examples
3091 ========
3093 >>> from sympy.utilities.iterables import is_sequence
3094 >>> from types import GeneratorType
3095 >>> is_sequence([])
3096 True
3097 >>> is_sequence(set())
3098 False
3099 >>> is_sequence('abc')
3100 False
3101 >>> is_sequence('abc', include=str)
3102 True
3103 >>> generator = (c for c in 'abc')
3104 >>> is_sequence(generator)
3105 False
3106 >>> is_sequence(generator, include=(str, GeneratorType))
3107 True
3109 """
3110 return (hasattr(i, '__getitem__') and
3111 iterable(i) or
3112 bool(include) and
3113 isinstance(i, include))
3116@deprecated(
3117 """
3118 Using postorder_traversal from the sympy.utilities.iterables submodule is
3119 deprecated.
3121 Instead, use postorder_traversal from the top-level sympy namespace, like
3123 sympy.postorder_traversal
3124 """,
3125 deprecated_since_version="1.10",
3126 active_deprecations_target="deprecated-traversal-functions-moved")
3127def postorder_traversal(node, keys=None):
3128 from sympy.core.traversal import postorder_traversal as _postorder_traversal
3129 return _postorder_traversal(node, keys=keys)
3132@deprecated(
3133 """
3134 Using interactive_traversal from the sympy.utilities.iterables submodule
3135 is deprecated.
3137 Instead, use interactive_traversal from the top-level sympy namespace,
3138 like
3140 sympy.interactive_traversal
3141 """,
3142 deprecated_since_version="1.10",
3143 active_deprecations_target="deprecated-traversal-functions-moved")
3144def interactive_traversal(expr):
3145 from sympy.interactive.traversal import interactive_traversal as _interactive_traversal
3146 return _interactive_traversal(expr)
3149@deprecated(
3150 """
3151 Importing default_sort_key from sympy.utilities.iterables is deprecated.
3152 Use from sympy import default_sort_key instead.
3153 """,
3154 deprecated_since_version="1.10",
3155active_deprecations_target="deprecated-sympy-core-compatibility",
3156)
3157def default_sort_key(*args, **kwargs):
3158 from sympy import default_sort_key as _default_sort_key
3159 return _default_sort_key(*args, **kwargs)
3162@deprecated(
3163 """
3164 Importing default_sort_key from sympy.utilities.iterables is deprecated.
3165 Use from sympy import default_sort_key instead.
3166 """,
3167 deprecated_since_version="1.10",
3168active_deprecations_target="deprecated-sympy-core-compatibility",
3169)
3170def ordered(*args, **kwargs):
3171 from sympy import ordered as _ordered
3172 return _ordered(*args, **kwargs)