Itertool Functions¶

The following functions all construct and return iterators. Some providestreams of infinite length, so they should only be accessed by functions orloops that truncate the stream.

itertools.accumulate(iterable[,function,*,initial=None])¶

Make an iterator that returns accumulated sums or accumulatedresults from other binary functions.

Thefunction defaults to addition. Thefunction should accepttwo arguments, an accumulated total and a value from theiterable.

If aninitial value is provided, the accumulation will start withthat value and the output will have one more element than the inputiterable.

Roughly equivalent to:

defaccumulate(iterable,function=operator.add,*,initial=None):'Return running totals'# accumulate([1,2,3,4,5]) → 1 3 6 10 15# accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115# accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120iterator=iter(iterable)total=initialifinitialisNone:try:total=next(iterator)exceptStopIteration:returnyieldtotalforelementiniterator:total=function(total,element)yieldtotal

To compute a running minimum, setfunction tomin().For a running maximum, setfunction tomax().Or for a running product, setfunction tooperator.mul().To build anamortization table,accumulate the interest and apply payments:

>>>data=[3,4,6,2,1,9,0,7,5,8]>>>list(accumulate(data,max))# running maximum[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]>>>list(accumulate(data,operator.mul))# running product[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]# Amortize a 5% loan of 1000 with 10 annual payments of 90>>>update=lambdabalance,payment:round(balance*1.05)-payment>>>list(accumulate(repeat(90,10),update,initial=1_000))[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]

Seefunctools.reduce() for a similar function that returns only thefinal accumulated value.

Added in version 3.2.

Changed in version 3.3:Added the optionalfunction parameter.

Changed in version 3.8:Added the optionalinitial parameter.

itertools.batched(iterable,n,*,strict=False)¶

Batch data from theiterable into tuples of lengthn. The lastbatch may be shorter thann.

Ifstrict is true, will raise aValueError if the finalbatch is shorter thann.

Loops over the input iterable and accumulates data into tuples up tosizen. The input is consumed lazily, just enough to fill a batch.The result is yielded as soon as the batch is full or when the inputiterable is exhausted:

>>>flattened_data=['roses','red','violets','blue','sugar','sweet']>>>unflattened=list(batched(flattened_data,2))>>>unflattened[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]

Roughly equivalent to:

defbatched(iterable,n,*,strict=False):# batched('ABCDEFG', 3) → ABC DEF Gifn<1:raiseValueError('n must be at least one')iterator=iter(iterable)whilebatch:=tuple(islice(iterator,n)):ifstrictandlen(batch)!=n:raiseValueError('batched(): incomplete batch')yieldbatch

Added in version 3.12.

Changed in version 3.13:Added thestrict option.

itertools.chain(*iterables)¶

Make an iterator that returns elements from the first iterable untilit is exhausted, then proceeds to the next iterable, until all of theiterables are exhausted. This combines multiple data sources into asingle iterator. Roughly equivalent to:

defchain(*iterables):# chain('ABC', 'DEF') → A B C D E Fforiterableiniterables:yield fromiterable

classmethodchain.from_iterable(iterable)¶

Alternate constructor forchain(). Gets chained inputs from asingle iterable argument that is evaluated lazily. Roughly equivalent to:

deffrom_iterable(iterables):# chain.from_iterable(['ABC', 'DEF']) → A B C D E Fforiterableiniterables:yield fromiterable

itertools.combinations(iterable,r)¶

Returnr length subsequences of elements from the inputiterable.

The output is a subsequence ofproduct() keeping only entries thatare subsequences of theiterable. The length of the output is givenbymath.comb() which computesn!/r!/(n-r)! when0≤r≤n or zero whenr>n.

The combination tuples are emitted in lexicographic order according tothe order of the inputiterable. If the inputiterable is sorted,the output tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on theirvalue. If the input elements are unique, there will be no repeatedvalues within each combination.

Roughly equivalent to:

defcombinations(iterable,r):# combinations('ABCD', 2) → AB AC AD BC BD CD# combinations(range(4), 3) → 012 013 023 123pool=tuple(iterable)n=len(pool)ifr>n:returnindices=list(range(r))yieldtuple(pool[i]foriinindices)whileTrue:foriinreversed(range(r)):ifindices[i]!=i+n-r:breakelse:returnindices[i]+=1forjinrange(i+1,r):indices[j]=indices[j-1]+1yieldtuple(pool[i]foriinindices)

itertools.combinations_with_replacement(iterable,r)¶

Returnr length subsequences of elements from the inputiterableallowing individual elements to be repeated more than once.

The output is a subsequence ofproduct() that keeps only entriesthat are subsequences (with possible repeated elements) of theiterable. The number of subsequence returned is(n+r-1)!/r!/(n-1)! whenn>0.

The combination tuples are emitted in lexicographic order according tothe order of the inputiterable. if the inputiterable is sorted,the output tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on theirvalue. If the input elements are unique, the generated combinationswill also be unique.

Roughly equivalent to:

defcombinations_with_replacement(iterable,r):# combinations_with_replacement('ABC', 2) → AA AB AC BB BC CCpool=tuple(iterable)n=len(pool)ifnotnandr:returnindices=[0]*ryieldtuple(pool[i]foriinindices)whileTrue:foriinreversed(range(r)):ifindices[i]!=n-1:breakelse:returnindices[i:]=[indices[i]+1]*(r-i)yieldtuple(pool[i]foriinindices)

Added in version 3.1.

itertools.compress(data,selectors)¶

Make an iterator that returns elements fromdata where thecorresponding element inselectors is true. Stops when either thedata orselectors iterables have been exhausted. Roughlyequivalent to:

defcompress(data,selectors):# compress('ABCDEF', [1,0,1,0,1,1]) → A C E Freturn(datumfordatum,selectorinzip(data,selectors)ifselector)

Added in version 3.1.

itertools.count(start=0,step=1)¶

Make an iterator that returns evenly spaced values beginning withstart. Can be used withmap() to generate consecutive datapoints or withzip() to add sequence numbers. Roughlyequivalent to:

defcount(start=0,step=1):# count(10) → 10 11 12 13 14 ...# count(2.5, 0.5) → 2.5 3.0 3.5 ...n=startwhileTrue:yieldnn+=step

When counting with floating-point numbers, better accuracy can sometimes beachieved by substituting multiplicative code such as:(start+step*iforiincount()).

Changed in version 3.1:Addedstep argument and allowed non-integer arguments.

itertools.cycle(iterable)¶

Make an iterator returning elements from theiterable and saving acopy of each. When the iterable is exhausted, return elements fromthe saved copy. Repeats indefinitely. Roughly equivalent to:

defcycle(iterable):# cycle('ABCD') → A B C D A B C D A B C D ...saved=[]forelementiniterable:yieldelementsaved.append(element)whilesaved:forelementinsaved:yieldelement

This itertool may require significant auxiliary storage (depending onthe length of the iterable).

itertools.dropwhile(predicate,iterable)¶

Make an iterator that drops elements from theiterable while thepredicate is true and afterwards returns every element. Roughlyequivalent to:

defdropwhile(predicate,iterable):# dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8iterator=iter(iterable)forxiniterator:ifnotpredicate(x):yieldxbreakforxiniterator:yieldx

Note this does not produceany output until the predicate firstbecomes false, so this itertool may have a lengthy start-up time.

itertools.filterfalse(predicate,iterable)¶

Make an iterator that filters elements from theiterable returningonly those for which thepredicate returns a false value. Ifpredicate isNone, returns the items that are false. Roughlyequivalent to:

deffilterfalse(predicate,iterable):# filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8ifpredicateisNone:predicate=boolforxiniterable:ifnotpredicate(x):yieldx

itertools.groupby(iterable,key=None)¶

Make an iterator that returns consecutive keys and groups from theiterable.Thekey is a function computing a key value for each element. If notspecified or isNone,key defaults to an identity function and returnsthe element unchanged. Generally, the iterable needs to already be sorted onthe same key function.

The operation ofgroupby() is similar to theuniq filter in Unix. Itgenerates a break or new group every time the value of the key function changes(which is why it is usually necessary to have sorted the data using the same keyfunction). That behavior differs from SQL’s GROUP BY which aggregates commonelements regardless of their input order.

The returned group is itself an iterator that shares the underlying iterablewithgroupby(). Because the source is shared, when thegroupby()object is advanced, the previous group is no longer visible. So, if that datais needed later, it should be stored as a list:

groups=[]uniquekeys=[]data=sorted(data,key=keyfunc)fork,gingroupby(data,keyfunc):groups.append(list(g))# Store group iterator as a listuniquekeys.append(k)

groupby() is roughly equivalent to:

defgroupby(iterable,key=None):# [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B# [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC Dkeyfunc=(lambdax:x)ifkeyisNoneelsekeyiterator=iter(iterable)exhausted=Falsedef_grouper(target_key):nonlocalcurr_value,curr_key,exhaustedyieldcurr_valueforcurr_valueiniterator:curr_key=keyfunc(curr_value)ifcurr_key!=target_key:returnyieldcurr_valueexhausted=Truetry:curr_value=next(iterator)exceptStopIteration:returncurr_key=keyfunc(curr_value)whilenotexhausted:target_key=curr_keycurr_group=_grouper(target_key)yieldcurr_key,curr_groupifcurr_key==target_key:for_incurr_group:pass

itertools.islice(iterable,stop)¶

itertools.islice(iterable,start,stop[,step])

Make an iterator that returns selected elements from the iterable.Works like sequence slicing but does not support negative values forstart,stop, orstep.

Ifstart is zero orNone, iteration starts at zero. Otherwise,elements from the iterable are skipped untilstart is reached.

Ifstop isNone, iteration continues until the input isexhausted, if at all. Otherwise, it stops at the specified position.

Ifstep isNone, the step defaults to one. Elements are returnedconsecutively unlessstep is set higher than one which results initems being skipped.

Roughly equivalent to:

defislice(iterable,*args):# islice('ABCDEFG', 2) → A B# islice('ABCDEFG', 2, 4) → C D# islice('ABCDEFG', 2, None) → C D E F G# islice('ABCDEFG', 0, None, 2) → A C E Gs=slice(*args)start=0ifs.startisNoneelses.startstop=s.stopstep=1ifs.stepisNoneelses.stepifstart<0or(stopisnotNoneandstop<0)orstep<=0:raiseValueErrorindices=count()ifstopisNoneelserange(max(start,stop))next_i=startfori,elementinzip(indices,iterable):ifi==next_i:yieldelementnext_i+=step

If the input is an iterator, then fully consuming theisliceadvances the input iterator bymax(start,stop) steps regardlessof thestep value.

itertools.pairwise(iterable)¶

Return successive overlapping pairs taken from the inputiterable.

The number of 2-tuples in the output iterator will be one fewer than thenumber of inputs. It will be empty if the input iterable has fewer thantwo values.

Roughly equivalent to:

defpairwise(iterable):# pairwise('ABCDEFG') → AB BC CD DE EF FGiterator=iter(iterable)a=next(iterator,None)forbiniterator:yielda,ba=b

Added in version 3.10.

itertools.permutations(iterable,r=None)¶

Return successiver lengthpermutations of elements from theiterable.

Ifr is not specified or isNone, thenr defaults to the lengthof theiterable and all possible full-length permutationsare generated.

The output is a subsequence ofproduct() where entries withrepeated elements have been filtered out. The length of the output isgiven bymath.perm() which computesn!/(n-r)! when0≤r≤n or zero whenr>n.

The permutation tuples are emitted in lexicographic order according tothe order of the inputiterable. If the inputiterable is sorted,the output tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on theirvalue. If the input elements are unique, there will be no repeatedvalues within a permutation.

Roughly equivalent to:

defpermutations(iterable,r=None):# permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC# permutations(range(3)) → 012 021 102 120 201 210pool=tuple(iterable)n=len(pool)r=nifrisNoneelserifr>n:returnindices=list(range(n))cycles=list(range(n,n-r,-1))yieldtuple(pool[i]foriinindices[:r])whilen:foriinreversed(range(r)):cycles[i]-=1ifcycles[i]==0:indices[i:]=indices[i+1:]+indices[i:i+1]cycles[i]=n-ielse:j=cycles[i]indices[i],indices[-j]=indices[-j],indices[i]yieldtuple(pool[i]foriinindices[:r])breakelse:return

itertools.product(*iterables,repeat=1)¶

Cartesian productof the input iterables.

Roughly equivalent to nested for-loops in a generator expression. For example,product(A,B) returns the same as((x,y)forxinAforyinB).

The nested loops cycle like an odometer with the rightmost element advancingon every iteration. This pattern creates a lexicographic ordering so that ifthe input’s iterables are sorted, the product tuples are emitted in sortedorder.

To compute the product of an iterable with itself, specify the number ofrepetitions with the optionalrepeat keyword argument. For example,product(A,repeat=4) means the same asproduct(A,A,A,A).

This function is roughly equivalent to the following code, except that theactual implementation does not build up intermediate results in memory:

defproduct(*iterables,repeat=1):# product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy# product(range(2), repeat=3) → 000 001 010 011 100 101 110 111ifrepeat<0:raiseValueError('repeat argument cannot be negative')pools=[tuple(pool)forpooliniterables]*repeatresult=[[]]forpoolinpools:result=[x+[y]forxinresultforyinpool]forprodinresult:yieldtuple(prod)

Beforeproduct() runs, it completely consumes the input iterables,keeping pools of values in memory to generate the products. Accordingly,it is only useful with finite inputs.

itertools.repeat(object[,times])¶

Make an iterator that returnsobject over and over again. Runs indefinitelyunless thetimes argument is specified.

Roughly equivalent to:

defrepeat(object,times=None):# repeat(10, 3) → 10 10 10iftimesisNone:whileTrue:yieldobjectelse:foriinrange(times):yieldobject

A common use forrepeat is to supply a stream of constant values tomaporzip:

>>>list(map(pow,range(10),repeat(2)))[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

itertools.starmap(function,iterable)¶

Make an iterator that computes thefunction using arguments obtainedfrom theiterable. Used instead ofmap() when argumentparameters have already been “pre-zipped” into tuples.

The difference betweenmap() andstarmap() parallels thedistinction betweenfunction(a,b) andfunction(*c). Roughlyequivalent to:

defstarmap(function,iterable):# starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000forargsiniterable:yieldfunction(*args)

itertools.takewhile(predicate,iterable)¶

Make an iterator that returns elements from theiterable as long asthepredicate is true. Roughly equivalent to:

deftakewhile(predicate,iterable):# takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4forxiniterable:ifnotpredicate(x):breakyieldx

Note, the element that first fails the predicate condition isconsumed from the input iterator and there is no way to access it.This could be an issue if an application wants to further consume theinput iterator aftertakewhile has been run to exhaustion. To workaround this problem, consider usingmore-itertools before_and_after()instead.

itertools.tee(iterable,n=2)¶

Returnn independent iterators from a single iterable.

Roughly equivalent to:

deftee(iterable,n=2):ifn<0:raiseValueErrorifn==0:return()iterator=_tee(iterable)result=[iterator]for_inrange(n-1):result.append(_tee(iterator))returntuple(result)class_tee:def__init__(self,iterable):it=iter(iterable)ifisinstance(it,_tee):self.iterator=it.iteratorself.link=it.linkelse:self.iterator=itself.link=[None,None]def__iter__(self):returnselfdef__next__(self):link=self.linkiflink[1]isNone:link[0]=next(self.iterator)link[1]=[None,None]value,self.link=linkreturnvalue

When the inputiterable is already a tee iterator object, allmembers of the return tuple are constructed as if they had beenproduced by the upstreamtee() call. This “flattening step”allows nestedtee() calls to share the same underlying datachain and to have a single update step rather than a chain of calls.

The flattening property makes tee iterators efficiently peekable:

deflookahead(tee_iterator):"Return the next value without moving the input forward"[forked_iterator]=tee(tee_iterator,1)returnnext(forked_iterator)

>>>iterator=iter('abcdef')>>>[iterator]=tee(iterator,1)# Make the input peekable>>>next(iterator)# Move the iterator forward'a'>>>lookahead(iterator)# Check next value'b'>>>next(iterator)# Continue moving forward'b'

tee iterators are not threadsafe. ARuntimeError may beraised when simultaneously using iterators returned by the sametee()call, even if the originaliterable is threadsafe.

This itertool may require significant auxiliary storage (depending on howmuch temporary data needs to be stored). In general, if one iterator usesmost or all of the data before another iterator starts, it is faster to uselist() instead oftee().

itertools.zip_longest(*iterables,fillvalue=None)¶

Make an iterator that aggregates elements from each of theiterables.

If the iterables are of uneven length, missing values are filled-inwithfillvalue. If not specified,fillvalue defaults toNone.

Iteration continues until the longest iterable is exhausted.

Roughly equivalent to:

defzip_longest(*iterables,fillvalue=None):# zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-iterators=list(map(iter,iterables))num_active=len(iterators)ifnotnum_active:returnwhileTrue:values=[]fori,iteratorinenumerate(iterators):try:value=next(iterator)exceptStopIteration:num_active-=1ifnotnum_active:returniterators[i]=repeat(fillvalue)value=fillvaluevalues.append(value)yieldtuple(values)

If one of the iterables is potentially infinite, then thezip_longest()function should be wrapped with something that limits the number of calls(for exampleislice() ortakewhile()).

Itertools Recipes¶

This section shows recipes for creating an extended toolset using the existingitertools as building blocks.

The primary purpose of the itertools recipes is educational. The recipes showvarious ways of thinking about individual tools — for example, thatchain.from_iterable is related to the concept of flattening. The recipesalso give ideas about ways that the tools can be combined — for example, howstarmap() andrepeat() can work together. The recipes also show patternsfor using itertools with theoperator andcollections modules aswell as with the built-in itertools such asmap(),filter(),reversed(), andenumerate().

A secondary purpose of the recipes is to serve as an incubator. Theaccumulate(),compress(), andpairwise() itertools started out asrecipes. Currently, thesliding_window(),iter_index(), andsieve()recipes are being tested to see whether they prove their worth.

Substantially all of these recipes and many, many others can be installed fromthemore-itertools project foundon the Python Package Index:

python-mpipinstallmore-itertools

Many of the recipes offer the same high performance as the underlying toolset.Superior memory performance is kept by processing elements one at a time ratherthan bringing the whole iterable into memory all at once. Code volume is keptsmall by linking the tools together in afunctional style. High speedis retained by preferring “vectorized” building blocks over the use of for-loopsandgenerators which incur interpreter overhead.

fromcollectionsimportCounter,dequefromcontextlibimportsuppressfromfunctoolsimportreducefrommathimportcomb,prod,sumprod,isqrtfromoperatorimportitemgetter,getitem,mul,negdeftake(n,iterable):"Return first n items of the iterable as a list."returnlist(islice(iterable,n))defprepend(value,iterable):"Prepend a single value in front of an iterable."# prepend(1, [2, 3, 4]) → 1 2 3 4returnchain([value],iterable)deftabulate(function,start=0):"Return function(0), function(1), ..."returnmap(function,count(start))defrepeatfunc(function,times=None,*args):"Repeat calls to a function with specified arguments."iftimesisNone:returnstarmap(function,repeat(args))returnstarmap(function,repeat(args,times))defflatten(list_of_lists):"Flatten one level of nesting."returnchain.from_iterable(list_of_lists)defncycles(iterable,n):"Returns the sequence elements n times."returnchain.from_iterable(repeat(tuple(iterable),n))defloops(n):"Loop n times. Like range(n) but without creating integers."# for _ in loops(100): ...returnrepeat(None,n)deftail(n,iterable):"Return an iterator over the last n items."# tail(3, 'ABCDEFG') → E F Greturniter(deque(iterable,maxlen=n))defconsume(iterator,n=None):"Advance the iterator n-steps ahead. If n is None, consume entirely."# Use functions that consume iterators at C speed.ifnisNone:deque(iterator,maxlen=0)else:next(islice(iterator,n,n),None)defnth(iterable,n,default=None):"Returns the nth item or a default value."returnnext(islice(iterable,n,None),default)defquantify(iterable,predicate=bool):"Given a predicate that returns True or False, count the True results."returnsum(map(predicate,iterable))deffirst_true(iterable,default=False,predicate=None):"Returns the first true value or the *default* if there is no true value."# first_true([a,b,c], x) → a or b or c or x# first_true([a,b], x, f) → a if f(a) else b if f(b) else xreturnnext(filter(predicate,iterable),default)defall_equal(iterable,key=None):"Returns True if all the elements are equal to each other."# all_equal('4٤௪౪໔', key=int) → Truereturnlen(take(2,groupby(iterable,key)))<=1defunique_justseen(iterable,key=None):"Yield unique elements, preserving order. Remember only the element just seen."# unique_justseen('AAAABBBCCDAABBB') → A B C D A B# unique_justseen('ABBcCAD', str.casefold) → A B c A DifkeyisNone:returnmap(itemgetter(0),groupby(iterable))returnmap(next,map(itemgetter(1),groupby(iterable,key)))defunique_everseen(iterable,key=None):"Yield unique elements, preserving order. Remember all elements ever seen."# unique_everseen('AAAABBBCCDAABBB') → A B C D# unique_everseen('ABBcCAD', str.casefold) → A B c Dseen=set()ifkeyisNone:forelementinfilterfalse(seen.__contains__,iterable):seen.add(element)yieldelementelse:forelementiniterable:k=key(element)ifknotinseen:seen.add(k)yieldelementdefunique(iterable,key=None,reverse=False):"Yield unique elements in sorted order. Supports unhashable inputs."# unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]sequenced=sorted(iterable,key=key,reverse=reverse)returnunique_justseen(sequenced,key=key)defsliding_window(iterable,n):"Collect data into overlapping fixed-length chunks or blocks."# sliding_window('ABCDEFG', 4) → ABCD BCDE CDEF DEFGiterator=iter(iterable)window=deque(islice(iterator,n-1),maxlen=n)forxiniterator:window.append(x)yieldtuple(window)defgrouper(iterable,n,*,incomplete='fill',fillvalue=None):"Collect data into non-overlapping fixed-length chunks or blocks."# grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx# grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError# grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEFiterators=[iter(iterable)]*nmatchincomplete:case'fill':returnzip_longest(*iterators,fillvalue=fillvalue)case'strict':returnzip(*iterators,strict=True)case'ignore':returnzip(*iterators)case_:raiseValueError('Expected fill, strict, or ignore')defroundrobin(*iterables):"Visit input iterables in a cycle until each is exhausted."# roundrobin('ABC', 'D', 'EF') → A D E B F C# Algorithm credited to George Sakkisiterators=map(iter,iterables)fornum_activeinrange(len(iterables),0,-1):iterators=cycle(islice(iterators,num_active))yield frommap(next,iterators)defsubslices(seq):"Return all contiguous non-empty subslices of a sequence."# subslices('ABCD') → A AB ABC ABCD B BC BCD C CD Dslices=starmap(slice,combinations(range(len(seq)+1),2))returnmap(getitem,repeat(seq),slices)defiter_index(iterable,value,start=0,stop=None):"Return indices where a value occurs in a sequence or iterable."# iter_index('AABCADEAF', 'A') → 0 1 4 7seq_index=getattr(iterable,'index',None)ifseq_indexisNone:iterator=islice(iterable,start,stop)fori,elementinenumerate(iterator,start):ifelementisvalueorelement==value:yieldielse:stop=len(iterable)ifstopisNoneelsestopi=startwithsuppress(ValueError):whileTrue:yield(i:=seq_index(value,i,stop))i+=1defiter_except(function,exception,first=None):"Convert a call-until-exception interface to an iterator interface."# iter_except(d.popitem, KeyError) → non-blocking dictionary iteratorwithsuppress(exception):iffirstisnotNone:yieldfirst()whileTrue:yieldfunction()

The following recipes have a more mathematical flavor:

defmultinomial(*counts):"Number of distinct arrangements of a multiset."# Counter('abracadabra').values() → 5 2 2 1 1# multinomial(5, 2, 2, 1, 1) → 83160returnprod(map(comb,accumulate(counts),counts))defpowerset(iterable):"Subsequences of the iterable from shortest to longest."# powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)s=list(iterable)returnchain.from_iterable(combinations(s,r)forrinrange(len(s)+1))defsum_of_squares(iterable):"Add up the squares of the input values."# sum_of_squares([10, 20, 30]) → 1400returnsumprod(*tee(iterable))defreshape(matrix,columns):"Reshape a 2-D matrix to have a given number of columns."# reshape([(0, 1), (2, 3), (4, 5)], 3) →  (0, 1, 2), (3, 4, 5)returnbatched(chain.from_iterable(matrix),columns,strict=True)deftranspose(matrix):"Swap the rows and columns of a 2-D matrix."# transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)returnzip(*matrix,strict=True)defmatmul(m1,m2):"Multiply two matrices."# matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80), (41, 60)n=len(m2[0])returnbatched(starmap(sumprod,product(m1,transpose(m2))),n)defconvolve(signal,kernel):"""Discrete linear convolution of two iterables.    Equivalent to polynomial multiplication.    Convolutions are mathematically commutative; however, the inputs are    evaluated differently.  The signal is consumed lazily and can be    infinite. The kernel is fully consumed before the calculations begin.    Article:  https://betterexplained.com/articles/intuitive-convolution/    Video:    https://www.youtube.com/watch?v=KuXjwB4LzSA    """# convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60# convolve(data, [0.25, 0.25, 0.25, 0.25]) → Moving average (blur)# convolve(data, [1/2, 0, -1/2]) → 1st derivative estimate# convolve(data, [1, -2, 1]) → 2nd derivative estimatekernel=tuple(kernel)[::-1]n=len(kernel)padded_signal=chain(repeat(0,n-1),signal,repeat(0,n-1))windowed_signal=sliding_window(padded_signal,n)returnmap(sumprod,repeat(kernel),windowed_signal)defpolynomial_from_roots(roots):"""Compute a polynomial's coefficients from its roots.       (x - 5) (x + 4) (x - 3)  expands to:   x³ -4x² -17x + 60    """# polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]factors=zip(repeat(1),map(neg,roots))returnlist(reduce(convolve,factors,[1]))defpolynomial_eval(coefficients,x):"""Evaluate a polynomial at a specific value.    Computes with better numeric stability than Horner's method.    """# Evaluate x³ -4x² -17x + 60 at x = 5# polynomial_eval([1, -4, -17, 60], x=5) → 0n=len(coefficients)ifnotn:returntype(x)(0)powers=map(pow,repeat(x),reversed(range(n)))returnsumprod(coefficients,powers)defpolynomial_derivative(coefficients):"""Compute the first derivative of a polynomial.       f(x)  =  x³ -4x² -17x + 60       f'(x) = 3x² -8x  -17    """# polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]n=len(coefficients)powers=reversed(range(1,n))returnlist(map(mul,coefficients,powers))defsieve(n):"Primes less than n."# sieve(30) → 2 3 5 7 11 13 17 19 23 29ifn>2:yield2data=bytearray((0,1))*(n//2)forpiniter_index(data,1,start=3,stop=isqrt(n)+1):data[p*p:n:p+p]=bytes(len(range(p*p,n,p+p)))yield fromiter_index(data,1,start=3)deffactor(n):"Prime factors of n."# factor(99) → 3 3 11# factor(1_000_000_000_000_007) → 47 59 360620266859# factor(1_000_000_000_000_403) → 1000000000000403forprimeinsieve(isqrt(n)+1):whilenotn%prime:yieldprimen//=primeifn==1:returnifn>1:yieldndefis_prime(n):"Return True if n is prime."# is_prime(1_000_000_000_000_403) → Truereturnn>1andnext(factor(n))==ndeftotient(n):"Count of natural numbers up to n that are coprime to n."# https://mathworld.wolfram.com/TotientFunction.html# totient(12) → 4 because len([1, 5, 7, 11]) == 4forprimeinset(factor(n)):n-=n//primereturnn