Itertool関数¶

以下の関数は全て、イテレータを作成して返します。無限長のストリームのイテレータを返す関数もあり、この場合にはストリームを中断するような関数かループ処理から使用しなければなりません。

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

累計や加算ではない (func オプション引数で指定される) 2変数関数による累積結果を返すイテレータを作成します。

func が与えられた場合、2つの引数を取る関数でなければなりません。入力iterable の要素は、func が引数として取れる型を持ちます。(例えば、デフォルトの演算の加算では、要素はDecimal やFraction を含む、加算ができる型を持ちます。)

通常、出力される要素数は入力iterable の要素数と一致します。ただし、キーワード引数initial が指定されていれば、 iterable の要素は最初にinitial 値を持つため、出力は入力されたイテラブルよりも要素を1つ多く持ちます。

およそ次と等価です:

defaccumulate(iterable,func=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 120it=iter(iterable)total=initialifinitialisNone:try:total=next(it)exceptStopIteration:returnyieldtotalforelementinit:total=func(total,element)yieldtotal

func 引数の利用法はたくさんあります。最小値にするためにmin() を、最大値にするためにmax() を、積にするためにoperator.mul() を使うことができます。金利を累積し支払いを適用して償還表を作成することもできます。初期値をイテラブルに与えてfunc 引数で累積和を利用するだけで一階の漸化式 をモデル化できます:

>>>data=[3,4,6,2,1,9,0,7,5,8]>>>list(accumulate(data,operator.mul))# running product[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]>>>list(accumulate(data,max))# running maximum[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]# Amortize a 5% loan of 1000 with 4 annual payments of 90>>>cashflows=[1000,-90,-90,-90,-90]>>>list(accumulate(cashflows,lambdabal,pmt:bal*1.05+pmt))[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]# Chaotic recurrence relation https://en.wikipedia.org/wiki/Logistic_map>>>logistic_map=lambdax,_:r*x*(1-x)>>>r=3.8>>>x0=0.4>>>inputs=repeat(x0,36)# only the initial value is used>>>[format(x,'.2f')forxinaccumulate(inputs,logistic_map)]['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63', '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57', '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32', '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60']

最終的な累積値だけを返す類似の関数についてはfunctools.reduce() を見てください。

バージョン 3.2 で追加.

バージョン 3.3 で変更:オプションのfunc 引数が追加されました。

バージョン 3.8 で変更:オプションのinitial パラメータが追加されました。

itertools.chain(*iterables)¶

先頭の iterable の全要素を返し、次に2番目の iterable の全要素を返し、と全 iterable の要素を返すイテレータを作成します。連続したシーケンスを一つのシーケンスとして扱う場合に使用します。およそ次と等価です:

defchain(*iterables):# chain('ABC', 'DEF') --> A B C D E Fforitiniterables:forelementinit:yieldelement

classmethodchain.from_iterable(iterable)¶

chain() のためのもう一つのコンストラクタです。遅延評価される iterable 引数一つから連鎖した入力を受け取ります。この関数は、以下のコードとほぼ等価です:

deffrom_iterable(iterables):# chain.from_iterable(['ABC', 'DEF']) --> A B C D E Fforitiniterables:forelementinit:yieldelement

itertools.combinations(iterable,r)¶

入力iterable の要素からなる長さr の部分列を返します。

組合せ(combination)は入力iterable に応じた辞書式順序で出力されます。したがって、入力iterable がソートされていれば、出力される組合わせ(combination)タプルもソートされた順番で生成されます。

各要素は場所に基づいて一意に取り扱われ、値にはよりません。入力された要素がバラバラなら各組合せの中に重複した値は現れません。

およそ次と等価です:

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)

combinations() のコードはpermutations() のシーケンスから (入力プールでの位置に応じた順序で) 要素がソートされていないものをフィルターしたようにも表現できます:

defcombinations(iterable,r):pool=tuple(iterable)n=len(pool)forindicesinpermutations(range(n),r):ifsorted(indices)==list(indices):yieldtuple(pool[i]foriinindices)

返される要素の数は、0<=r<=n の場合は、n!/r!/(n-r)! で、r>n の場合は 0 です。

itertools.combinations_with_replacement(iterable,r)¶

入力iterable から、それぞれの要素が複数回現れることを許して、長さr の要素の部分列を返します。

組合せ(combination)は入力iterable に応じた辞書式順序で出力されます。したがって、入力iterable がソートされていれば、出力される組合わせ(combination)タプルもソートされた順番で生成されます。

要素は、値ではなく位置に基づいて一意に扱われます。ですから、入力の要素が一意であれば、生成された組合せも一意になります。

およそ次と等価です:

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)

combinations_with_replacement() のコードは、product() の部分列から、要素が (入力プールの位置に従って) ソートされた順になっていない項目をフィルタリングしたものとしても表せます:

defcombinations_with_replacement(iterable,r):pool=tuple(iterable)n=len(pool)forindicesinproduct(range(n),repeat=r):ifsorted(indices)==list(indices):yieldtuple(pool[i]foriinindices)

返される要素の数は、n>0 のとき(n+r-1)!/r!/(n-1)! です。

バージョン 3.1 で追加.

itertools.compress(data,selectors)¶

data の要素からselectors の対応する要素がTrue と評価されるものだけをフィルタしたイテレータを作ります。data とselectors のいずれかが尽きたときに止まります。およそ次と等価です:

defcompress(data,selectors):# compress('ABCDEF', [1,0,1,0,1,1]) --> A C E Freturn(dford,sinzip(data,selectors)ifs)

バージョン 3.1 で追加.

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

数start で始まる等間隔の値を返すイテレータを作成します。map() に渡して連続したデータを生成するのによく使われます。 また、zip() に連続した番号を追加するのにも使われます。 およそ次と等価です:

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

浮動小数点数でカウントするときは(start+step*iforiincount()) のように掛け算を使ったコードに置き換えたほうが正確にできることがあります。

バージョン 3.1 で変更:step 引数が追加され、非整数の引数が許されるようになりました。

itertools.cycle(iterable)¶

iterable から要素を取得し、そのコピーを保存するイテレータを作成します。iterable の全要素を返すと、セーブされたコピーから要素を返します。これを無限に繰り返します。およそ次と等価です:

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

cycle() は大きなメモリ領域を使用します。使用するメモリ量は iterable の大きさに依存します。

itertools.dropwhile(predicate,iterable)¶

predicate (述語) が真である間は要素を飛ばし、その後は全ての要素を返すイテレータを作成します。このイテレータは、predicate が最初に偽になるまで全く 要素を返さないため、要素を返し始めるまでに長い時間がかかる場合があります。およそ次と等価です:

defdropwhile(predicate,iterable):# dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1iterable=iter(iterable)forxiniterable:ifnotpredicate(x):yieldxbreakforxiniterable:yieldx

itertools.filterfalse(predicate,iterable)¶

iterable から predicate がFalse となる要素だけを返すイテレータを作成します。predicate がNone の場合、偽の要素だけを返します。およそ次と等価です:

deffilterfalse(predicate,iterable):# filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8ifpredicateisNone:predicate=boolforxiniterable:ifnotpredicate(x):yieldx

itertools.groupby(iterable,key=None)¶

同じキーをもつような要素からなるiterable 中のグループに対して、キーとグループを返すようなイテレータを作成します。key は各要素に対するキー値を計算する関数です。キーを指定しない場合やNone にした場合、key 関数のデフォルトは恒等関数になり要素をそのまま返します。通常、iterable は同じキー関数でソート済みである必要があります。

groupby() の操作は Unix のuniq フィルターと似ています。 key 関数の値が変わるたびに休止または新しいグループを生成します (このために通常同じ key 関数でソートしておく必要があるのです)。この動作は SQL の入力順に関係なく共通の要素を集約する GROUP BY とは違います。

返されるグループはそれ自体がイテレータで、groupby() とiterable を共有しています。もととなるiterable を共有しているため、groupby() オブジェクトの要素取り出しを先に進めると、それ以前の要素であるグループは見えなくなってしまいます。従って、データが後で必要な場合にはリストの形で保存しておく必要があります:

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

groupby() はおよそ次と等価です:

classgroupby:# [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B# [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC Ddef__init__(self,iterable,key=None):ifkeyisNone:key=lambdax:xself.keyfunc=keyself.it=iter(iterable)self.tgtkey=self.currkey=self.currvalue=object()def__iter__(self):returnselfdef__next__(self):self.id=object()whileself.currkey==self.tgtkey:self.currvalue=next(self.it)# Exit on StopIterationself.currkey=self.keyfunc(self.currvalue)self.tgtkey=self.currkeyreturn(self.currkey,self._grouper(self.tgtkey,self.id))def_grouper(self,tgtkey,id):whileself.idisidandself.currkey==tgtkey:yieldself.currvaluetry:self.currvalue=next(self.it)exceptStopIteration:returnself.currkey=self.keyfunc(self.currvalue)

itertools.islice(iterable,stop)¶

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

iterable から要素を選択して返すイテレータを作成します。start が0でない場合、iterable の要素は start に達するまでスキップされます。その後、要素が順に返されます。

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,stop,step=s.startor0,s.stoporsys.maxsize,s.stepor1it=iter(range(start,stop,step))try:nexti=next(it)exceptStopIteration:# Consume *iterable* up to the *start* position.fori,elementinzip(range(start),iterable):passreturntry:fori,elementinenumerate(iterable):ifi==nexti:yieldelementnexti=next(it)exceptStopIteration:# Consume to *stop*.fori,elementinzip(range(i+1,stop),iterable):pass

start がNone の場合、イテレーションは0から始まります。step がNone の場合、ステップはデフォルトの1になります。

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.

およそ次と等価です:

defpairwise(iterable):# pairwise('ABCDEFG') --> AB BC CD DE EF FGa,b=tee(iterable)next(b,None)returnzip(a,b)

バージョン 3.10 で追加.

itertools.permutations(iterable,r=None)¶

iterable の要素からなる長さr の順列 (permutation) を連続的に返します。

r が指定されない場合やNone の場合、r はデフォルトでiterable の長さとなり、可能な最長の順列の全てが生成されます。

順列(permutation)は入力iterable に応じた辞書式順序で出力されます。したがって、入力iterable がソートされていれば、出力される組合わせタプルもソートされた順番で生成されます。

要素は値ではなく位置に基づいて一意的に扱われます。したがって入力された要素が全て異なっている場合、それぞれの順列に重複した要素が現れないことになります。

およそ次と等価です:

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

permutations() のコードはproduct() の列から重複 (それらは入力プールの同じ位置から取られたものです) を除くようフィルタしたものとしても表現できます:

defpermutations(iterable,r=None):pool=tuple(iterable)n=len(pool)r=nifrisNoneelserforindicesinproduct(range(n),repeat=r):iflen(set(indices))==r:yieldtuple(pool[i]foriinindices)

返される要素の数は、0<=r<=n の場合n!/(n-r)! で、r>n の場合は 0 です。

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

入力イテラブルのデカルト積です。

ジェネレータ式の入れ子になった for ループとおよそ等価です。たとえばproduct(A,B) は((x,y)forxinAforyinB) と同じものを返します。

入れ子ループは走行距離計と同じように右端の要素がイテレーションごとに更新されていきます。このパターンは辞書式順序を作り出し、入力のイテレート可能オブジェクトたちがソートされていれば、直積タプルもソートされた順に出てきます。

イテラブル自身との直積を計算するためには、オプションのrepeat キーワード引数に繰り返し回数を指定します。たとえばproduct(A,repeat=4) はproduct(A,A,A,A) と同じ意味です。

この関数は以下のコードとおよそ等価ですが、実際の実装ではメモリ中に中間結果を作りません:

defproduct(*args,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 111pools=[tuple(pool)forpoolinargs]*repeatresult=[[]]forpoolinpools:result=[x+[y]forxinresultforyinpool]forprodinresult:yieldtuple(prod)

product() は動作する前に、入力のイテラブルを完全に読み取り、直積を生成するためにメモリ内に値を蓄えます。したがって、入力が有限の場合に限り有用です。

itertools.repeat(object[,times])¶

繰り返しobject を返すイテレータを作成します。times 引数を指定しなければ、無限に値を返し続けます。map() の引数にして、呼び出された関数に同じ引数を渡すのに使います。またzip() と使って、タプルの変わらない部分を作ります。

およそ次と等価です:

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

repeat はmap やzip に定数のストリームを与えるためによく利用されます:

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

itertools.starmap(function,iterable)¶

iterable の要素を引数として funtion を計算するイテレータを作成します。 function の引数が一つの iterable からタプルに既にグループ化されている (データが "zip済み") 場合、map() の代わりに使用します。map() とstarmap() の違いはfunction(a,b) とfunction(*c) の差に似ています。およそ次と等価です:

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

itertools.takewhile(predicate,iterable)¶

predicate が真である限り iterable から要素を返すイテレータを作成します。およそ次と等価です:

deftakewhile(predicate,iterable):# takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4forxiniterable:ifpredicate(x):yieldxelse:break

itertools.tee(iterable,n=2)¶

一つの iterable からn 個の独立したイテレータを返します。

以下の Python コードはtee がすることについての理解を助けるでしょう (ただし実際の実装はより複雑で、下層のFIFO キューを一つしか使いませんが)。

およそ次と等価です:

deftee(iterable,n=2):it=iter(iterable)deques=[collections.deque()foriinrange(n)]defgen(mydeque):whileTrue:ifnotmydeque:# when the local deque is emptytry:newval=next(it)# fetch a new value andexceptStopIteration:returnfordindeques:# load it to all the dequesd.append(newval)yieldmydeque.popleft()returntuple(gen(d)fordindeques)

一度tee() でイテレータを分割すると、もとのiterable を他で使ってはいけません。さもなければ、tee() オブジェクトの知らない間にiterable が先の要素に進んでしまうことになります。

tee() イテレーターはスレッドセーフではありません。同じtee() から生じた複数のイテレータを同時に使用すると、元のイテラブルがスレッドセーフであっても、RuntimeError が発生することがあります。

tee() はかなり大きなメモリ領域を使用するかもしれません (使用するメモリ量はiterableの大きさに依存します)。一般には、一つのイテレータが他のイテレータよりも先にほとんどまたは全ての要素を消費するような場合には、tee() よりもlist() を使った方が高速です。

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

各 iterable の要素をまとめるイテレータを作成します。iterable の長さが違う場合、足りない値はfillvalue で埋められます。最も長い itarable が尽きるまでイテレーションします。およそ次と等価です:

defzip_longest(*args,fillvalue=None):# zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-iterators=[iter(it)foritinargs]num_active=len(iterators)ifnotnum_active:returnwhileTrue:values=[]fori,itinenumerate(iterators):try:value=next(it)exceptStopIteration:num_active-=1ifnotnum_active:returniterators[i]=repeat(fillvalue)value=fillvaluevalues.append(value)yieldtuple(values)

iterables の1つが無限になりうる場合zip_longest() は呼び出し回数を制限するような何かでラップしなければいけません(例えばislice() ortakewhile())。fillvalue は指定しない場合のデフォルトはNone です。

Itertools レシピ¶

この節では、既存の itertools を素材としてツールセットを拡張するためのレシピを示します。

下記のレシピを包含した広範なレシピ集は Python Package Index 上のmore-itertools project からインストールできます。

pipinstallmore-itertools

iterable 全体を一度にメモリ上に置くよりも、要素を一つづつ処理する方がメモリ効率上の有利さを保てます。関数形式のままツールをリンクしてゆくと、コードのサイズを減らし、一時変数を減らす助けになります。インタプリタのオーバヘッドをもたらす for ループやジェネレータ を使わずに、 "ベクトル化された" ビルディングブロックを使うと、高速な処理を実現できます。

deftake(n,iterable):"Return first n items of the iterable as a list"returnlist(islice(iterable,n))defprepend(value,iterator):"Prepend a single value in front of an iterator"# prepend(1, [2, 3, 4]) -> 1 2 3 4returnchain([value],iterator)deftabulate(function,start=0):"Return function(0), function(1), ..."returnmap(function,count(start))deftail(n,iterable):"Return an iterator over the last n items"# tail(3, 'ABCDEFG') --> E F Greturniter(collections.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:# feed the entire iterator into a zero-length dequecollections.deque(iterator,maxlen=0)else:# advance to the empty slice starting at position nnext(islice(iterator,n,n),None)defnth(iterable,n,default=None):"Returns the nth item or a default value"returnnext(islice(iterable,n,None),default)defall_equal(iterable):"Returns True if all the elements are equal to each other"g=groupby(iterable)returnnext(g,True)andnotnext(g,False)defquantify(iterable,pred=bool):"Count how many times the predicate is true"returnsum(map(pred,iterable))defpad_none(iterable):"""Returns the sequence elements and then returns None indefinitely.    Useful for emulating the behavior of the built-in map() function.    """returnchain(iterable,repeat(None))defncycles(iterable,n):"Returns the sequence elements n times"returnchain.from_iterable(repeat(tuple(iterable),n))defdotproduct(vec1,vec2):returnsum(map(operator.mul,vec1,vec2))defconvolve(signal,kernel):# See:  https://betterexplained.com/articles/intuitive-convolution/# convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Moving average (blur)# convolve(data, [1, -1]) --> 1st finite difference (1st derivative)# convolve(data, [1, -2, 1]) --> 2nd finite difference (2nd derivative)kernel=tuple(kernel)[::-1]n=len(kernel)window=collections.deque([0],maxlen=n)*nforxinchain(signal,repeat(0,n-1)):window.append(x)yieldsum(map(operator.mul,kernel,window))defflatten(list_of_lists):"Flatten one level of nesting"returnchain.from_iterable(list_of_lists)defrepeatfunc(func,times=None,*args):"""Repeat calls to func with specified arguments.    Example:  repeatfunc(random.random)    """iftimesisNone:returnstarmap(func,repeat(args))returnstarmap(func,repeat(args,times))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 DEFargs=[iter(iterable)]*nifincomplete=='fill':returnzip_longest(*args,fillvalue=fillvalue)ifincomplete=='strict':returnzip(*args,strict=True)ifincomplete=='ignore':returnzip(*args)else:raiseValueError('Expected fill, strict, or ignore')deftriplewise(iterable):"Return overlapping triplets from an iterable"# triplewise('ABCDEFG') -> ABC BCD CDE DEF EFGfor(a,_),(b,c)inpairwise(pairwise(iterable)):yielda,b,cdefsliding_window(iterable,n):# sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFGit=iter(iterable)window=collections.deque(islice(it,n),maxlen=n)iflen(window)==n:yieldtuple(window)forxinit:window.append(x)yieldtuple(window)defroundrobin(*iterables):"roundrobin('ABC', 'D', 'EF') --> A D E B F C"# Recipe credited to George Sakkisnum_active=len(iterables)nexts=cycle(iter(it).__next__foritiniterables)whilenum_active:try:fornextinnexts:yieldnext()exceptStopIteration:# Remove the iterator we just exhausted from the cycle.num_active-=1nexts=cycle(islice(nexts,num_active))defpartition(pred,iterable):"Use a predicate to partition entries into false entries and true entries"# partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9t1,t2=tee(iterable)returnfilterfalse(pred,t1),filter(pred,t2)defbefore_and_after(predicate,it):""" Variant of takewhile() that allows complete        access to the remainder of the iterator.        >>> it = iter('ABCdEfGhI')        >>> all_upper, remainder = before_and_after(str.isupper, it)        >>> ''.join(all_upper)        'ABC'        >>> ''.join(remainder)     # takewhile() would lose the 'd'        'dEfGhI'        Note that the first iterator must be fully        consumed before the second iterator can        generate valid results.    """it=iter(it)transition=[]deftrue_iterator():foreleminit:ifpredicate(elem):yieldelemelse:transition.append(elem)returndefremainder_iterator():yield fromtransitionyield fromitreturntrue_iterator(),remainder_iterator()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(operator.getitem,repeat(seq),slices)defpowerset(iterable):"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))defunique_everseen(iterable,key=None):"List unique elements, preserving order. Remember all elements ever seen."# unique_everseen('AAAABBBCCDAABBB') --> A B C D# unique_everseen('ABBCcAD', str.lower) --> A B C Dseen=set()seen_add=seen.addifkeyisNone:forelementinfilterfalse(seen.__contains__,iterable):seen_add(element)yieldelementelse:forelementiniterable:k=key(element)ifknotinseen:seen_add(k)yieldelementdefunique_justseen(iterable,key=None):"List unique elements, preserving order. Remember only the element just seen."# unique_justseen('AAAABBBCCDAABBB') --> A B C D A B# unique_justseen('ABBCcAD', str.lower) --> A B C A Dreturnmap(next,map(operator.itemgetter(1),groupby(iterable,key)))defiter_except(func,exception,first=None):""" Call a function repeatedly until an exception is raised.    Converts a call-until-exception interface to an iterator interface.    Like builtins.iter(func, sentinel) but uses an exception instead    of a sentinel to end the loop.    Examples:        iter_except(functools.partial(heappop, h), IndexError)   # priority queue iterator        iter_except(d.popitem, KeyError)                         # non-blocking dict iterator        iter_except(d.popleft, IndexError)                       # non-blocking deque iterator        iter_except(q.get_nowait, Queue.Empty)                   # loop over a producer Queue        iter_except(s.pop, KeyError)                             # non-blocking set iterator    """try:iffirstisnotNone:yieldfirst()# For database APIs needing an initial cast to db.first()whileTrue:yieldfunc()exceptexception:passdeffirst_true(iterable,default=False,pred=None):"""Returns the first true value in the iterable.    If no true value is found, returns *default*    If *pred* is not None, returns the first item    for which pred(item) is true.    """# 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(pred,iterable),default)defrandom_product(*args,repeat=1):"Random selection from itertools.product(*args, **kwds)"pools=[tuple(pool)forpoolinargs]*repeatreturntuple(map(random.choice,pools))defrandom_permutation(iterable,r=None):"Random selection from itertools.permutations(iterable, r)"pool=tuple(iterable)r=len(pool)ifrisNoneelserreturntuple(random.sample(pool,r))defrandom_combination(iterable,r):"Random selection from itertools.combinations(iterable, r)"pool=tuple(iterable)n=len(pool)indices=sorted(random.sample(range(n),r))returntuple(pool[i]foriinindices)defrandom_combination_with_replacement(iterable,r):"Random selection from itertools.combinations_with_replacement(iterable, r)"pool=tuple(iterable)n=len(pool)indices=sorted(random.choices(range(n),k=r))returntuple(pool[i]foriinindices)defnth_combination(iterable,r,index):"Equivalent to list(combinations(iterable, r))[index]"pool=tuple(iterable)n=len(pool)ifr<0orr>n:raiseValueErrorc=1k=min(r,n-r)foriinrange(1,k+1):c=c*(n-k+i)//iifindex<0:index+=cifindex<0orindex>=c:raiseIndexErrorresult=[]whiler:c,n,r=c*r//n,n-1,r-1whileindex>=c:index-=cc,n=c*(n-r)//n,n-1result.append(pool[-1-n])returntuple(result)