iterables.py 86 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052
  1. from collections import defaultdict, OrderedDict
  2. from itertools import (
  3. combinations, combinations_with_replacement, permutations,
  4. product
  5. )
  6. # For backwards compatibility
  7. from itertools import product as cartes # noqa: F401
  8. from operator import gt
  9. # this is the logical location of these functions
  10. from sympy.utilities.enumerative import (
  11. multiset_partitions_taocp, list_visitor, MultisetPartitionTraverser)
  12. from sympy.utilities.misc import as_int
  13. from sympy.utilities.decorator import deprecated
  14. def is_palindromic(s, i=0, j=None):
  15. """return True if the sequence is the same from left to right as it
  16. is from right to left in the whole sequence (default) or in the
  17. Python slice ``s[i: j]``; else False.
  18. Examples
  19. ========
  20. >>> from sympy.utilities.iterables import is_palindromic
  21. >>> is_palindromic([1, 0, 1])
  22. True
  23. >>> is_palindromic('abcbb')
  24. False
  25. >>> is_palindromic('abcbb', 1)
  26. False
  27. Normal Python slicing is performed in place so there is no need to
  28. create a slice of the sequence for testing:
  29. >>> is_palindromic('abcbb', 1, -1)
  30. True
  31. >>> is_palindromic('abcbb', -4, -1)
  32. True
  33. See Also
  34. ========
  35. sympy.ntheory.digits.is_palindromic: tests integers
  36. """
  37. i, j, _ = slice(i, j).indices(len(s))
  38. m = (j - i)//2
  39. # if length is odd, middle element will be ignored
  40. return all(s[i + k] == s[j - 1 - k] for k in range(m))
  41. def flatten(iterable, levels=None, cls=None): # noqa: F811
  42. """
  43. Recursively denest iterable containers.
  44. >>> from sympy.utilities.iterables import flatten
  45. >>> flatten([1, 2, 3])
  46. [1, 2, 3]
  47. >>> flatten([1, 2, [3]])
  48. [1, 2, 3]
  49. >>> flatten([1, [2, 3], [4, 5]])
  50. [1, 2, 3, 4, 5]
  51. >>> flatten([1.0, 2, (1, None)])
  52. [1.0, 2, 1, None]
  53. If you want to denest only a specified number of levels of
  54. nested containers, then set ``levels`` flag to the desired
  55. number of levels::
  56. >>> ls = [[(-2, -1), (1, 2)], [(0, 0)]]
  57. >>> flatten(ls, levels=1)
  58. [(-2, -1), (1, 2), (0, 0)]
  59. If cls argument is specified, it will only flatten instances of that
  60. class, for example:
  61. >>> from sympy.core import Basic, S
  62. >>> class MyOp(Basic):
  63. ... pass
  64. ...
  65. >>> flatten([MyOp(S(1), MyOp(S(2), S(3)))], cls=MyOp)
  66. [1, 2, 3]
  67. adapted from https://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks
  68. """
  69. from sympy.tensor.array import NDimArray
  70. if levels is not None:
  71. if not levels:
  72. return iterable
  73. elif levels > 0:
  74. levels -= 1
  75. else:
  76. raise ValueError(
  77. "expected non-negative number of levels, got %s" % levels)
  78. if cls is None:
  79. reducible = lambda x: is_sequence(x, set)
  80. else:
  81. reducible = lambda x: isinstance(x, cls)
  82. result = []
  83. for el in iterable:
  84. if reducible(el):
  85. if hasattr(el, 'args') and not isinstance(el, NDimArray):
  86. el = el.args
  87. result.extend(flatten(el, levels=levels, cls=cls))
  88. else:
  89. result.append(el)
  90. return result
  91. def unflatten(iter, n=2):
  92. """Group ``iter`` into tuples of length ``n``. Raise an error if
  93. the length of ``iter`` is not a multiple of ``n``.
  94. """
  95. if n < 1 or len(iter) % n:
  96. raise ValueError('iter length is not a multiple of %i' % n)
  97. return list(zip(*(iter[i::n] for i in range(n))))
  98. def reshape(seq, how):
  99. """Reshape the sequence according to the template in ``how``.
  100. Examples
  101. ========
  102. >>> from sympy.utilities import reshape
  103. >>> seq = list(range(1, 9))
  104. >>> reshape(seq, [4]) # lists of 4
  105. [[1, 2, 3, 4], [5, 6, 7, 8]]
  106. >>> reshape(seq, (4,)) # tuples of 4
  107. [(1, 2, 3, 4), (5, 6, 7, 8)]
  108. >>> reshape(seq, (2, 2)) # tuples of 4
  109. [(1, 2, 3, 4), (5, 6, 7, 8)]
  110. >>> reshape(seq, (2, [2])) # (i, i, [i, i])
  111. [(1, 2, [3, 4]), (5, 6, [7, 8])]
  112. >>> reshape(seq, ((2,), [2])) # etc....
  113. [((1, 2), [3, 4]), ((5, 6), [7, 8])]
  114. >>> reshape(seq, (1, [2], 1))
  115. [(1, [2, 3], 4), (5, [6, 7], 8)]
  116. >>> reshape(tuple(seq), ([[1], 1, (2,)],))
  117. (([[1], 2, (3, 4)],), ([[5], 6, (7, 8)],))
  118. >>> reshape(tuple(seq), ([1], 1, (2,)))
  119. (([1], 2, (3, 4)), ([5], 6, (7, 8)))
  120. >>> reshape(list(range(12)), [2, [3], {2}, (1, (3,), 1)])
  121. [[0, 1, [2, 3, 4], {5, 6}, (7, (8, 9, 10), 11)]]
  122. """
  123. m = sum(flatten(how))
  124. n, rem = divmod(len(seq), m)
  125. if m < 0 or rem:
  126. raise ValueError('template must sum to positive number '
  127. 'that divides the length of the sequence')
  128. i = 0
  129. container = type(how)
  130. rv = [None]*n
  131. for k in range(len(rv)):
  132. rv[k] = []
  133. for hi in how:
  134. if isinstance(hi, int):
  135. rv[k].extend(seq[i: i + hi])
  136. i += hi
  137. else:
  138. n = sum(flatten(hi))
  139. hi_type = type(hi)
  140. rv[k].append(hi_type(reshape(seq[i: i + n], hi)[0]))
  141. i += n
  142. rv[k] = container(rv[k])
  143. return type(seq)(rv)
  144. def group(seq, multiple=True):
  145. """
  146. Splits a sequence into a list of lists of equal, adjacent elements.
  147. Examples
  148. ========
  149. >>> from sympy.utilities.iterables import group
  150. >>> group([1, 1, 1, 2, 2, 3])
  151. [[1, 1, 1], [2, 2], [3]]
  152. >>> group([1, 1, 1, 2, 2, 3], multiple=False)
  153. [(1, 3), (2, 2), (3, 1)]
  154. >>> group([1, 1, 3, 2, 2, 1], multiple=False)
  155. [(1, 2), (3, 1), (2, 2), (1, 1)]
  156. See Also
  157. ========
  158. multiset
  159. """
  160. if not seq:
  161. return []
  162. current, groups = [seq[0]], []
  163. for elem in seq[1:]:
  164. if elem == current[-1]:
  165. current.append(elem)
  166. else:
  167. groups.append(current)
  168. current = [elem]
  169. groups.append(current)
  170. if multiple:
  171. return groups
  172. for i, current in enumerate(groups):
  173. groups[i] = (current[0], len(current))
  174. return groups
  175. def _iproduct2(iterable1, iterable2):
  176. '''Cartesian product of two possibly infinite iterables'''
  177. it1 = iter(iterable1)
  178. it2 = iter(iterable2)
  179. elems1 = []
  180. elems2 = []
  181. sentinel = object()
  182. def append(it, elems):
  183. e = next(it, sentinel)
  184. if e is not sentinel:
  185. elems.append(e)
  186. n = 0
  187. append(it1, elems1)
  188. append(it2, elems2)
  189. while n <= len(elems1) + len(elems2):
  190. for m in range(n-len(elems1)+1, len(elems2)):
  191. yield (elems1[n-m], elems2[m])
  192. n += 1
  193. append(it1, elems1)
  194. append(it2, elems2)
  195. def iproduct(*iterables):
  196. '''
  197. Cartesian product of iterables.
  198. Generator of the cartesian product of iterables. This is analogous to
  199. itertools.product except that it works with infinite iterables and will
  200. yield any item from the infinite product eventually.
  201. Examples
  202. ========
  203. >>> from sympy.utilities.iterables import iproduct
  204. >>> sorted(iproduct([1,2], [3,4]))
  205. [(1, 3), (1, 4), (2, 3), (2, 4)]
  206. With an infinite iterator:
  207. >>> from sympy import S
  208. >>> (3,) in iproduct(S.Integers)
  209. True
  210. >>> (3, 4) in iproduct(S.Integers, S.Integers)
  211. True
  212. .. seealso::
  213. `itertools.product <https://docs.python.org/3/library/itertools.html#itertools.product>`_
  214. '''
  215. if len(iterables) == 0:
  216. yield ()
  217. return
  218. elif len(iterables) == 1:
  219. for e in iterables[0]:
  220. yield (e,)
  221. elif len(iterables) == 2:
  222. yield from _iproduct2(*iterables)
  223. else:
  224. first, others = iterables[0], iterables[1:]
  225. for ef, eo in _iproduct2(first, iproduct(*others)):
  226. yield (ef,) + eo
  227. def multiset(seq):
  228. """Return the hashable sequence in multiset form with values being the
  229. multiplicity of the item in the sequence.
  230. Examples
  231. ========
  232. >>> from sympy.utilities.iterables import multiset
  233. >>> multiset('mississippi')
  234. {'i': 4, 'm': 1, 'p': 2, 's': 4}
  235. See Also
  236. ========
  237. group
  238. """
  239. rv = defaultdict(int)
  240. for s in seq:
  241. rv[s] += 1
  242. return dict(rv)
  243. def ibin(n, bits=None, str=False):
  244. """Return a list of length ``bits`` corresponding to the binary value
  245. of ``n`` with small bits to the right (last). If bits is omitted, the
  246. length will be the number required to represent ``n``. If the bits are
  247. desired in reversed order, use the ``[::-1]`` slice of the returned list.
  248. If a sequence of all bits-length lists starting from ``[0, 0,..., 0]``
  249. through ``[1, 1, ..., 1]`` are desired, pass a non-integer for bits, e.g.
  250. ``'all'``.
  251. If the bit *string* is desired pass ``str=True``.
  252. Examples
  253. ========
  254. >>> from sympy.utilities.iterables import ibin
  255. >>> ibin(2)
  256. [1, 0]
  257. >>> ibin(2, 4)
  258. [0, 0, 1, 0]
  259. If all lists corresponding to 0 to 2**n - 1, pass a non-integer
  260. for bits:
  261. >>> bits = 2
  262. >>> for i in ibin(2, 'all'):
  263. ... print(i)
  264. (0, 0)
  265. (0, 1)
  266. (1, 0)
  267. (1, 1)
  268. If a bit string is desired of a given length, use str=True:
  269. >>> n = 123
  270. >>> bits = 10
  271. >>> ibin(n, bits, str=True)
  272. '0001111011'
  273. >>> ibin(n, bits, str=True)[::-1] # small bits left
  274. '1101111000'
  275. >>> list(ibin(3, 'all', str=True))
  276. ['000', '001', '010', '011', '100', '101', '110', '111']
  277. """
  278. if n < 0:
  279. raise ValueError("negative numbers are not allowed")
  280. n = as_int(n)
  281. if bits is None:
  282. bits = 0
  283. else:
  284. try:
  285. bits = as_int(bits)
  286. except ValueError:
  287. bits = -1
  288. else:
  289. if n.bit_length() > bits:
  290. raise ValueError(
  291. "`bits` must be >= {}".format(n.bit_length()))
  292. if not str:
  293. if bits >= 0:
  294. return [1 if i == "1" else 0 for i in bin(n)[2:].rjust(bits, "0")]
  295. else:
  296. return variations(list(range(2)), n, repetition=True)
  297. else:
  298. if bits >= 0:
  299. return bin(n)[2:].rjust(bits, "0")
  300. else:
  301. return (bin(i)[2:].rjust(n, "0") for i in range(2**n))
  302. def variations(seq, n, repetition=False):
  303. r"""Returns a generator of the n-sized variations of ``seq`` (size N).
  304. ``repetition`` controls whether items in ``seq`` can appear more than once;
  305. Examples
  306. ========
  307. ``variations(seq, n)`` will return `\frac{N!}{(N - n)!}` permutations without
  308. repetition of ``seq``'s elements:
  309. >>> from sympy.utilities.iterables import variations
  310. >>> list(variations([1, 2], 2))
  311. [(1, 2), (2, 1)]
  312. ``variations(seq, n, True)`` will return the `N^n` permutations obtained
  313. by allowing repetition of elements:
  314. >>> list(variations([1, 2], 2, repetition=True))
  315. [(1, 1), (1, 2), (2, 1), (2, 2)]
  316. If you ask for more items than are in the set you get the empty set unless
  317. you allow repetitions:
  318. >>> list(variations([0, 1], 3, repetition=False))
  319. []
  320. >>> list(variations([0, 1], 3, repetition=True))[:4]
  321. [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1)]
  322. .. seealso::
  323. `itertools.permutations <https://docs.python.org/3/library/itertools.html#itertools.permutations>`_,
  324. `itertools.product <https://docs.python.org/3/library/itertools.html#itertools.product>`_
  325. """
  326. if not repetition:
  327. seq = tuple(seq)
  328. if len(seq) < n:
  329. return
  330. yield from permutations(seq, n)
  331. else:
  332. if n == 0:
  333. yield ()
  334. else:
  335. yield from product(seq, repeat=n)
  336. def subsets(seq, k=None, repetition=False):
  337. r"""Generates all `k`-subsets (combinations) from an `n`-element set, ``seq``.
  338. A `k`-subset of an `n`-element set is any subset of length exactly `k`. The
  339. number of `k`-subsets of an `n`-element set is given by ``binomial(n, k)``,
  340. whereas there are `2^n` subsets all together. If `k` is ``None`` then all
  341. `2^n` subsets will be returned from shortest to longest.
  342. Examples
  343. ========
  344. >>> from sympy.utilities.iterables import subsets
  345. ``subsets(seq, k)`` will return the `\frac{n!}{k!(n - k)!}` `k`-subsets (combinations)
  346. without repetition, i.e. once an item has been removed, it can no
  347. longer be "taken":
  348. >>> list(subsets([1, 2], 2))
  349. [(1, 2)]
  350. >>> list(subsets([1, 2]))
  351. [(), (1,), (2,), (1, 2)]
  352. >>> list(subsets([1, 2, 3], 2))
  353. [(1, 2), (1, 3), (2, 3)]
  354. ``subsets(seq, k, repetition=True)`` will return the `\frac{(n - 1 + k)!}{k!(n - 1)!}`
  355. combinations *with* repetition:
  356. >>> list(subsets([1, 2], 2, repetition=True))
  357. [(1, 1), (1, 2), (2, 2)]
  358. If you ask for more items than are in the set you get the empty set unless
  359. you allow repetitions:
  360. >>> list(subsets([0, 1], 3, repetition=False))
  361. []
  362. >>> list(subsets([0, 1], 3, repetition=True))
  363. [(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)]
  364. """
  365. if k is None:
  366. for k in range(len(seq) + 1):
  367. yield from subsets(seq, k, repetition)
  368. else:
  369. if not repetition:
  370. yield from combinations(seq, k)
  371. else:
  372. yield from combinations_with_replacement(seq, k)
  373. def filter_symbols(iterator, exclude):
  374. """
  375. Only yield elements from `iterator` that do not occur in `exclude`.
  376. Parameters
  377. ==========
  378. iterator : iterable
  379. iterator to take elements from
  380. exclude : iterable
  381. elements to exclude
  382. Returns
  383. =======
  384. iterator : iterator
  385. filtered iterator
  386. """
  387. exclude = set(exclude)
  388. for s in iterator:
  389. if s not in exclude:
  390. yield s
  391. def numbered_symbols(prefix='x', cls=None, start=0, exclude=(), *args, **assumptions):
  392. """
  393. Generate an infinite stream of Symbols consisting of a prefix and
  394. increasing subscripts provided that they do not occur in ``exclude``.
  395. Parameters
  396. ==========
  397. prefix : str, optional
  398. The prefix to use. By default, this function will generate symbols of
  399. the form "x0", "x1", etc.
  400. cls : class, optional
  401. The class to use. By default, it uses ``Symbol``, but you can also use ``Wild`` or ``Dummy``.
  402. start : int, optional
  403. The start number. By default, it is 0.
  404. Returns
  405. =======
  406. sym : Symbol
  407. The subscripted symbols.
  408. """
  409. exclude = set(exclude or [])
  410. if cls is None:
  411. # We can't just make the default cls=Symbol because it isn't
  412. # imported yet.
  413. from sympy.core import Symbol
  414. cls = Symbol
  415. while True:
  416. name = '%s%s' % (prefix, start)
  417. s = cls(name, *args, **assumptions)
  418. if s not in exclude:
  419. yield s
  420. start += 1
  421. def capture(func):
  422. """Return the printed output of func().
  423. ``func`` should be a function without arguments that produces output with
  424. print statements.
  425. >>> from sympy.utilities.iterables import capture
  426. >>> from sympy import pprint
  427. >>> from sympy.abc import x
  428. >>> def foo():
  429. ... print('hello world!')
  430. ...
  431. >>> 'hello' in capture(foo) # foo, not foo()
  432. True
  433. >>> capture(lambda: pprint(2/x))
  434. '2\\n-\\nx\\n'
  435. """
  436. from io import StringIO
  437. import sys
  438. stdout = sys.stdout
  439. sys.stdout = file = StringIO()
  440. try:
  441. func()
  442. finally:
  443. sys.stdout = stdout
  444. return file.getvalue()
  445. def sift(seq, keyfunc, binary=False):
  446. """
  447. Sift the sequence, ``seq`` according to ``keyfunc``.
  448. Returns
  449. =======
  450. When ``binary`` is ``False`` (default), the output is a dictionary
  451. where elements of ``seq`` are stored in a list keyed to the value
  452. of keyfunc for that element. If ``binary`` is True then a tuple
  453. with lists ``T`` and ``F`` are returned where ``T`` is a list
  454. containing elements of seq for which ``keyfunc`` was ``True`` and
  455. ``F`` containing those elements for which ``keyfunc`` was ``False``;
  456. a ValueError is raised if the ``keyfunc`` is not binary.
  457. Examples
  458. ========
  459. >>> from sympy.utilities import sift
  460. >>> from sympy.abc import x, y
  461. >>> from sympy import sqrt, exp, pi, Tuple
  462. >>> sift(range(5), lambda x: x % 2)
  463. {0: [0, 2, 4], 1: [1, 3]}
  464. sift() returns a defaultdict() object, so any key that has no matches will
  465. give [].
  466. >>> sift([x], lambda x: x.is_commutative)
  467. {True: [x]}
  468. >>> _[False]
  469. []
  470. Sometimes you will not know how many keys you will get:
  471. >>> sift([sqrt(x), exp(x), (y**x)**2],
  472. ... lambda x: x.as_base_exp()[0])
  473. {E: [exp(x)], x: [sqrt(x)], y: [y**(2*x)]}
  474. Sometimes you expect the results to be binary; the
  475. results can be unpacked by setting ``binary`` to True:
  476. >>> sift(range(4), lambda x: x % 2, binary=True)
  477. ([1, 3], [0, 2])
  478. >>> sift(Tuple(1, pi), lambda x: x.is_rational, binary=True)
  479. ([1], [pi])
  480. A ValueError is raised if the predicate was not actually binary
  481. (which is a good test for the logic where sifting is used and
  482. binary results were expected):
  483. >>> unknown = exp(1) - pi # the rationality of this is unknown
  484. >>> args = Tuple(1, pi, unknown)
  485. >>> sift(args, lambda x: x.is_rational, binary=True)
  486. Traceback (most recent call last):
  487. ...
  488. ValueError: keyfunc gave non-binary output
  489. The non-binary sifting shows that there were 3 keys generated:
  490. >>> set(sift(args, lambda x: x.is_rational).keys())
  491. {None, False, True}
  492. If you need to sort the sifted items it might be better to use
  493. ``ordered`` which can economically apply multiple sort keys
  494. to a sequence while sorting.
  495. See Also
  496. ========
  497. ordered
  498. """
  499. if not binary:
  500. m = defaultdict(list)
  501. for i in seq:
  502. m[keyfunc(i)].append(i)
  503. return m
  504. sift = F, T = [], []
  505. for i in seq:
  506. try:
  507. sift[keyfunc(i)].append(i)
  508. except (IndexError, TypeError):
  509. raise ValueError('keyfunc gave non-binary output')
  510. return T, F
  511. def take(iter, n):
  512. """Return ``n`` items from ``iter`` iterator. """
  513. return [ value for _, value in zip(range(n), iter) ]
  514. def dict_merge(*dicts):
  515. """Merge dictionaries into a single dictionary. """
  516. merged = {}
  517. for dict in dicts:
  518. merged.update(dict)
  519. return merged
  520. def common_prefix(*seqs):
  521. """Return the subsequence that is a common start of sequences in ``seqs``.
  522. >>> from sympy.utilities.iterables import common_prefix
  523. >>> common_prefix(list(range(3)))
  524. [0, 1, 2]
  525. >>> common_prefix(list(range(3)), list(range(4)))
  526. [0, 1, 2]
  527. >>> common_prefix([1, 2, 3], [1, 2, 5])
  528. [1, 2]
  529. >>> common_prefix([1, 2, 3], [1, 3, 5])
  530. [1]
  531. """
  532. if not all(seqs):
  533. return []
  534. elif len(seqs) == 1:
  535. return seqs[0]
  536. i = 0
  537. for i in range(min(len(s) for s in seqs)):
  538. if not all(seqs[j][i] == seqs[0][i] for j in range(len(seqs))):
  539. break
  540. else:
  541. i += 1
  542. return seqs[0][:i]
  543. def common_suffix(*seqs):
  544. """Return the subsequence that is a common ending of sequences in ``seqs``.
  545. >>> from sympy.utilities.iterables import common_suffix
  546. >>> common_suffix(list(range(3)))
  547. [0, 1, 2]
  548. >>> common_suffix(list(range(3)), list(range(4)))
  549. []
  550. >>> common_suffix([1, 2, 3], [9, 2, 3])
  551. [2, 3]
  552. >>> common_suffix([1, 2, 3], [9, 7, 3])
  553. [3]
  554. """
  555. if not all(seqs):
  556. return []
  557. elif len(seqs) == 1:
  558. return seqs[0]
  559. i = 0
  560. for i in range(-1, -min(len(s) for s in seqs) - 1, -1):
  561. if not all(seqs[j][i] == seqs[0][i] for j in range(len(seqs))):
  562. break
  563. else:
  564. i -= 1
  565. if i == -1:
  566. return []
  567. else:
  568. return seqs[0][i + 1:]
  569. def prefixes(seq):
  570. """
  571. Generate all prefixes of a sequence.
  572. Examples
  573. ========
  574. >>> from sympy.utilities.iterables import prefixes
  575. >>> list(prefixes([1,2,3,4]))
  576. [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
  577. """
  578. n = len(seq)
  579. for i in range(n):
  580. yield seq[:i + 1]
  581. def postfixes(seq):
  582. """
  583. Generate all postfixes of a sequence.
  584. Examples
  585. ========
  586. >>> from sympy.utilities.iterables import postfixes
  587. >>> list(postfixes([1,2,3,4]))
  588. [[4], [3, 4], [2, 3, 4], [1, 2, 3, 4]]
  589. """
  590. n = len(seq)
  591. for i in range(n):
  592. yield seq[n - i - 1:]
  593. def topological_sort(graph, key=None):
  594. r"""
  595. Topological sort of graph's vertices.
  596. Parameters
  597. ==========
  598. graph : tuple[list, list[tuple[T, T]]
  599. A tuple consisting of a list of vertices and a list of edges of
  600. a graph to be sorted topologically.
  601. key : callable[T] (optional)
  602. Ordering key for vertices on the same level. By default the natural
  603. (e.g. lexicographic) ordering is used (in this case the base type
  604. must implement ordering relations).
  605. Examples
  606. ========
  607. Consider a graph::
  608. +---+ +---+ +---+
  609. | 7 |\ | 5 | | 3 |
  610. +---+ \ +---+ +---+
  611. | _\___/ ____ _/ |
  612. | / \___/ \ / |
  613. V V V V |
  614. +----+ +---+ |
  615. | 11 | | 8 | |
  616. +----+ +---+ |
  617. | | \____ ___/ _ |
  618. | \ \ / / \ |
  619. V \ V V / V V
  620. +---+ \ +---+ | +----+
  621. | 2 | | | 9 | | | 10 |
  622. +---+ | +---+ | +----+
  623. \________/
  624. where vertices are integers. This graph can be encoded using
  625. elementary Python's data structures as follows::
  626. >>> V = [2, 3, 5, 7, 8, 9, 10, 11]
  627. >>> E = [(7, 11), (7, 8), (5, 11), (3, 8), (3, 10),
  628. ... (11, 2), (11, 9), (11, 10), (8, 9)]
  629. To compute a topological sort for graph ``(V, E)`` issue::
  630. >>> from sympy.utilities.iterables import topological_sort
  631. >>> topological_sort((V, E))
  632. [3, 5, 7, 8, 11, 2, 9, 10]
  633. If specific tie breaking approach is needed, use ``key`` parameter::
  634. >>> topological_sort((V, E), key=lambda v: -v)
  635. [7, 5, 11, 3, 10, 8, 9, 2]
  636. Only acyclic graphs can be sorted. If the input graph has a cycle,
  637. then ``ValueError`` will be raised::
  638. >>> topological_sort((V, E + [(10, 7)]))
  639. Traceback (most recent call last):
  640. ...
  641. ValueError: cycle detected
  642. References
  643. ==========
  644. .. [1] https://en.wikipedia.org/wiki/Topological_sorting
  645. """
  646. V, E = graph
  647. L = []
  648. S = set(V)
  649. E = list(E)
  650. for v, u in E:
  651. S.discard(u)
  652. if key is None:
  653. key = lambda value: value
  654. S = sorted(S, key=key, reverse=True)
  655. while S:
  656. node = S.pop()
  657. L.append(node)
  658. for u, v in list(E):
  659. if u == node:
  660. E.remove((u, v))
  661. for _u, _v in E:
  662. if v == _v:
  663. break
  664. else:
  665. kv = key(v)
  666. for i, s in enumerate(S):
  667. ks = key(s)
  668. if kv > ks:
  669. S.insert(i, v)
  670. break
  671. else:
  672. S.append(v)
  673. if E:
  674. raise ValueError("cycle detected")
  675. else:
  676. return L
  677. def strongly_connected_components(G):
  678. r"""
  679. Strongly connected components of a directed graph in reverse topological
  680. order.
  681. Parameters
  682. ==========
  683. graph : tuple[list, list[tuple[T, T]]
  684. A tuple consisting of a list of vertices and a list of edges of
  685. a graph whose strongly connected components are to be found.
  686. Examples
  687. ========
  688. Consider a directed graph (in dot notation)::
  689. digraph {
  690. A -> B
  691. A -> C
  692. B -> C
  693. C -> B
  694. B -> D
  695. }
  696. .. graphviz::
  697. digraph {
  698. A -> B
  699. A -> C
  700. B -> C
  701. C -> B
  702. B -> D
  703. }
  704. where vertices are the letters A, B, C and D. This graph can be encoded
  705. using Python's elementary data structures as follows::
  706. >>> V = ['A', 'B', 'C', 'D']
  707. >>> E = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'B'), ('B', 'D')]
  708. The strongly connected components of this graph can be computed as
  709. >>> from sympy.utilities.iterables import strongly_connected_components
  710. >>> strongly_connected_components((V, E))
  711. [['D'], ['B', 'C'], ['A']]
  712. This also gives the components in reverse topological order.
  713. Since the subgraph containing B and C has a cycle they must be together in
  714. a strongly connected component. A and D are connected to the rest of the
  715. graph but not in a cyclic manner so they appear as their own strongly
  716. connected components.
  717. Notes
  718. =====
  719. The vertices of the graph must be hashable for the data structures used.
  720. If the vertices are unhashable replace them with integer indices.
  721. This function uses Tarjan's algorithm to compute the strongly connected
  722. components in `O(|V|+|E|)` (linear) time.
  723. References
  724. ==========
  725. .. [1] https://en.wikipedia.org/wiki/Strongly_connected_component
  726. .. [2] https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
  727. See Also
  728. ========
  729. sympy.utilities.iterables.connected_components
  730. """
  731. # Map from a vertex to its neighbours
  732. V, E = G
  733. Gmap = {vi: [] for vi in V}
  734. for v1, v2 in E:
  735. Gmap[v1].append(v2)
  736. return _strongly_connected_components(V, Gmap)
  737. def _strongly_connected_components(V, Gmap):
  738. """More efficient internal routine for strongly_connected_components"""
  739. #
  740. # Here V is an iterable of vertices and Gmap is a dict mapping each vertex
  741. # to a list of neighbours e.g.:
  742. #
  743. # V = [0, 1, 2, 3]
  744. # Gmap = {0: [2, 3], 1: [0]}
  745. #
  746. # For a large graph these data structures can often be created more
  747. # efficiently then those expected by strongly_connected_components() which
  748. # in this case would be
  749. #
  750. # V = [0, 1, 2, 3]
  751. # Gmap = [(0, 2), (0, 3), (1, 0)]
  752. #
  753. # XXX: Maybe this should be the recommended function to use instead...
  754. #
  755. # Non-recursive Tarjan's algorithm:
  756. lowlink = {}
  757. indices = {}
  758. stack = OrderedDict()
  759. callstack = []
  760. components = []
  761. nomore = object()
  762. def start(v):
  763. index = len(stack)
  764. indices[v] = lowlink[v] = index
  765. stack[v] = None
  766. callstack.append((v, iter(Gmap[v])))
  767. def finish(v1):
  768. # Finished a component?
  769. if lowlink[v1] == indices[v1]:
  770. component = [stack.popitem()[0]]
  771. while component[-1] is not v1:
  772. component.append(stack.popitem()[0])
  773. components.append(component[::-1])
  774. v2, _ = callstack.pop()
  775. if callstack:
  776. v1, _ = callstack[-1]
  777. lowlink[v1] = min(lowlink[v1], lowlink[v2])
  778. for v in V:
  779. if v in indices:
  780. continue
  781. start(v)
  782. while callstack:
  783. v1, it1 = callstack[-1]
  784. v2 = next(it1, nomore)
  785. # Finished children of v1?
  786. if v2 is nomore:
  787. finish(v1)
  788. # Recurse on v2
  789. elif v2 not in indices:
  790. start(v2)
  791. elif v2 in stack:
  792. lowlink[v1] = min(lowlink[v1], indices[v2])
  793. # Reverse topological sort order:
  794. return components
  795. def connected_components(G):
  796. r"""
  797. Connected components of an undirected graph or weakly connected components
  798. of a directed graph.
  799. Parameters
  800. ==========
  801. graph : tuple[list, list[tuple[T, T]]
  802. A tuple consisting of a list of vertices and a list of edges of
  803. a graph whose connected components are to be found.
  804. Examples
  805. ========
  806. Given an undirected graph::
  807. graph {
  808. A -- B
  809. C -- D
  810. }
  811. .. graphviz::
  812. graph {
  813. A -- B
  814. C -- D
  815. }
  816. We can find the connected components using this function if we include
  817. each edge in both directions::
  818. >>> from sympy.utilities.iterables import connected_components
  819. >>> V = ['A', 'B', 'C', 'D']
  820. >>> E = [('A', 'B'), ('B', 'A'), ('C', 'D'), ('D', 'C')]
  821. >>> connected_components((V, E))
  822. [['A', 'B'], ['C', 'D']]
  823. The weakly connected components of a directed graph can found the same
  824. way.
  825. Notes
  826. =====
  827. The vertices of the graph must be hashable for the data structures used.
  828. If the vertices are unhashable replace them with integer indices.
  829. This function uses Tarjan's algorithm to compute the connected components
  830. in `O(|V|+|E|)` (linear) time.
  831. References
  832. ==========
  833. .. [1] https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
  834. .. [2] https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
  835. See Also
  836. ========
  837. sympy.utilities.iterables.strongly_connected_components
  838. """
  839. # Duplicate edges both ways so that the graph is effectively undirected
  840. # and return the strongly connected components:
  841. V, E = G
  842. E_undirected = []
  843. for v1, v2 in E:
  844. E_undirected.extend([(v1, v2), (v2, v1)])
  845. return strongly_connected_components((V, E_undirected))
  846. def rotate_left(x, y):
  847. """
  848. Left rotates a list x by the number of steps specified
  849. in y.
  850. Examples
  851. ========
  852. >>> from sympy.utilities.iterables import rotate_left
  853. >>> a = [0, 1, 2]
  854. >>> rotate_left(a, 1)
  855. [1, 2, 0]
  856. """
  857. if len(x) == 0:
  858. return []
  859. y = y % len(x)
  860. return x[y:] + x[:y]
  861. def rotate_right(x, y):
  862. """
  863. Right rotates a list x by the number of steps specified
  864. in y.
  865. Examples
  866. ========
  867. >>> from sympy.utilities.iterables import rotate_right
  868. >>> a = [0, 1, 2]
  869. >>> rotate_right(a, 1)
  870. [2, 0, 1]
  871. """
  872. if len(x) == 0:
  873. return []
  874. y = len(x) - y % len(x)
  875. return x[y:] + x[:y]
  876. def least_rotation(x, key=None):
  877. '''
  878. Returns the number of steps of left rotation required to
  879. obtain lexicographically minimal string/list/tuple, etc.
  880. Examples
  881. ========
  882. >>> from sympy.utilities.iterables import least_rotation, rotate_left
  883. >>> a = [3, 1, 5, 1, 2]
  884. >>> least_rotation(a)
  885. 3
  886. >>> rotate_left(a, _)
  887. [1, 2, 3, 1, 5]
  888. References
  889. ==========
  890. .. [1] https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
  891. '''
  892. from sympy.functions.elementary.miscellaneous import Id
  893. if key is None: key = Id
  894. S = x + x # Concatenate string to it self to avoid modular arithmetic
  895. f = [-1] * len(S) # Failure function
  896. k = 0 # Least rotation of string found so far
  897. for j in range(1,len(S)):
  898. sj = S[j]
  899. i = f[j-k-1]
  900. while i != -1 and sj != S[k+i+1]:
  901. if key(sj) < key(S[k+i+1]):
  902. k = j-i-1
  903. i = f[i]
  904. if sj != S[k+i+1]:
  905. if key(sj) < key(S[k]):
  906. k = j
  907. f[j-k] = -1
  908. else:
  909. f[j-k] = i+1
  910. return k
  911. def multiset_combinations(m, n, g=None):
  912. """
  913. Return the unique combinations of size ``n`` from multiset ``m``.
  914. Examples
  915. ========
  916. >>> from sympy.utilities.iterables import multiset_combinations
  917. >>> from itertools import combinations
  918. >>> [''.join(i) for i in multiset_combinations('baby', 3)]
  919. ['abb', 'aby', 'bby']
  920. >>> def count(f, s): return len(list(f(s, 3)))
  921. The number of combinations depends on the number of letters; the
  922. number of unique combinations depends on how the letters are
  923. repeated.
  924. >>> s1 = 'abracadabra'
  925. >>> s2 = 'banana tree'
  926. >>> count(combinations, s1), count(multiset_combinations, s1)
  927. (165, 23)
  928. >>> count(combinations, s2), count(multiset_combinations, s2)
  929. (165, 54)
  930. """
  931. from sympy.core.sorting import ordered
  932. if g is None:
  933. if isinstance(m, dict):
  934. if any(as_int(v) < 0 for v in m.values()):
  935. raise ValueError('counts cannot be negative')
  936. N = sum(m.values())
  937. if n > N:
  938. return
  939. g = [[k, m[k]] for k in ordered(m)]
  940. else:
  941. m = list(m)
  942. N = len(m)
  943. if n > N:
  944. return
  945. try:
  946. m = multiset(m)
  947. g = [(k, m[k]) for k in ordered(m)]
  948. except TypeError:
  949. m = list(ordered(m))
  950. g = [list(i) for i in group(m, multiple=False)]
  951. del m
  952. else:
  953. # not checking counts since g is intended for internal use
  954. N = sum(v for k, v in g)
  955. if n > N or not n:
  956. yield []
  957. else:
  958. for i, (k, v) in enumerate(g):
  959. if v >= n:
  960. yield [k]*n
  961. v = n - 1
  962. for v in range(min(n, v), 0, -1):
  963. for j in multiset_combinations(None, n - v, g[i + 1:]):
  964. rv = [k]*v + j
  965. if len(rv) == n:
  966. yield rv
  967. def multiset_permutations(m, size=None, g=None):
  968. """
  969. Return the unique permutations of multiset ``m``.
  970. Examples
  971. ========
  972. >>> from sympy.utilities.iterables import multiset_permutations
  973. >>> from sympy import factorial
  974. >>> [''.join(i) for i in multiset_permutations('aab')]
  975. ['aab', 'aba', 'baa']
  976. >>> factorial(len('banana'))
  977. 720
  978. >>> len(list(multiset_permutations('banana')))
  979. 60
  980. """
  981. from sympy.core.sorting import ordered
  982. if g is None:
  983. if isinstance(m, dict):
  984. if any(as_int(v) < 0 for v in m.values()):
  985. raise ValueError('counts cannot be negative')
  986. g = [[k, m[k]] for k in ordered(m)]
  987. else:
  988. m = list(ordered(m))
  989. g = [list(i) for i in group(m, multiple=False)]
  990. del m
  991. do = [gi for gi in g if gi[1] > 0]
  992. SUM = sum([gi[1] for gi in do])
  993. if not do or size is not None and (size > SUM or size < 1):
  994. if not do and size is None or size == 0:
  995. yield []
  996. return
  997. elif size == 1:
  998. for k, v in do:
  999. yield [k]
  1000. elif len(do) == 1:
  1001. k, v = do[0]
  1002. v = v if size is None else (size if size <= v else 0)
  1003. yield [k for i in range(v)]
  1004. elif all(v == 1 for k, v in do):
  1005. for p in permutations([k for k, v in do], size):
  1006. yield list(p)
  1007. else:
  1008. size = size if size is not None else SUM
  1009. for i, (k, v) in enumerate(do):
  1010. do[i][1] -= 1
  1011. for j in multiset_permutations(None, size - 1, do):
  1012. if j:
  1013. yield [k] + j
  1014. do[i][1] += 1
  1015. def _partition(seq, vector, m=None):
  1016. """
  1017. Return the partition of seq as specified by the partition vector.
  1018. Examples
  1019. ========
  1020. >>> from sympy.utilities.iterables import _partition
  1021. >>> _partition('abcde', [1, 0, 1, 2, 0])
  1022. [['b', 'e'], ['a', 'c'], ['d']]
  1023. Specifying the number of bins in the partition is optional:
  1024. >>> _partition('abcde', [1, 0, 1, 2, 0], 3)
  1025. [['b', 'e'], ['a', 'c'], ['d']]
  1026. The output of _set_partitions can be passed as follows:
  1027. >>> output = (3, [1, 0, 1, 2, 0])
  1028. >>> _partition('abcde', *output)
  1029. [['b', 'e'], ['a', 'c'], ['d']]
  1030. See Also
  1031. ========
  1032. combinatorics.partitions.Partition.from_rgs
  1033. """
  1034. if m is None:
  1035. m = max(vector) + 1
  1036. elif isinstance(vector, int): # entered as m, vector
  1037. vector, m = m, vector
  1038. p = [[] for i in range(m)]
  1039. for i, v in enumerate(vector):
  1040. p[v].append(seq[i])
  1041. return p
  1042. def _set_partitions(n):
  1043. """Cycle through all partions of n elements, yielding the
  1044. current number of partitions, ``m``, and a mutable list, ``q``
  1045. such that element[i] is in part q[i] of the partition.
  1046. NOTE: ``q`` is modified in place and generally should not be changed
  1047. between function calls.
  1048. Examples
  1049. ========
  1050. >>> from sympy.utilities.iterables import _set_partitions, _partition
  1051. >>> for m, q in _set_partitions(3):
  1052. ... print('%s %s %s' % (m, q, _partition('abc', q, m)))
  1053. 1 [0, 0, 0] [['a', 'b', 'c']]
  1054. 2 [0, 0, 1] [['a', 'b'], ['c']]
  1055. 2 [0, 1, 0] [['a', 'c'], ['b']]
  1056. 2 [0, 1, 1] [['a'], ['b', 'c']]
  1057. 3 [0, 1, 2] [['a'], ['b'], ['c']]
  1058. Notes
  1059. =====
  1060. This algorithm is similar to, and solves the same problem as,
  1061. Algorithm 7.2.1.5H, from volume 4A of Knuth's The Art of Computer
  1062. Programming. Knuth uses the term "restricted growth string" where
  1063. this code refers to a "partition vector". In each case, the meaning is
  1064. the same: the value in the ith element of the vector specifies to
  1065. which part the ith set element is to be assigned.
  1066. At the lowest level, this code implements an n-digit big-endian
  1067. counter (stored in the array q) which is incremented (with carries) to
  1068. get the next partition in the sequence. A special twist is that a
  1069. digit is constrained to be at most one greater than the maximum of all
  1070. the digits to the left of it. The array p maintains this maximum, so
  1071. that the code can efficiently decide when a digit can be incremented
  1072. in place or whether it needs to be reset to 0 and trigger a carry to
  1073. the next digit. The enumeration starts with all the digits 0 (which
  1074. corresponds to all the set elements being assigned to the same 0th
  1075. part), and ends with 0123...n, which corresponds to each set element
  1076. being assigned to a different, singleton, part.
  1077. This routine was rewritten to use 0-based lists while trying to
  1078. preserve the beauty and efficiency of the original algorithm.
  1079. References
  1080. ==========
  1081. .. [1] Nijenhuis, Albert and Wilf, Herbert. (1978) Combinatorial Algorithms,
  1082. 2nd Ed, p 91, algorithm "nexequ". Available online from
  1083. https://www.math.upenn.edu/~wilf/website/CombAlgDownld.html (viewed
  1084. November 17, 2012).
  1085. """
  1086. p = [0]*n
  1087. q = [0]*n
  1088. nc = 1
  1089. yield nc, q
  1090. while nc != n:
  1091. m = n
  1092. while 1:
  1093. m -= 1
  1094. i = q[m]
  1095. if p[i] != 1:
  1096. break
  1097. q[m] = 0
  1098. i += 1
  1099. q[m] = i
  1100. m += 1
  1101. nc += m - n
  1102. p[0] += n - m
  1103. if i == nc:
  1104. p[nc] = 0
  1105. nc += 1
  1106. p[i - 1] -= 1
  1107. p[i] += 1
  1108. yield nc, q
  1109. def multiset_partitions(multiset, m=None):
  1110. """
  1111. Return unique partitions of the given multiset (in list form).
  1112. If ``m`` is None, all multisets will be returned, otherwise only
  1113. partitions with ``m`` parts will be returned.
  1114. If ``multiset`` is an integer, a range [0, 1, ..., multiset - 1]
  1115. will be supplied.
  1116. Examples
  1117. ========
  1118. >>> from sympy.utilities.iterables import multiset_partitions
  1119. >>> list(multiset_partitions([1, 2, 3, 4], 2))
  1120. [[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 2], [3, 4]],
  1121. [[1, 3, 4], [2]], [[1, 3], [2, 4]], [[1, 4], [2, 3]],
  1122. [[1], [2, 3, 4]]]
  1123. >>> list(multiset_partitions([1, 2, 3, 4], 1))
  1124. [[[1, 2, 3, 4]]]
  1125. Only unique partitions are returned and these will be returned in a
  1126. canonical order regardless of the order of the input:
  1127. >>> a = [1, 2, 2, 1]
  1128. >>> ans = list(multiset_partitions(a, 2))
  1129. >>> a.sort()
  1130. >>> list(multiset_partitions(a, 2)) == ans
  1131. True
  1132. >>> a = range(3, 1, -1)
  1133. >>> (list(multiset_partitions(a)) ==
  1134. ... list(multiset_partitions(sorted(a))))
  1135. True
  1136. If m is omitted then all partitions will be returned:
  1137. >>> list(multiset_partitions([1, 1, 2]))
  1138. [[[1, 1, 2]], [[1, 1], [2]], [[1, 2], [1]], [[1], [1], [2]]]
  1139. >>> list(multiset_partitions([1]*3))
  1140. [[[1, 1, 1]], [[1], [1, 1]], [[1], [1], [1]]]
  1141. Counting
  1142. ========
  1143. The number of partitions of a set is given by the bell number:
  1144. >>> from sympy import bell
  1145. >>> len(list(multiset_partitions(5))) == bell(5) == 52
  1146. True
  1147. The number of partitions of length k from a set of size n is given by the
  1148. Stirling Number of the 2nd kind:
  1149. >>> from sympy.functions.combinatorial.numbers import stirling
  1150. >>> stirling(5, 2) == len(list(multiset_partitions(5, 2))) == 15
  1151. True
  1152. These comments on counting apply to *sets*, not multisets.
  1153. Notes
  1154. =====
  1155. When all the elements are the same in the multiset, the order
  1156. of the returned partitions is determined by the ``partitions``
  1157. routine. If one is counting partitions then it is better to use
  1158. the ``nT`` function.
  1159. See Also
  1160. ========
  1161. partitions
  1162. sympy.combinatorics.partitions.Partition
  1163. sympy.combinatorics.partitions.IntegerPartition
  1164. sympy.functions.combinatorial.numbers.nT
  1165. """
  1166. # This function looks at the supplied input and dispatches to
  1167. # several special-case routines as they apply.
  1168. if isinstance(multiset, int):
  1169. n = multiset
  1170. if m and m > n:
  1171. return
  1172. multiset = list(range(n))
  1173. if m == 1:
  1174. yield [multiset[:]]
  1175. return
  1176. # If m is not None, it can sometimes be faster to use
  1177. # MultisetPartitionTraverser.enum_range() even for inputs
  1178. # which are sets. Since the _set_partitions code is quite
  1179. # fast, this is only advantageous when the overall set
  1180. # partitions outnumber those with the desired number of parts
  1181. # by a large factor. (At least 60.) Such a switch is not
  1182. # currently implemented.
  1183. for nc, q in _set_partitions(n):
  1184. if m is None or nc == m:
  1185. rv = [[] for i in range(nc)]
  1186. for i in range(n):
  1187. rv[q[i]].append(multiset[i])
  1188. yield rv
  1189. return
  1190. if len(multiset) == 1 and isinstance(multiset, str):
  1191. multiset = [multiset]
  1192. if not has_variety(multiset):
  1193. # Only one component, repeated n times. The resulting
  1194. # partitions correspond to partitions of integer n.
  1195. n = len(multiset)
  1196. if m and m > n:
  1197. return
  1198. if m == 1:
  1199. yield [multiset[:]]
  1200. return
  1201. x = multiset[:1]
  1202. for size, p in partitions(n, m, size=True):
  1203. if m is None or size == m:
  1204. rv = []
  1205. for k in sorted(p):
  1206. rv.extend([x*k]*p[k])
  1207. yield rv
  1208. else:
  1209. from sympy.core.sorting import ordered
  1210. multiset = list(ordered(multiset))
  1211. n = len(multiset)
  1212. if m and m > n:
  1213. return
  1214. if m == 1:
  1215. yield [multiset[:]]
  1216. return
  1217. # Split the information of the multiset into two lists -
  1218. # one of the elements themselves, and one (of the same length)
  1219. # giving the number of repeats for the corresponding element.
  1220. elements, multiplicities = zip(*group(multiset, False))
  1221. if len(elements) < len(multiset):
  1222. # General case - multiset with more than one distinct element
  1223. # and at least one element repeated more than once.
  1224. if m:
  1225. mpt = MultisetPartitionTraverser()
  1226. for state in mpt.enum_range(multiplicities, m-1, m):
  1227. yield list_visitor(state, elements)
  1228. else:
  1229. for state in multiset_partitions_taocp(multiplicities):
  1230. yield list_visitor(state, elements)
  1231. else:
  1232. # Set partitions case - no repeated elements. Pretty much
  1233. # same as int argument case above, with same possible, but
  1234. # currently unimplemented optimization for some cases when
  1235. # m is not None
  1236. for nc, q in _set_partitions(n):
  1237. if m is None or nc == m:
  1238. rv = [[] for i in range(nc)]
  1239. for i in range(n):
  1240. rv[q[i]].append(i)
  1241. yield [[multiset[j] for j in i] for i in rv]
  1242. def partitions(n, m=None, k=None, size=False):
  1243. """Generate all partitions of positive integer, n.
  1244. Parameters
  1245. ==========
  1246. m : integer (default gives partitions of all sizes)
  1247. limits number of parts in partition (mnemonic: m, maximum parts)
  1248. k : integer (default gives partitions number from 1 through n)
  1249. limits the numbers that are kept in the partition (mnemonic: k, keys)
  1250. size : bool (default False, only partition is returned)
  1251. when ``True`` then (M, P) is returned where M is the sum of the
  1252. multiplicities and P is the generated partition.
  1253. Each partition is represented as a dictionary, mapping an integer
  1254. to the number of copies of that integer in the partition. For example,
  1255. the first partition of 4 returned is {4: 1}, "4: one of them".
  1256. Examples
  1257. ========
  1258. >>> from sympy.utilities.iterables import partitions
  1259. The numbers appearing in the partition (the key of the returned dict)
  1260. are limited with k:
  1261. >>> for p in partitions(6, k=2): # doctest: +SKIP
  1262. ... print(p)
  1263. {2: 3}
  1264. {1: 2, 2: 2}
  1265. {1: 4, 2: 1}
  1266. {1: 6}
  1267. The maximum number of parts in the partition (the sum of the values in
  1268. the returned dict) are limited with m (default value, None, gives
  1269. partitions from 1 through n):
  1270. >>> for p in partitions(6, m=2): # doctest: +SKIP
  1271. ... print(p)
  1272. ...
  1273. {6: 1}
  1274. {1: 1, 5: 1}
  1275. {2: 1, 4: 1}
  1276. {3: 2}
  1277. References
  1278. ==========
  1279. .. [1] modified from Tim Peter's version to allow for k and m values:
  1280. http://code.activestate.com/recipes/218332-generator-for-integer-partitions/
  1281. See Also
  1282. ========
  1283. sympy.combinatorics.partitions.Partition
  1284. sympy.combinatorics.partitions.IntegerPartition
  1285. """
  1286. if (n <= 0 or
  1287. m is not None and m < 1 or
  1288. k is not None and k < 1 or
  1289. m and k and m*k < n):
  1290. # the empty set is the only way to handle these inputs
  1291. # and returning {} to represent it is consistent with
  1292. # the counting convention, e.g. nT(0) == 1.
  1293. if size:
  1294. yield 0, {}
  1295. else:
  1296. yield {}
  1297. return
  1298. if m is None:
  1299. m = n
  1300. else:
  1301. m = min(m, n)
  1302. k = min(k or n, n)
  1303. n, m, k = as_int(n), as_int(m), as_int(k)
  1304. q, r = divmod(n, k)
  1305. ms = {k: q}
  1306. keys = [k] # ms.keys(), from largest to smallest
  1307. if r:
  1308. ms[r] = 1
  1309. keys.append(r)
  1310. room = m - q - bool(r)
  1311. if size:
  1312. yield sum(ms.values()), ms.copy()
  1313. else:
  1314. yield ms.copy()
  1315. while keys != [1]:
  1316. # Reuse any 1's.
  1317. if keys[-1] == 1:
  1318. del keys[-1]
  1319. reuse = ms.pop(1)
  1320. room += reuse
  1321. else:
  1322. reuse = 0
  1323. while 1:
  1324. # Let i be the smallest key larger than 1. Reuse one
  1325. # instance of i.
  1326. i = keys[-1]
  1327. newcount = ms[i] = ms[i] - 1
  1328. reuse += i
  1329. if newcount == 0:
  1330. del keys[-1], ms[i]
  1331. room += 1
  1332. # Break the remainder into pieces of size i-1.
  1333. i -= 1
  1334. q, r = divmod(reuse, i)
  1335. need = q + bool(r)
  1336. if need > room:
  1337. if not keys:
  1338. return
  1339. continue
  1340. ms[i] = q
  1341. keys.append(i)
  1342. if r:
  1343. ms[r] = 1
  1344. keys.append(r)
  1345. break
  1346. room -= need
  1347. if size:
  1348. yield sum(ms.values()), ms.copy()
  1349. else:
  1350. yield ms.copy()
  1351. def ordered_partitions(n, m=None, sort=True):
  1352. """Generates ordered partitions of integer ``n``.
  1353. Parameters
  1354. ==========
  1355. m : integer (default None)
  1356. The default value gives partitions of all sizes else only
  1357. those with size m. In addition, if ``m`` is not None then
  1358. partitions are generated *in place* (see examples).
  1359. sort : bool (default True)
  1360. Controls whether partitions are
  1361. returned in sorted order when ``m`` is not None; when False,
  1362. the partitions are returned as fast as possible with elements
  1363. sorted, but when m|n the partitions will not be in
  1364. ascending lexicographical order.
  1365. Examples
  1366. ========
  1367. >>> from sympy.utilities.iterables import ordered_partitions
  1368. All partitions of 5 in ascending lexicographical:
  1369. >>> for p in ordered_partitions(5):
  1370. ... print(p)
  1371. [1, 1, 1, 1, 1]
  1372. [1, 1, 1, 2]
  1373. [1, 1, 3]
  1374. [1, 2, 2]
  1375. [1, 4]
  1376. [2, 3]
  1377. [5]
  1378. Only partitions of 5 with two parts:
  1379. >>> for p in ordered_partitions(5, 2):
  1380. ... print(p)
  1381. [1, 4]
  1382. [2, 3]
  1383. When ``m`` is given, a given list objects will be used more than
  1384. once for speed reasons so you will not see the correct partitions
  1385. unless you make a copy of each as it is generated:
  1386. >>> [p for p in ordered_partitions(7, 3)]
  1387. [[1, 1, 1], [1, 1, 1], [1, 1, 1], [2, 2, 2]]
  1388. >>> [list(p) for p in ordered_partitions(7, 3)]
  1389. [[1, 1, 5], [1, 2, 4], [1, 3, 3], [2, 2, 3]]
  1390. When ``n`` is a multiple of ``m``, the elements are still sorted
  1391. but the partitions themselves will be *unordered* if sort is False;
  1392. the default is to return them in ascending lexicographical order.
  1393. >>> for p in ordered_partitions(6, 2):
  1394. ... print(p)
  1395. [1, 5]
  1396. [2, 4]
  1397. [3, 3]
  1398. But if speed is more important than ordering, sort can be set to
  1399. False:
  1400. >>> for p in ordered_partitions(6, 2, sort=False):
  1401. ... print(p)
  1402. [1, 5]
  1403. [3, 3]
  1404. [2, 4]
  1405. References
  1406. ==========
  1407. .. [1] Generating Integer Partitions, [online],
  1408. Available: https://jeromekelleher.net/generating-integer-partitions.html
  1409. .. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
  1410. Partitions: A Comparison Of Two Encodings", [online],
  1411. Available: https://arxiv.org/pdf/0909.2331v2.pdf
  1412. """
  1413. if n < 1 or m is not None and m < 1:
  1414. # the empty set is the only way to handle these inputs
  1415. # and returning {} to represent it is consistent with
  1416. # the counting convention, e.g. nT(0) == 1.
  1417. yield []
  1418. return
  1419. if m is None:
  1420. # The list `a`'s leading elements contain the partition in which
  1421. # y is the biggest element and x is either the same as y or the
  1422. # 2nd largest element; v and w are adjacent element indices
  1423. # to which x and y are being assigned, respectively.
  1424. a = [1]*n
  1425. y = -1
  1426. v = n
  1427. while v > 0:
  1428. v -= 1
  1429. x = a[v] + 1
  1430. while y >= 2 * x:
  1431. a[v] = x
  1432. y -= x
  1433. v += 1
  1434. w = v + 1
  1435. while x <= y:
  1436. a[v] = x
  1437. a[w] = y
  1438. yield a[:w + 1]
  1439. x += 1
  1440. y -= 1
  1441. a[v] = x + y
  1442. y = a[v] - 1
  1443. yield a[:w]
  1444. elif m == 1:
  1445. yield [n]
  1446. elif n == m:
  1447. yield [1]*n
  1448. else:
  1449. # recursively generate partitions of size m
  1450. for b in range(1, n//m + 1):
  1451. a = [b]*m
  1452. x = n - b*m
  1453. if not x:
  1454. if sort:
  1455. yield a
  1456. elif not sort and x <= m:
  1457. for ax in ordered_partitions(x, sort=False):
  1458. mi = len(ax)
  1459. a[-mi:] = [i + b for i in ax]
  1460. yield a
  1461. a[-mi:] = [b]*mi
  1462. else:
  1463. for mi in range(1, m):
  1464. for ax in ordered_partitions(x, mi, sort=True):
  1465. a[-mi:] = [i + b for i in ax]
  1466. yield a
  1467. a[-mi:] = [b]*mi
  1468. def binary_partitions(n):
  1469. """
  1470. Generates the binary partition of n.
  1471. A binary partition consists only of numbers that are
  1472. powers of two. Each step reduces a `2^{k+1}` to `2^k` and
  1473. `2^k`. Thus 16 is converted to 8 and 8.
  1474. Examples
  1475. ========
  1476. >>> from sympy.utilities.iterables import binary_partitions
  1477. >>> for i in binary_partitions(5):
  1478. ... print(i)
  1479. ...
  1480. [4, 1]
  1481. [2, 2, 1]
  1482. [2, 1, 1, 1]
  1483. [1, 1, 1, 1, 1]
  1484. References
  1485. ==========
  1486. .. [1] TAOCP 4, section 7.2.1.5, problem 64
  1487. """
  1488. from math import ceil, log
  1489. power = int(2**(ceil(log(n, 2))))
  1490. acc = 0
  1491. partition = []
  1492. while power:
  1493. if acc + power <= n:
  1494. partition.append(power)
  1495. acc += power
  1496. power >>= 1
  1497. last_num = len(partition) - 1 - (n & 1)
  1498. while last_num >= 0:
  1499. yield partition
  1500. if partition[last_num] == 2:
  1501. partition[last_num] = 1
  1502. partition.append(1)
  1503. last_num -= 1
  1504. continue
  1505. partition.append(1)
  1506. partition[last_num] >>= 1
  1507. x = partition[last_num + 1] = partition[last_num]
  1508. last_num += 1
  1509. while x > 1:
  1510. if x <= len(partition) - last_num - 1:
  1511. del partition[-x + 1:]
  1512. last_num += 1
  1513. partition[last_num] = x
  1514. else:
  1515. x >>= 1
  1516. yield [1]*n
  1517. def has_dups(seq):
  1518. """Return True if there are any duplicate elements in ``seq``.
  1519. Examples
  1520. ========
  1521. >>> from sympy.utilities.iterables import has_dups
  1522. >>> from sympy import Dict, Set
  1523. >>> has_dups((1, 2, 1))
  1524. True
  1525. >>> has_dups(range(3))
  1526. False
  1527. >>> all(has_dups(c) is False for c in (set(), Set(), dict(), Dict()))
  1528. True
  1529. """
  1530. from sympy.core.containers import Dict
  1531. from sympy.sets.sets import Set
  1532. if isinstance(seq, (dict, set, Dict, Set)):
  1533. return False
  1534. unique = set()
  1535. try:
  1536. return any(True for s in seq if s in unique or unique.add(s))
  1537. except TypeError:
  1538. return len(seq) != len(list(uniq(seq)))
  1539. def has_variety(seq):
  1540. """Return True if there are any different elements in ``seq``.
  1541. Examples
  1542. ========
  1543. >>> from sympy.utilities.iterables import has_variety
  1544. >>> has_variety((1, 2, 1))
  1545. True
  1546. >>> has_variety((1, 1, 1))
  1547. False
  1548. """
  1549. for i, s in enumerate(seq):
  1550. if i == 0:
  1551. sentinel = s
  1552. else:
  1553. if s != sentinel:
  1554. return True
  1555. return False
  1556. def uniq(seq, result=None):
  1557. """
  1558. Yield unique elements from ``seq`` as an iterator. The second
  1559. parameter ``result`` is used internally; it is not necessary
  1560. to pass anything for this.
  1561. Note: changing the sequence during iteration will raise a
  1562. RuntimeError if the size of the sequence is known; if you pass
  1563. an iterator and advance the iterator you will change the
  1564. output of this routine but there will be no warning.
  1565. Examples
  1566. ========
  1567. >>> from sympy.utilities.iterables import uniq
  1568. >>> dat = [1, 4, 1, 5, 4, 2, 1, 2]
  1569. >>> type(uniq(dat)) in (list, tuple)
  1570. False
  1571. >>> list(uniq(dat))
  1572. [1, 4, 5, 2]
  1573. >>> list(uniq(x for x in dat))
  1574. [1, 4, 5, 2]
  1575. >>> list(uniq([[1], [2, 1], [1]]))
  1576. [[1], [2, 1]]
  1577. """
  1578. try:
  1579. n = len(seq)
  1580. except TypeError:
  1581. n = None
  1582. def check():
  1583. # check that size of seq did not change during iteration;
  1584. # if n == None the object won't support size changing, e.g.
  1585. # an iterator can't be changed
  1586. if n is not None and len(seq) != n:
  1587. raise RuntimeError('sequence changed size during iteration')
  1588. try:
  1589. seen = set()
  1590. result = result or []
  1591. for i, s in enumerate(seq):
  1592. if not (s in seen or seen.add(s)):
  1593. yield s
  1594. check()
  1595. except TypeError:
  1596. if s not in result:
  1597. yield s
  1598. check()
  1599. result.append(s)
  1600. if hasattr(seq, '__getitem__'):
  1601. yield from uniq(seq[i + 1:], result)
  1602. else:
  1603. yield from uniq(seq, result)
  1604. def generate_bell(n):
  1605. """Return permutations of [0, 1, ..., n - 1] such that each permutation
  1606. differs from the last by the exchange of a single pair of neighbors.
  1607. The ``n!`` permutations are returned as an iterator. In order to obtain
  1608. the next permutation from a random starting permutation, use the
  1609. ``next_trotterjohnson`` method of the Permutation class (which generates
  1610. the same sequence in a different manner).
  1611. Examples
  1612. ========
  1613. >>> from itertools import permutations
  1614. >>> from sympy.utilities.iterables import generate_bell
  1615. >>> from sympy import zeros, Matrix
  1616. This is the sort of permutation used in the ringing of physical bells,
  1617. and does not produce permutations in lexicographical order. Rather, the
  1618. permutations differ from each other by exactly one inversion, and the
  1619. position at which the swapping occurs varies periodically in a simple
  1620. fashion. Consider the first few permutations of 4 elements generated
  1621. by ``permutations`` and ``generate_bell``:
  1622. >>> list(permutations(range(4)))[:5]
  1623. [(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2)]
  1624. >>> list(generate_bell(4))[:5]
  1625. [(0, 1, 2, 3), (0, 1, 3, 2), (0, 3, 1, 2), (3, 0, 1, 2), (3, 0, 2, 1)]
  1626. Notice how the 2nd and 3rd lexicographical permutations have 3 elements
  1627. out of place whereas each "bell" permutation always has only two
  1628. elements out of place relative to the previous permutation (and so the
  1629. signature (+/-1) of a permutation is opposite of the signature of the
  1630. previous permutation).
  1631. How the position of inversion varies across the elements can be seen
  1632. by tracing out where the largest number appears in the permutations:
  1633. >>> m = zeros(4, 24)
  1634. >>> for i, p in enumerate(generate_bell(4)):
  1635. ... m[:, i] = Matrix([j - 3 for j in list(p)]) # make largest zero
  1636. >>> m.print_nonzero('X')
  1637. [XXX XXXXXX XXXXXX XXX]
  1638. [XX XX XXXX XX XXXX XX XX]
  1639. [X XXXX XX XXXX XX XXXX X]
  1640. [ XXXXXX XXXXXX XXXXXX ]
  1641. See Also
  1642. ========
  1643. sympy.combinatorics.permutations.Permutation.next_trotterjohnson
  1644. References
  1645. ==========
  1646. .. [1] https://en.wikipedia.org/wiki/Method_ringing
  1647. .. [2] https://stackoverflow.com/questions/4856615/recursive-permutation/4857018
  1648. .. [3] http://programminggeeks.com/bell-algorithm-for-permutation/
  1649. .. [4] https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm
  1650. .. [5] Generating involutions, derangements, and relatives by ECO
  1651. Vincent Vajnovszki, DMTCS vol 1 issue 12, 2010
  1652. """
  1653. n = as_int(n)
  1654. if n < 1:
  1655. raise ValueError('n must be a positive integer')
  1656. if n == 1:
  1657. yield (0,)
  1658. elif n == 2:
  1659. yield (0, 1)
  1660. yield (1, 0)
  1661. elif n == 3:
  1662. yield from [(0, 1, 2), (0, 2, 1), (2, 0, 1), (2, 1, 0), (1, 2, 0), (1, 0, 2)]
  1663. else:
  1664. m = n - 1
  1665. op = [0] + [-1]*m
  1666. l = list(range(n))
  1667. while True:
  1668. yield tuple(l)
  1669. # find biggest element with op
  1670. big = None, -1 # idx, value
  1671. for i in range(n):
  1672. if op[i] and l[i] > big[1]:
  1673. big = i, l[i]
  1674. i, _ = big
  1675. if i is None:
  1676. break # there are no ops left
  1677. # swap it with neighbor in the indicated direction
  1678. j = i + op[i]
  1679. l[i], l[j] = l[j], l[i]
  1680. op[i], op[j] = op[j], op[i]
  1681. # if it landed at the end or if the neighbor in the same
  1682. # direction is bigger then turn off op
  1683. if j == 0 or j == m or l[j + op[j]] > l[j]:
  1684. op[j] = 0
  1685. # any element bigger to the left gets +1 op
  1686. for i in range(j):
  1687. if l[i] > l[j]:
  1688. op[i] = 1
  1689. # any element bigger to the right gets -1 op
  1690. for i in range(j + 1, n):
  1691. if l[i] > l[j]:
  1692. op[i] = -1
  1693. def generate_involutions(n):
  1694. """
  1695. Generates involutions.
  1696. An involution is a permutation that when multiplied
  1697. by itself equals the identity permutation. In this
  1698. implementation the involutions are generated using
  1699. Fixed Points.
  1700. Alternatively, an involution can be considered as
  1701. a permutation that does not contain any cycles with
  1702. a length that is greater than two.
  1703. Examples
  1704. ========
  1705. >>> from sympy.utilities.iterables import generate_involutions
  1706. >>> list(generate_involutions(3))
  1707. [(0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 1, 0)]
  1708. >>> len(list(generate_involutions(4)))
  1709. 10
  1710. References
  1711. ==========
  1712. .. [1] http://mathworld.wolfram.com/PermutationInvolution.html
  1713. """
  1714. idx = list(range(n))
  1715. for p in permutations(idx):
  1716. for i in idx:
  1717. if p[p[i]] != i:
  1718. break
  1719. else:
  1720. yield p
  1721. def multiset_derangements(s):
  1722. """Generate derangements of the elements of s *in place*.
  1723. Examples
  1724. ========
  1725. >>> from sympy.utilities.iterables import multiset_derangements, uniq
  1726. Because the derangements of multisets (not sets) are generated
  1727. in place, copies of the return value must be made if a collection
  1728. of derangements is desired or else all values will be the same:
  1729. >>> list(uniq([i for i in multiset_derangements('1233')]))
  1730. [[None, None, None, None]]
  1731. >>> [i.copy() for i in multiset_derangements('1233')]
  1732. [['3', '3', '1', '2'], ['3', '3', '2', '1']]
  1733. >>> [''.join(i) for i in multiset_derangements('1233')]
  1734. ['3312', '3321']
  1735. """
  1736. from sympy.core.sorting import ordered
  1737. # create multiset dictionary of hashable elements or else
  1738. # remap elements to integers
  1739. try:
  1740. ms = multiset(s)
  1741. except TypeError:
  1742. # give each element a canonical integer value
  1743. key = dict(enumerate(ordered(uniq(s))))
  1744. h = []
  1745. for si in s:
  1746. for k in key:
  1747. if key[k] == si:
  1748. h.append(k)
  1749. break
  1750. for i in multiset_derangements(h):
  1751. yield [key[j] for j in i]
  1752. return
  1753. mx = max(ms.values()) # max repetition of any element
  1754. n = len(s) # the number of elements
  1755. ## special cases
  1756. # 1) one element has more than half the total cardinality of s: no
  1757. # derangements are possible.
  1758. if mx*2 > n:
  1759. return
  1760. # 2) all elements appear once: singletons
  1761. if len(ms) == n:
  1762. yield from _set_derangements(s)
  1763. return
  1764. # find the first element that is repeated the most to place
  1765. # in the following two special cases where the selection
  1766. # is unambiguous: either there are two elements with multiplicity
  1767. # of mx or else there is only one with multiplicity mx
  1768. for M in ms:
  1769. if ms[M] == mx:
  1770. break
  1771. inonM = [i for i in range(n) if s[i] != M] # location of non-M
  1772. iM = [i for i in range(n) if s[i] == M] # locations of M
  1773. rv = [None]*n
  1774. # 3) half are the same
  1775. if 2*mx == n:
  1776. # M goes into non-M locations
  1777. for i in inonM:
  1778. rv[i] = M
  1779. # permutations of non-M go to M locations
  1780. for p in multiset_permutations([s[i] for i in inonM]):
  1781. for i, pi in zip(iM, p):
  1782. rv[i] = pi
  1783. yield rv
  1784. # clean-up (and encourages proper use of routine)
  1785. rv[:] = [None]*n
  1786. return
  1787. # 4) single repeat covers all but 1 of the non-repeats:
  1788. # if there is one repeat then the multiset of the values
  1789. # of ms would be {mx: 1, 1: n - mx}, i.e. there would
  1790. # be n - mx + 1 values with the condition that n - 2*mx = 1
  1791. if n - 2*mx == 1 and len(ms.values()) == n - mx + 1:
  1792. for i in range(len(inonM)):
  1793. i1 = inonM[i]
  1794. ifill = inonM[:i] + inonM[i+1:]
  1795. for j in ifill:
  1796. rv[j] = M
  1797. for p in permutations([s[j] for j in ifill]):
  1798. rv[i1] = s[i1]
  1799. for j, pi in zip(iM, p):
  1800. rv[j] = pi
  1801. k = i1
  1802. for j in iM:
  1803. rv[j], rv[k] = rv[k], rv[j]
  1804. yield rv
  1805. k = j
  1806. # clean-up (and encourages proper use of routine)
  1807. rv[:] = [None]*n
  1808. return
  1809. ## general case is handled with 3 helpers:
  1810. # 1) `finish_derangements` will place the last two elements
  1811. # which have arbitrary multiplicities, e.g. for multiset
  1812. # {c: 3, a: 2, b: 2}, the last two elements are a and b
  1813. # 2) `iopen` will tell where a given element can be placed
  1814. # 3) `do` will recursively place elements into subsets of
  1815. # valid locations
  1816. def finish_derangements():
  1817. """Place the last two elements into the partially completed
  1818. derangement, and yield the results.
  1819. """
  1820. a = take[1][0] # penultimate element
  1821. a_ct = take[1][1]
  1822. b = take[0][0] # last element to be placed
  1823. b_ct = take[0][1]
  1824. # split the indexes of the not-already-assigned elemements of rv into
  1825. # three categories
  1826. forced_a = [] # positions which must have an a
  1827. forced_b = [] # positions which must have a b
  1828. open_free = [] # positions which could take either
  1829. for i in range(len(s)):
  1830. if rv[i] is None:
  1831. if s[i] == a:
  1832. forced_b.append(i)
  1833. elif s[i] == b:
  1834. forced_a.append(i)
  1835. else:
  1836. open_free.append(i)
  1837. if len(forced_a) > a_ct or len(forced_b) > b_ct:
  1838. # No derangement possible
  1839. return
  1840. for i in forced_a:
  1841. rv[i] = a
  1842. for i in forced_b:
  1843. rv[i] = b
  1844. for a_place in combinations(open_free, a_ct - len(forced_a)):
  1845. for a_pos in a_place:
  1846. rv[a_pos] = a
  1847. for i in open_free:
  1848. if rv[i] is None: # anything not in the subset is set to b
  1849. rv[i] = b
  1850. yield rv
  1851. # Clean up/undo the final placements
  1852. for i in open_free:
  1853. rv[i] = None
  1854. # additional cleanup - clear forced_a, forced_b
  1855. for i in forced_a:
  1856. rv[i] = None
  1857. for i in forced_b:
  1858. rv[i] = None
  1859. def iopen(v):
  1860. # return indices at which element v can be placed in rv:
  1861. # locations which are not already occupied if that location
  1862. # does not already contain v in the same location of s
  1863. return [i for i in range(n) if rv[i] is None and s[i] != v]
  1864. def do(j):
  1865. if j == 1:
  1866. # handle the last two elements (regardless of multiplicity)
  1867. # with a special method
  1868. yield from finish_derangements()
  1869. else:
  1870. # place the mx elements of M into a subset of places
  1871. # into which it can be replaced
  1872. M, mx = take[j]
  1873. for i in combinations(iopen(M), mx):
  1874. # place M
  1875. for ii in i:
  1876. rv[ii] = M
  1877. # recursively place the next element
  1878. yield from do(j - 1)
  1879. # mark positions where M was placed as once again
  1880. # open for placement of other elements
  1881. for ii in i:
  1882. rv[ii] = None
  1883. # process elements in order of canonically decreasing multiplicity
  1884. take = sorted(ms.items(), key=lambda x:(x[1], x[0]))
  1885. yield from do(len(take) - 1)
  1886. rv[:] = [None]*n
  1887. def random_derangement(t, choice=None, strict=True):
  1888. """Return a list of elements in which none are in the same positions
  1889. as they were originally. If an element fills more than half of the positions
  1890. then an error will be raised since no derangement is possible. To obtain
  1891. a derangement of as many items as possible--with some of the most numerous
  1892. remaining in their original positions--pass `strict=False`. To produce a
  1893. pseudorandom derangment, pass a pseudorandom selector like `choice` (see
  1894. below).
  1895. Examples
  1896. ========
  1897. >>> from sympy.utilities.iterables import random_derangement
  1898. >>> t = 'SymPy: a CAS in pure Python'
  1899. >>> d = random_derangement(t)
  1900. >>> all(i != j for i, j in zip(d, t))
  1901. True
  1902. A predictable result can be obtained by using a pseudorandom
  1903. generator for the choice:
  1904. >>> from sympy.core.random import seed, choice as c
  1905. >>> seed(1)
  1906. >>> d = [''.join(random_derangement(t, c)) for i in range(5)]
  1907. >>> assert len(set(d)) != 1 # we got different values
  1908. By reseeding, the same sequence can be obtained:
  1909. >>> seed(1)
  1910. >>> d2 = [''.join(random_derangement(t, c)) for i in range(5)]
  1911. >>> assert d == d2
  1912. """
  1913. if choice is None:
  1914. import secrets
  1915. choice = secrets.choice
  1916. def shuffle(rv):
  1917. '''Knuth shuffle'''
  1918. for i in range(len(rv) - 1, 0, -1):
  1919. x = choice(rv[:i + 1])
  1920. j = rv.index(x)
  1921. rv[i], rv[j] = rv[j], rv[i]
  1922. def pick(rv, n):
  1923. '''shuffle rv and return the first n values
  1924. '''
  1925. shuffle(rv)
  1926. return rv[:n]
  1927. ms = multiset(t)
  1928. tot = len(t)
  1929. ms = sorted(ms.items(), key=lambda x: x[1])
  1930. # if there are not enough spaces for the most
  1931. # plentiful element to move to then some of them
  1932. # will have to stay in place
  1933. M, mx = ms[-1]
  1934. n = len(t)
  1935. xs = 2*mx - tot
  1936. if xs > 0:
  1937. if strict:
  1938. raise ValueError('no derangement possible')
  1939. opts = [i for (i, c) in enumerate(t) if c == ms[-1][0]]
  1940. pick(opts, xs)
  1941. stay = sorted(opts[:xs])
  1942. rv = list(t)
  1943. for i in reversed(stay):
  1944. rv.pop(i)
  1945. rv = random_derangement(rv, choice)
  1946. for i in stay:
  1947. rv.insert(i, ms[-1][0])
  1948. return ''.join(rv) if type(t) is str else rv
  1949. # the normal derangement calculated from here
  1950. if n == len(ms):
  1951. # approx 1/3 will succeed
  1952. rv = list(t)
  1953. while True:
  1954. shuffle(rv)
  1955. if all(i != j for i,j in zip(rv, t)):
  1956. break
  1957. else:
  1958. # general case
  1959. rv = [None]*n
  1960. while True:
  1961. j = 0
  1962. while j > -len(ms): # do most numerous first
  1963. j -= 1
  1964. e, c = ms[j]
  1965. opts = [i for i in range(n) if rv[i] is None and t[i] != e]
  1966. if len(opts) < c:
  1967. for i in range(n):
  1968. rv[i] = None
  1969. break # try again
  1970. pick(opts, c)
  1971. for i in range(c):
  1972. rv[opts[i]] = e
  1973. else:
  1974. return rv
  1975. return rv
  1976. def _set_derangements(s):
  1977. """
  1978. yield derangements of items in ``s`` which are assumed to contain
  1979. no repeated elements
  1980. """
  1981. if len(s) < 2:
  1982. return
  1983. if len(s) == 2:
  1984. yield [s[1], s[0]]
  1985. return
  1986. if len(s) == 3:
  1987. yield [s[1], s[2], s[0]]
  1988. yield [s[2], s[0], s[1]]
  1989. return
  1990. for p in permutations(s):
  1991. if not any(i == j for i, j in zip(p, s)):
  1992. yield list(p)
  1993. def generate_derangements(s):
  1994. """
  1995. Return unique derangements of the elements of iterable ``s``.
  1996. Examples
  1997. ========
  1998. >>> from sympy.utilities.iterables import generate_derangements
  1999. >>> list(generate_derangements([0, 1, 2]))
  2000. [[1, 2, 0], [2, 0, 1]]
  2001. >>> list(generate_derangements([0, 1, 2, 2]))
  2002. [[2, 2, 0, 1], [2, 2, 1, 0]]
  2003. >>> list(generate_derangements([0, 1, 1]))
  2004. []
  2005. See Also
  2006. ========
  2007. sympy.functions.combinatorial.factorials.subfactorial
  2008. """
  2009. if not has_dups(s):
  2010. yield from _set_derangements(s)
  2011. else:
  2012. for p in multiset_derangements(s):
  2013. yield list(p)
  2014. def necklaces(n, k, free=False):
  2015. """
  2016. A routine to generate necklaces that may (free=True) or may not
  2017. (free=False) be turned over to be viewed. The "necklaces" returned
  2018. are comprised of ``n`` integers (beads) with ``k`` different
  2019. values (colors). Only unique necklaces are returned.
  2020. Examples
  2021. ========
  2022. >>> from sympy.utilities.iterables import necklaces, bracelets
  2023. >>> def show(s, i):
  2024. ... return ''.join(s[j] for j in i)
  2025. The "unrestricted necklace" is sometimes also referred to as a
  2026. "bracelet" (an object that can be turned over, a sequence that can
  2027. be reversed) and the term "necklace" is used to imply a sequence
  2028. that cannot be reversed. So ACB == ABC for a bracelet (rotate and
  2029. reverse) while the two are different for a necklace since rotation
  2030. alone cannot make the two sequences the same.
  2031. (mnemonic: Bracelets can be viewed Backwards, but Not Necklaces.)
  2032. >>> B = [show('ABC', i) for i in bracelets(3, 3)]
  2033. >>> N = [show('ABC', i) for i in necklaces(3, 3)]
  2034. >>> set(N) - set(B)
  2035. {'ACB'}
  2036. >>> list(necklaces(4, 2))
  2037. [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1),
  2038. (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]
  2039. >>> [show('.o', i) for i in bracelets(4, 2)]
  2040. ['....', '...o', '..oo', '.o.o', '.ooo', 'oooo']
  2041. References
  2042. ==========
  2043. .. [1] http://mathworld.wolfram.com/Necklace.html
  2044. """
  2045. return uniq(minlex(i, directed=not free) for i in
  2046. variations(list(range(k)), n, repetition=True))
  2047. def bracelets(n, k):
  2048. """Wrapper to necklaces to return a free (unrestricted) necklace."""
  2049. return necklaces(n, k, free=True)
  2050. def generate_oriented_forest(n):
  2051. """
  2052. This algorithm generates oriented forests.
  2053. An oriented graph is a directed graph having no symmetric pair of directed
  2054. edges. A forest is an acyclic graph, i.e., it has no cycles. A forest can
  2055. also be described as a disjoint union of trees, which are graphs in which
  2056. any two vertices are connected by exactly one simple path.
  2057. Examples
  2058. ========
  2059. >>> from sympy.utilities.iterables import generate_oriented_forest
  2060. >>> list(generate_oriented_forest(4))
  2061. [[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0], \
  2062. [0, 1, 1, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
  2063. References
  2064. ==========
  2065. .. [1] T. Beyer and S.M. Hedetniemi: constant time generation of
  2066. rooted trees, SIAM J. Computing Vol. 9, No. 4, November 1980
  2067. .. [2] https://stackoverflow.com/questions/1633833/oriented-forest-taocp-algorithm-in-python
  2068. """
  2069. P = list(range(-1, n))
  2070. while True:
  2071. yield P[1:]
  2072. if P[n] > 0:
  2073. P[n] = P[P[n]]
  2074. else:
  2075. for p in range(n - 1, 0, -1):
  2076. if P[p] != 0:
  2077. target = P[p] - 1
  2078. for q in range(p - 1, 0, -1):
  2079. if P[q] == target:
  2080. break
  2081. offset = p - q
  2082. for i in range(p, n + 1):
  2083. P[i] = P[i - offset]
  2084. break
  2085. else:
  2086. break
  2087. def minlex(seq, directed=True, key=None):
  2088. r"""
  2089. Return the rotation of the sequence in which the lexically smallest
  2090. elements appear first, e.g. `cba \rightarrow acb`.
  2091. The sequence returned is a tuple, unless the input sequence is a string
  2092. in which case a string is returned.
  2093. If ``directed`` is False then the smaller of the sequence and the
  2094. reversed sequence is returned, e.g. `cba \rightarrow abc`.
  2095. If ``key`` is not None then it is used to extract a comparison key from each element in iterable.
  2096. Examples
  2097. ========
  2098. >>> from sympy.combinatorics.polyhedron import minlex
  2099. >>> minlex((1, 2, 0))
  2100. (0, 1, 2)
  2101. >>> minlex((1, 0, 2))
  2102. (0, 2, 1)
  2103. >>> minlex((1, 0, 2), directed=False)
  2104. (0, 1, 2)
  2105. >>> minlex('11010011000', directed=True)
  2106. '00011010011'
  2107. >>> minlex('11010011000', directed=False)
  2108. '00011001011'
  2109. >>> minlex(('bb', 'aaa', 'c', 'a'))
  2110. ('a', 'bb', 'aaa', 'c')
  2111. >>> minlex(('bb', 'aaa', 'c', 'a'), key=len)
  2112. ('c', 'a', 'bb', 'aaa')
  2113. """
  2114. from sympy.functions.elementary.miscellaneous import Id
  2115. if key is None: key = Id
  2116. best = rotate_left(seq, least_rotation(seq, key=key))
  2117. if not directed:
  2118. rseq = seq[::-1]
  2119. rbest = rotate_left(rseq, least_rotation(rseq, key=key))
  2120. best = min(best, rbest, key=key)
  2121. # Convert to tuple, unless we started with a string.
  2122. return tuple(best) if not isinstance(seq, str) else best
  2123. def runs(seq, op=gt):
  2124. """Group the sequence into lists in which successive elements
  2125. all compare the same with the comparison operator, ``op``:
  2126. op(seq[i + 1], seq[i]) is True from all elements in a run.
  2127. Examples
  2128. ========
  2129. >>> from sympy.utilities.iterables import runs
  2130. >>> from operator import ge
  2131. >>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2])
  2132. [[0, 1, 2], [2], [1, 4], [3], [2], [2]]
  2133. >>> runs([0, 1, 2, 2, 1, 4, 3, 2, 2], op=ge)
  2134. [[0, 1, 2, 2], [1, 4], [3], [2, 2]]
  2135. """
  2136. cycles = []
  2137. seq = iter(seq)
  2138. try:
  2139. run = [next(seq)]
  2140. except StopIteration:
  2141. return []
  2142. while True:
  2143. try:
  2144. ei = next(seq)
  2145. except StopIteration:
  2146. break
  2147. if op(ei, run[-1]):
  2148. run.append(ei)
  2149. continue
  2150. else:
  2151. cycles.append(run)
  2152. run = [ei]
  2153. if run:
  2154. cycles.append(run)
  2155. return cycles
  2156. def kbins(l, k, ordered=None):
  2157. """
  2158. Return sequence ``l`` partitioned into ``k`` bins.
  2159. Examples
  2160. ========
  2161. The default is to give the items in the same order, but grouped
  2162. into k partitions without any reordering:
  2163. >>> from sympy.utilities.iterables import kbins
  2164. >>> for p in kbins(list(range(5)), 2):
  2165. ... print(p)
  2166. ...
  2167. [[0], [1, 2, 3, 4]]
  2168. [[0, 1], [2, 3, 4]]
  2169. [[0, 1, 2], [3, 4]]
  2170. [[0, 1, 2, 3], [4]]
  2171. The ``ordered`` flag is either None (to give the simple partition
  2172. of the elements) or is a 2 digit integer indicating whether the order of
  2173. the bins and the order of the items in the bins matters. Given::
  2174. A = [[0], [1, 2]]
  2175. B = [[1, 2], [0]]
  2176. C = [[2, 1], [0]]
  2177. D = [[0], [2, 1]]
  2178. the following values for ``ordered`` have the shown meanings::
  2179. 00 means A == B == C == D
  2180. 01 means A == B
  2181. 10 means A == D
  2182. 11 means A == A
  2183. >>> for ordered_flag in [None, 0, 1, 10, 11]:
  2184. ... print('ordered = %s' % ordered_flag)
  2185. ... for p in kbins(list(range(3)), 2, ordered=ordered_flag):
  2186. ... print(' %s' % p)
  2187. ...
  2188. ordered = None
  2189. [[0], [1, 2]]
  2190. [[0, 1], [2]]
  2191. ordered = 0
  2192. [[0, 1], [2]]
  2193. [[0, 2], [1]]
  2194. [[0], [1, 2]]
  2195. ordered = 1
  2196. [[0], [1, 2]]
  2197. [[0], [2, 1]]
  2198. [[1], [0, 2]]
  2199. [[1], [2, 0]]
  2200. [[2], [0, 1]]
  2201. [[2], [1, 0]]
  2202. ordered = 10
  2203. [[0, 1], [2]]
  2204. [[2], [0, 1]]
  2205. [[0, 2], [1]]
  2206. [[1], [0, 2]]
  2207. [[0], [1, 2]]
  2208. [[1, 2], [0]]
  2209. ordered = 11
  2210. [[0], [1, 2]]
  2211. [[0, 1], [2]]
  2212. [[0], [2, 1]]
  2213. [[0, 2], [1]]
  2214. [[1], [0, 2]]
  2215. [[1, 0], [2]]
  2216. [[1], [2, 0]]
  2217. [[1, 2], [0]]
  2218. [[2], [0, 1]]
  2219. [[2, 0], [1]]
  2220. [[2], [1, 0]]
  2221. [[2, 1], [0]]
  2222. See Also
  2223. ========
  2224. partitions, multiset_partitions
  2225. """
  2226. def partition(lista, bins):
  2227. # EnricoGiampieri's partition generator from
  2228. # https://stackoverflow.com/questions/13131491/
  2229. # partition-n-items-into-k-bins-in-python-lazily
  2230. if len(lista) == 1 or bins == 1:
  2231. yield [lista]
  2232. elif len(lista) > 1 and bins > 1:
  2233. for i in range(1, len(lista)):
  2234. for part in partition(lista[i:], bins - 1):
  2235. if len([lista[:i]] + part) == bins:
  2236. yield [lista[:i]] + part
  2237. if ordered is None:
  2238. yield from partition(l, k)
  2239. elif ordered == 11:
  2240. for pl in multiset_permutations(l):
  2241. pl = list(pl)
  2242. yield from partition(pl, k)
  2243. elif ordered == 00:
  2244. yield from multiset_partitions(l, k)
  2245. elif ordered == 10:
  2246. for p in multiset_partitions(l, k):
  2247. for perm in permutations(p):
  2248. yield list(perm)
  2249. elif ordered == 1:
  2250. for kgot, p in partitions(len(l), k, size=True):
  2251. if kgot != k:
  2252. continue
  2253. for li in multiset_permutations(l):
  2254. rv = []
  2255. i = j = 0
  2256. li = list(li)
  2257. for size, multiplicity in sorted(p.items()):
  2258. for m in range(multiplicity):
  2259. j = i + size
  2260. rv.append(li[i: j])
  2261. i = j
  2262. yield rv
  2263. else:
  2264. raise ValueError(
  2265. 'ordered must be one of 00, 01, 10 or 11, not %s' % ordered)
  2266. def permute_signs(t):
  2267. """Return iterator in which the signs of non-zero elements
  2268. of t are permuted.
  2269. Examples
  2270. ========
  2271. >>> from sympy.utilities.iterables import permute_signs
  2272. >>> list(permute_signs((0, 1, 2)))
  2273. [(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2)]
  2274. """
  2275. for signs in product(*[(1, -1)]*(len(t) - t.count(0))):
  2276. signs = list(signs)
  2277. yield type(t)([i*signs.pop() if i else i for i in t])
  2278. def signed_permutations(t):
  2279. """Return iterator in which the signs of non-zero elements
  2280. of t and the order of the elements are permuted.
  2281. Examples
  2282. ========
  2283. >>> from sympy.utilities.iterables import signed_permutations
  2284. >>> list(signed_permutations((0, 1, 2)))
  2285. [(0, 1, 2), (0, -1, 2), (0, 1, -2), (0, -1, -2), (0, 2, 1),
  2286. (0, -2, 1), (0, 2, -1), (0, -2, -1), (1, 0, 2), (-1, 0, 2),
  2287. (1, 0, -2), (-1, 0, -2), (1, 2, 0), (-1, 2, 0), (1, -2, 0),
  2288. (-1, -2, 0), (2, 0, 1), (-2, 0, 1), (2, 0, -1), (-2, 0, -1),
  2289. (2, 1, 0), (-2, 1, 0), (2, -1, 0), (-2, -1, 0)]
  2290. """
  2291. return (type(t)(i) for j in permutations(t)
  2292. for i in permute_signs(j))
  2293. def rotations(s, dir=1):
  2294. """Return a generator giving the items in s as list where
  2295. each subsequent list has the items rotated to the left (default)
  2296. or right (dir=-1) relative to the previous list.
  2297. Examples
  2298. ========
  2299. >>> from sympy.utilities.iterables import rotations
  2300. >>> list(rotations([1,2,3]))
  2301. [[1, 2, 3], [2, 3, 1], [3, 1, 2]]
  2302. >>> list(rotations([1,2,3], -1))
  2303. [[1, 2, 3], [3, 1, 2], [2, 3, 1]]
  2304. """
  2305. seq = list(s)
  2306. for i in range(len(seq)):
  2307. yield seq
  2308. seq = rotate_left(seq, dir)
  2309. def roundrobin(*iterables):
  2310. """roundrobin recipe taken from itertools documentation:
  2311. https://docs.python.org/2/library/itertools.html#recipes
  2312. roundrobin('ABC', 'D', 'EF') --> A D E B F C
  2313. Recipe credited to George Sakkis
  2314. """
  2315. import itertools
  2316. nexts = itertools.cycle(iter(it).__next__ for it in iterables)
  2317. pending = len(iterables)
  2318. while pending:
  2319. try:
  2320. for nxt in nexts:
  2321. yield nxt()
  2322. except StopIteration:
  2323. pending -= 1
  2324. nexts = itertools.cycle(itertools.islice(nexts, pending))
  2325. class NotIterable:
  2326. """
  2327. Use this as mixin when creating a class which is not supposed to
  2328. return true when iterable() is called on its instances because
  2329. calling list() on the instance, for example, would result in
  2330. an infinite loop.
  2331. """
  2332. pass
  2333. def iterable(i, exclude=(str, dict, NotIterable)):
  2334. """
  2335. Return a boolean indicating whether ``i`` is SymPy iterable.
  2336. True also indicates that the iterator is finite, e.g. you can
  2337. call list(...) on the instance.
  2338. When SymPy is working with iterables, it is almost always assuming
  2339. that the iterable is not a string or a mapping, so those are excluded
  2340. by default. If you want a pure Python definition, make exclude=None. To
  2341. exclude multiple items, pass them as a tuple.
  2342. You can also set the _iterable attribute to True or False on your class,
  2343. which will override the checks here, including the exclude test.
  2344. As a rule of thumb, some SymPy functions use this to check if they should
  2345. recursively map over an object. If an object is technically iterable in
  2346. the Python sense but does not desire this behavior (e.g., because its
  2347. iteration is not finite, or because iteration might induce an unwanted
  2348. computation), it should disable it by setting the _iterable attribute to False.
  2349. See also: is_sequence
  2350. Examples
  2351. ========
  2352. >>> from sympy.utilities.iterables import iterable
  2353. >>> from sympy import Tuple
  2354. >>> things = [[1], (1,), set([1]), Tuple(1), (j for j in [1, 2]), {1:2}, '1', 1]
  2355. >>> for i in things:
  2356. ... print('%s %s' % (iterable(i), type(i)))
  2357. True <... 'list'>
  2358. True <... 'tuple'>
  2359. True <... 'set'>
  2360. True <class 'sympy.core.containers.Tuple'>
  2361. True <... 'generator'>
  2362. False <... 'dict'>
  2363. False <... 'str'>
  2364. False <... 'int'>
  2365. >>> iterable({}, exclude=None)
  2366. True
  2367. >>> iterable({}, exclude=str)
  2368. True
  2369. >>> iterable("no", exclude=str)
  2370. False
  2371. """
  2372. if hasattr(i, '_iterable'):
  2373. return i._iterable
  2374. try:
  2375. iter(i)
  2376. except TypeError:
  2377. return False
  2378. if exclude:
  2379. return not isinstance(i, exclude)
  2380. return True
  2381. def is_sequence(i, include=None):
  2382. """
  2383. Return a boolean indicating whether ``i`` is a sequence in the SymPy
  2384. sense. If anything that fails the test below should be included as
  2385. being a sequence for your application, set 'include' to that object's
  2386. type; multiple types should be passed as a tuple of types.
  2387. Note: although generators can generate a sequence, they often need special
  2388. handling to make sure their elements are captured before the generator is
  2389. exhausted, so these are not included by default in the definition of a
  2390. sequence.
  2391. See also: iterable
  2392. Examples
  2393. ========
  2394. >>> from sympy.utilities.iterables import is_sequence
  2395. >>> from types import GeneratorType
  2396. >>> is_sequence([])
  2397. True
  2398. >>> is_sequence(set())
  2399. False
  2400. >>> is_sequence('abc')
  2401. False
  2402. >>> is_sequence('abc', include=str)
  2403. True
  2404. >>> generator = (c for c in 'abc')
  2405. >>> is_sequence(generator)
  2406. False
  2407. >>> is_sequence(generator, include=(str, GeneratorType))
  2408. True
  2409. """
  2410. return (hasattr(i, '__getitem__') and
  2411. iterable(i) or
  2412. bool(include) and
  2413. isinstance(i, include))
  2414. @deprecated(
  2415. """
  2416. Using postorder_traversal from the sympy.utilities.iterables submodule is
  2417. deprecated.
  2418. Instead, use postorder_traversal from the top-level sympy namespace, like
  2419. sympy.postorder_traversal
  2420. """,
  2421. deprecated_since_version="1.10",
  2422. active_deprecations_target="deprecated-traversal-functions-moved")
  2423. def postorder_traversal(node, keys=None):
  2424. from sympy.core.traversal import postorder_traversal as _postorder_traversal
  2425. return _postorder_traversal(node, keys=keys)
  2426. @deprecated(
  2427. """
  2428. Using interactive_traversal from the sympy.utilities.iterables submodule
  2429. is deprecated.
  2430. Instead, use interactive_traversal from the top-level sympy namespace,
  2431. like
  2432. sympy.interactive_traversal
  2433. """,
  2434. deprecated_since_version="1.10",
  2435. active_deprecations_target="deprecated-traversal-functions-moved")
  2436. def interactive_traversal(expr):
  2437. from sympy.interactive.traversal import interactive_traversal as _interactive_traversal
  2438. return _interactive_traversal(expr)
  2439. @deprecated(
  2440. """
  2441. Importing default_sort_key from sympy.utilities.iterables is deprecated.
  2442. Use from sympy import default_sort_key instead.
  2443. """,
  2444. deprecated_since_version="1.10",
  2445. active_deprecations_target="deprecated-sympy-core-compatibility",
  2446. )
  2447. def default_sort_key(*args, **kwargs):
  2448. from sympy import default_sort_key as _default_sort_key
  2449. return _default_sort_key(*args, **kwargs)
  2450. @deprecated(
  2451. """
  2452. Importing default_sort_key from sympy.utilities.iterables is deprecated.
  2453. Use from sympy import default_sort_key instead.
  2454. """,
  2455. deprecated_since_version="1.10",
  2456. active_deprecations_target="deprecated-sympy-core-compatibility",
  2457. )
  2458. def ordered(*args, **kwargs):
  2459. from sympy import ordered as _ordered
  2460. return _ordered(*args, **kwargs)