Sklandus nereguliarus sąrašų sąrašas

Taip, žinau, kad šis klausimas buvo svarstomas anksčiau ( čia , čia , čia ), bet, kiek žinau, visi sprendimai, išskyrus vieną, palieka šį sąrašą:

 L = [[[1, 2, 3], [4, 5]], 6] 

Jei pageidaujate rezultato

 [1, 2, 3, 4, 5, 6] 

O gal net geriau, iteratorius. Šiame sprendime aptinkamas vienintelis sprendimas, kuris parodė, kad veikia savavališkai.

 def flatten(x): result = [] for el in x: if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result flatten(L) 

Ar tai geriausias modelis? Ar kažką praleidau? Bet kokios problemos?

368
29 янв. nustatytas telliott99 sausio 29 d 2010-01-29 01:15 '10 ne 1:15 2010-01-29 01:15
ответ 41 atsakymas
  • 1
  • 2

Naudojant generatoriaus funkcijas, jūsų pavyzdys gali būti šiek tiek lengviau skaitomas ir greičiausiai pagerintas.

Python 2

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, basestring): for sub in flatten(el): yield sub else: yield el 

Aš naudoju Iterable ABC , pridėtą 2.6.

Python 3

„Python 3“ basestring nebėra, bet jūs galite naudoti str ir bytes seką, kad gautumėte tą patį efektą.

Operatoriaus yield from grąžina elementą iš generatoriaus vienu metu. Ši sintaksė perduoti subgeneratoriui buvo įtraukta į 3.3

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): yield from flatten(el) else: yield el 
324
29 янв. Atsakymas pateikiamas Cristian 29 jan. 2010-01-29 01:35 '10 ne 1:35 2010-01-29 01:35

Mano sprendimas:

 def flatten(x): if isinstance(x, collections.Iterable): return [a for i in x for a in flatten(i)] else: return [x] 
border=0

Šiek tiek glaustesnis, bet beveik tas pats.

47
29 янв. Josh Lee atsakymas, pateiktas sausio 29 d 2010-01-29 01:34 '10 ne 1:34 2010-01-29 01:34

Ne rekursinio tirpalo @unutbu generatorius versija, @Andrew prašymu komentare:

 def genflat(l, ltypes=collections.Sequence): l = list(l) i = 0 while i < len(l): while isinstance(l[i], ltypes): if not l[i]: l.pop(i) i -= 1 break else: l[i:i + 1] = l[i] yield l[i] i += 1 

Šiek tiek supaprastinta šios generatoriaus versija:

 def genflat(l, ltypes=collections.Sequence): l = list(l) while l: while l and isinstance(l[0], ltypes): l[0:1] = l[0] if l: yield l.pop(0) 
33
29 янв. Alex Martelli atsakymas dėl sausio 29 d 2010-01-29 03:27 '10 at 3:27 2010-01-29 03:27

Generatorius, naudojant rekursiją ir antis spausdinimą (atnaujintas „Python 3“):

 def flatten(L): for item in L: try: yield from flatten(item) except TypeError: yield item list(flatten([[[1, 2, 3], [4, 5]], 6])) >>>[1, 2, 3, 4, 5, 6] 
32
24 янв. Atsakymas dansalmo suteiktas sausio 24 d 2013-01-24 02:04 '13, 02:04 2013-01-24 02:04

Ši flatten versija išskiria python rekursijos ribą (ir todėl veikia su savavališkai giliai įterptais iteratoriais). Tai generatorius, kuris gali apdoroti eilutes ir savavališkus iteratus (netgi begalinius).

 import itertools as IT import collections def flatten(iterable, ltypes=collections.Iterable): remainder = iter(iterable) while True: first = next(remainder) if isinstance(first, ltypes) and not isinstance(first, basestring): remainder = IT.chain(first, remainder) else: yield first 

Štai keletas pavyzdžių, rodančių jo naudojimą:

 print(list(IT.islice(flatten(IT.repeat(1)),10))) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3), {10,20,30}, 'foo bar'.split(), IT.repeat(1),)),10))) # [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1] print(list(flatten([[1,2,[3,4]]]))) # [1, 2, 3, 4] seq = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9)) print(list(flatten(seq))) # ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H', # 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P', # 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', # 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8] 

Nors flatten gali tvarkyti begalinius generatorius, jis negali tvarkyti begalinio lizdo:

 def infinitely_nested(): while True: yield IT.chain(infinitely_nested(), IT.repeat(1)) print(list(IT.islice(flatten(infinitely_nested()), 10))) # hangs 
25
29 янв. atsakymas duotas unutbu Jan 29 2010-01-29 01:42 '10 ne 1:42 2010-01-29 01:42

Čia yra mano funkcinė rekursyvaus anti-aliasing versija, kuri apdoroja ir eilutes, ir sąrašus, ir leidžia naudoti bet kokį pozicioninių argumentų derinį. Grąžina generatorių, kuris sukuria visą seką, arg arg:

 flatten = lambda *n: (e for a in n for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,))) 

Naudoti:

 l1 = ['a', ['b', ('c', 'd')]] l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)] print list(flatten(l1, -2, -1, l2)) ['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 
21
23 марта '11 в 20:42 2011-03-23 20:42 atsakymą pateikė „ mintabias“ kovo 23 d., 11 d., 20:42, 2011-03-23 ​​20:42

Čia yra dar vienas įdomesnis atsakymas ...

 import re def Flatten(TheList): a = str(TheList) b,crap = re.subn(r'[\[,\]]', ' ', a) c = b.split() d = [int(x) for x in c] return(d) 

Iš esmės ji konvertuoja įdėtą sąrašą į eilutę, naudoja įprastą išraišką, kad pabrėžtų įdėtą sintaksę, ir tada konvertuoja rezultatą atgal į (suplotas) sąrašą.

13
14 янв. atsakymas duotas moliui 14 sausio. 2011-01-14 21:31 '11, 21:31, 2011-01-14 21:31
 def flatten(xs): res = [] def loop(ys): for i in ys: if isinstance(i, list): loop(i) else: res.append(i) loop(xs) return res 
9
04 янв. atsakymas pateikiamas kev 04 jan. 2011-01-04 07:29 '11 at 7:29 2011-01-04 07:29

Galite naudoti deepflatten iš trečiosios šalies deepflatten paketo:

 >>> from iteration_utilities import deepflatten >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(deepflatten(L)) [1, 2, 3, 4, 5, 6] >>> list(deepflatten(L, types=list)) # only flatten "inner" lists [1, 2, 3, 4, 5, 6] 

Tai yra iteratorius, todėl jį reikia kartoti (pvz., Perpildę jį list arba naudodami jį kilpoje). Viduje jis naudoja iteracinį metodą, o ne rekursinį metodą, ir jis rašomas kaip C išplėtimas, todėl jis gali būti greitesnis nei grynas python metodas:

 >>> %timeit list(deepflatten(L)) 12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(deepflatten(L, types=list)) 8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(flatten(L)) # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381 86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(flatten(L)) # Josh Lee - https://stackoverflow.com/a/2158522/5393381 107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(genflat(L, list)) # Alex Martelli - https://stackoverflow.com/a/2159079/5393381 23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

Aš esu bibliotekos iteration_utilities autorius.

7
29 июля '17 в 17:01 2017-07-29 17:01 Atsakymą pateikė „ MSeifert“ liepos 17 d. 17 val. 17:01 2017-07-29 17:01

Tai buvo smagu pabandyti sukurti funkciją, kuri galėtų išlyginti nereguliarų Python sąrašą, tačiau, žinoma, tai yra Pythonas (įdomus programavimas). Toliau nurodytas generatorius veikia gana gerai, kai kurios išlygos:

 def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable 

Jis bytearray duomenų tipus, kurių gali prireikti vien tik (pvz., bytearray , bytes ir str objektai). Be to, kodas grindžiamas tuo, kad iteratoriaus užklausa, gauta iš netinkamo, padidina TypeError reikšmę.

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> 

Redaguoti:

Nesutinku su ankstesniu įgyvendinimu. Problema yra ta, kad neturėtumėte išlyginti dalykų, kurie nėra įprasti. Tai paini ir suteikia klaidingą nuomonę apie šį argumentą.

 >>> list(flatten(123)) [123] >>> 

Kitas generatorius yra beveik toks pat, kaip ir pirmasis, bet jis neturi jokios problemos bandydamas išlyginti nesunaikinamą objektą. Tai nepavyksta, kaip tikėtasi, kai jam priskirtas netinkamas argumentas.

 def flatten(iterable): for item in iterable: try: yield from flatten(item) except TypeError: yield item 

Generatoriaus bandymai puikiai atitinka pateiktą sąrašą. Tačiau naujas kodas sukels TypeError kai jam bus priskirtas nesunaikinamas objektas. Toliau pateikiami naujo elgesio pavyzdžiai.

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> list(flatten(123)) Traceback (most recent call last): File "<pyshell#32>", line 1, in <module> list(flatten(123)) File "<pyshell#27>", line 2, in flatten for item in iterable: TypeError: 'int' object is not iterable >>> 
6
25 июля '13 в 23:46 2013-07-25 23:46 atsakymą pateikė Noctis Skytower liepos 25 d., 13 val. 11:46 2013-07-25 23:46

Čia yra paprasta funkcija, kuri suvienodina savavališko gylio sąrašus. Nėra rekursijos, kad būtų išvengta.

 from copy import deepcopy def flatten_list(nested_list): """Flatten an arbitrarily nested list, without recursion (to avoid stack overflows). Returns a new list, the original list is unchanged. >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]])) [1, 2, 3, 4, 5] >> list(flatten_list([[1, 2], 3])) [1, 2, 3] """ nested_list = deepcopy(nested_list) while nested_list: sublist = nested_list.pop(0) if isinstance(sublist, list): nested_list = sublist + nested_list else: yield sublist 
4
10 дек. Atsakymą pateikė Wilfred Hughes gruodžio 10 d. 2013-12-10 15:56 '13, 15:56, 2013-12-10 15:56

Nors buvo pasirinktas elegantiškas ir labai pythoninis atsakymas, pateiksiu tik sprendimą dėl peržiūros:

 def flat(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flat(i)) else: ret.append(i) return ret 

Pasakykite mums, ar šis kodas yra geras ar blogas?

4
08 марта '11 в 1:32 2011-03-08 01:32 atsakymas pateikiamas Xolve kovo 8 d. 11 d. 1:32 2011-03-08 01:32

Norėčiau paprastų atsakymų. Nėra generatorių. Apribojimai rekursija arba rekursija. Tiesiog iteracija:

 def flatten(TheList): listIsNested = True while listIsNested: #outer loop keepChecking = False Temp = [] for element in TheList: #inner loop if isinstance(element,list): Temp.extend(element) keepChecking = True else: Temp.append(element) listIsNested = keepChecking #determine if outer loop exits TheList = Temp[:] return TheList 

Tai veikia su dviem sąrašais: vidine kilpa ir išorine kilpa.

Vidinis ciklo ciklas kartojamas per sąrašą. Jei jis suranda sąrašo elementą, jis (1) naudoja list.extend (), kad išlygintų lygį, kuriuo naudojamas vienas lizdų lygis, ir (2) perjungia nuolatinį tikrinimą į tikrąjį. Keepchecking naudojamas valdyti išorinį, o ciklas. Jei išorinė kilpa yra teisinga, ji pradeda vidinę kilpą kitam praėjimui.

Šie leidimai tęsiami tol, kol bus rasti daugiau įdėtų sąrašų. Kai pasibaigia leidimas, kur niekas nerastas, keepChecking niekada neveikia tiesai, o tai reiškia, kad listIsNested lieka netikras ir išorinis, o ciklas išeina.

Tada grąžinamas vienodas sąrašas.

Testavimas

 flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]]) 

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

4
13 янв. atsakymas duotas moliui 13 sausio. 2011-01-13 06:19 '11, 6:19, 2011-01-13 06:19

Esu nustebęs, kad niekas apie tai negalvojo. Sunaikinta rekursija. Negaliu gauti rekursinių atsakymų, kuriuos pasiūlė pažengę žmonės. Bet kokiu atveju, čia yra mano bandymas. rezervacija yra labai specifinė OP naudojimo atveju

 import re L = [[[1, 2, 3], [4, 5]], 6] flattened_list = re.sub("[\[\]]", "", str(L)).replace(" ", "").split(",") new_list = list(map(int, flattened_list)) print(new_list) 

išeiti:

 [1, 2, 3, 4, 5, 6] 
2
14 нояб. atsakymas pateikiamas Zion 14 lapkričio. 2015-11-14 08:59 '15, 8:59, 2015-11-14 08:59

Nematau visų čia jau pateiktų atsakymų, bet čia yra vienas linijinis laivas, kurį aš atėjau, skolindamasis iš lisp pirmuoju būdu ir tvarkydamas poilsio sąrašą

 def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l] 

čia yra vienas paprastas ir ne labai paprastas atvejis -

 >>> flatten([1,[2,3],4]) [1, 2, 3, 4] >>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30]) [1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] >>> 
2
08 апр. atsakymas pateikiamas Shreyas 08 balandžio. 2016-04-08 16:24 '16 at 16:24 pm 2016-04-08 16:24

Čia pateikiamas compiler.ast.flatten įgyvendinimas 2.7.5:

 def flatten(seq): l = [] for elt in seq: t = type(elt) if t is tuple or t is list: for elt2 in flatten(elt): l.append(elt2) else: l.append(elt) return l 

Yra geresnių ir greitesnių metodų (jei jau esate čia, jau matėte juos)

Taip pat atkreipkite dėmesį:

Netinkamas nuo 2.6 versijos: kompiliatoriaus paketas buvo pašalintas „Python 3“.

2
27 авг. atsakymas pateikiamas pradyunsg 27 rug . 2013-08-27 16:05 '13, 16:05, 2013-08-27 16:05

visiškai nulaužtas, bet manau, kad jis veiks (priklausomai nuo jūsų duomenų tipo)

 flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list))) 
1
28 мая '14 в 20:54 2014-05-28 20:54 Jorano Beasley atsakymas gegužės 28 d., 14 val. 20:54 2014-05-28 20:54

Naudojant itertools.chain :

 import itertools from collections import Iterable def list_flatten(lst): flat_lst = [] for item in itertools.chain(lst): if isinstance(item, Iterable): item = list_flatten(item) flat_lst.extend(item) else: flat_lst.append(item) return flat_lst 

Arba be privalomojo:

 def flatten(q, final): if not q: return if isinstance(q, list): if not isinstance(q[0], list): final.append(q[0]) else: flatten(q[0], final) flatten(q[1:], final) else: final.append(q) 
1
27 февр. atsakymą pateikė Saksamas Varma , vasario 27 d. 2015-02-27 05:38 '15, 5:38, 2015-02-27 05:38

Naudojau rekursiją, kad išsiaiškintumėte įdėtąjį sąrašą bet kokiu gyliu

 def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y): ''' apply function: combiner to a nested list element by element(treated as flatten list) ''' current_value=init for each_item in nlist: if isinstance(each_item,list): current_value =combine_nlist(each_item,current_value,combiner) else: current_value = combiner(current_value,each_item) return current_value 

Taigi, apibrėžus „comb_nlist“ funkciją, paprasta naudoti šią funkciją lygiavimui. Arba galite sujungti ją į vieną funkciją. Man patinka mano sprendimas, nes jis gali būti taikomas bet kuriam įdėtam sąrašui.

 def flatten_nlist(nlist): return combine_nlist(nlist,[],lambda x,y:x+[y]) 

rezultatas

 In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10]) Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
1
01 окт. atsakymas suteiktas freeyoung Oct 01 2014-10-01 01:02 '14 at 1:02 2014-10-01 01:02

Nesu tikras, kad tai būtinai yra greitesnė ar efektyvesnė, bet tai darau:

 def flatten(lst): return eval('[' + str(lst).replace('[', '').replace(']', '') + ']') L = [[[1, 2, 3], [4, 5]], 6] print(flatten(L)) 

flatten funkcija paverčia sąrašą į eilutę, ištraukia visus kvadratinius skliaustelius, susieja kvadratinius skliaustus prie galų ir grąžina juos atgal į sąrašą.

Nors, jei žinotumėte, kad jūsų sąraše eilutėse turėsite kvadratinių skliaustų, pvz., [[1, 2], "[3, 4] and [5]"] , jums reikės ką nors padaryti.

1
13 мая '17 в 5:32 2017-05-13 05:32 atsakymas į diligarą gegužės 13 d., 17 val

Žinau, kad jau yra daug puikių atsakymų, bet norėjau pridėti atsakymą, kuriame naudojamas funkcinis programavimo metodas. Šiame atsakyme naudoju dvigubą rekursiją:

 def flatten_list(seq): if not seq: return [] elif isinstance(seq[0],list): return (flatten_list(seq[0])+flatten_list(seq[1:])) else: return [seq[0]]+flatten_list(seq[1:]) print(flatten_list([1,2,[3,[4],5],[6,7]])) 

išeiti:

 [1, 2, 3, 4, 5, 6, 7] 
1
03 окт. Leo wahyd atsakymas, pateiktas spalio 3 d 2016-10-03 18:46 '16 at 18:46 2016-10-03 18:46

Lengviausias būdas yra naudoti „ morph“ biblioteką naudojant „ pip install morph .

Kodas:

 import morph list = [[[1, 2, 3], [4, 5]], 6] flattened_list = morph.flatten(list) # returns [1, 2, 3, 4, 5, 6] 
1
15 дек. Atsakymas pateikiamas YPCrumble 15 d. 2015-12-15 23:03 '15, 23:03 2015-12-15 23:03

Čia yra dar vienas „py2“ metodas, nesu tikras, kad jo greičiausias ar elegantiškiausias ir saugiausias ...

 from collections import Iterable from itertools import imap, repeat, chain def flat(seqs, ignore=(int, long, float, basestring)): return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

Jis gali ignoruoti bet kokį konkretų (ar išvestinį) tipą, kurį jums reikia, jis grąžina iteratorių, todėl galite jį konvertuoti į bet kurį konkretų konteinerį, pvz., Sąrašą, paketą, diktuoti arba tiesiog jį sunaikinti, kad sumažintumėte atmintį, geriau ar blogiau. , ji gali tvarkyti pradinius nesugriaunamus objektus, tokius kaip int ...

Atkreipkite dėmesį, kad didžioji dalis sunkiųjų kėlimo atliekama C, nes, kiek žinau, tai yra, kaip yra įgyvendinami, todėl rekursyvus, AFAIK neapsiriboja python rekursijos gyliu, nes funkcijų skambučiai įvyksta C, nors tai nereiškia, kad jūs ribojate atminties, ypač OS X, kur jo krūvos dydis šiandien yra sunkus (OS X Mavericks) ...

yra šiek tiek greitesnis metodas, tačiau mažiau nešiojamas metodas, naudokite jį tik tada, jei galite daryti prielaidą, kad pagrindiniai įvesties elementai gali būti aiškiai apibrėžti kitaip, gausite neribotą rekursiją, o OS X su riboto dydžio steku greitai panaikins segmentavimo klaidą. .

 def flat(seqs, ignore={int, long, float, str, unicode}): return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

čia mes naudojame rinkinius, kad patikrintume tipą, todėl norint patikrinti, ar elementas turėtų būti ignoruojamas, būtina, kad būtų ignoruojamas O (1) ir O (tipų skaičius), nors, žinoma, ignoruojama bet kokia reikšmė su išvestu apibrėžto tipo tipu, todėl nepavyks, todėl naudojant str , unicode naudoja jį atsargiai ...

Bandymai:

 import random def test_flat(test_size=2000): def increase_depth(value, depth=1): for func in xrange(depth): value = repeat(value, 1) return value def random_sub_chaining(nested_values): for values in nested_values: yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10))))) expected_values = zip(xrange(test_size), imap(str, xrange(test_size))) nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values))) assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),))))) >>> test_flat() >>> list(flat([[[1, 2, 3], [4, 5]], 6])) [1, 2, 3, 4, 5, 6] >>> $ uname -a Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64 $ python --version Python 2.7.5 
1
17 авг. Atsakymas, kurį pateikė Samy Vilar , rugpjūčio 17 d. 2014-08-17 22:52 '14, 10:52 pm 2014-08-17 22:52

Python-3

 from collections import Iterable L = [[[1, 2, 3], [4, 5]], 6,[7,[8,9,[10]]]] def flatten(thing): result = [] if isinstance(thing, Iterable): for item in thing: result.extend(flatten(item)) else: result.append(thing) return result flat = flatten(L) print(flat) 
0
27 февр. atsakymas, kurį pateikė Fuji Clado 27 vasaris 2017-02-27 19:01 '17 19:01 2017-02-27 19:01

Nenaudojant bibliotekos:

 def flat(l): def _flat(l, r): if type(l) is not list: r.append(l) else: for i in l: r = r + flat(i) return r return _flat(l, []) # example test = [[1], [[2]], [3], [['a','b','c'] , [['z','x','y']], ['d','f','g']], 4] print flat(test) # prints [1, 2, 3, 'a', 'b', 'c', 'z', 'x', 'y', 'd', 'f', 'g', 4] 
0
07 дек. Atsakyti alfasin 07 Dec 2014-12-07 09:06 '14 at 9:06 2014-12-07 09:06

Nėra rekursijos ar įdėtos kilpos. Kelios eilutės. Gerai suformatuotas ir lengvai skaitomas:

 def flatten_deep(arr: list): """ Flattens arbitrarily-nested list 'arr' into single-dimensional. """ while arr: if isinstance(arr[0], list): # Checks whether first element is a list arr = arr[0] + arr[1:] # If so, flattens that first element one level else: yield arr.pop(0) # Otherwise yield as part of the flat array flatten_deep(L) 

Iš savo kodo https://github.com/jorgeorpinel/flatten_nested_lists/blob/master/flatten.py

0
22 янв. Atsakymą pateikė Jorge Orpinel 22 sausis 2019-01-22 13:22 '19, 13:22 pm 2019-01-22 13:22

Bandant atsakyti į tokį klausimą, iš tikrųjų turite nurodyti kodo, kurį siūlote kaip sprendimą, apribojimus. Jei kalbėtume tik apie kalbas, aš neužmirščiau pernelyg daug, bet dauguma siūlomų kodų, kaip pasiūlymas (įskaitant priimtą atsakymą), netrukdo sąrašo, kurio gylis yra didesnis nei 1000.

Kai kalbu daugiausiai kodų, aš turiu galvoje visus kodus, kurie naudoja bet kokią rekursijos formą (arba skambina standartine bibliotekos funkcija, kuri yra rekursyvi). Visi šie kodai nepavyksta, nes kiekvienam rekursiniam skambučiui kamino (skambučio) skaičius auga vienu, o numatytoji skambučių stotelė (numatytoji) yra 1000.

Jei nesate per daug susipažinę su skambučių kaminu, galbūt tai padės (kitaip galite tiesiog eiti į įgyvendinimą ).

Skambučių kamino dydis ir rekursinis programavimas (Dungeon analogija)

Treasure Hunt ir Exit

Įsivaizduokite, kad įeisite į didžiulį požemį su numeruotais kambariais, ieškodami lobių. Jūs nežinote vietos, bet jūs turite keletą nurodymų , kaip rasti lobį. Kiekviena nuoroda yra paslaptis (sunkumai skiriasi, bet negalite prognozuoti, kaip sunku jie bus). Jūs nusprendėte šiek tiek galvoti apie laiko taupymo strategiją.

  1. Sunku (ilgai) rasti lobį, nes jūs turite išspręsti (potencialiai sunkias) mįsles, kad pasiektumėte.
  2. Kai randamas lobis, grįžimas į įėjimą gali būti lengvas, tiesiog reikia naudoti tą patį kelią kita kryptimi (nors atmintyje trunka šiek tiek atminties).

Kai įvedate požemį, čia matote mažą nešiojamąjį kompiuterį . Jūs nusprendžiate jį naudoti įrašydami kiekvieną kambarį, kurį išeisite po to, kai išspręsite mįslę (įeinant į naują kambarį), kad galėtumėte grįžti į įėjimą. Tai puiki idėja, jūs net neišleisite cento, įgyvendindami savo strategiją.

Jūs atsidursite požemyje, su dideliu pasisekimu išsprendžiate pirmuosius 1001 mįslių, bet čia ateina tai, ko neplanavote, jūs neturite vietos užrašuose, kuriuos pasiskolinote. Jūs nusprendžiate atsisakyti savo Quest, nes nenorite turėti lobių, nei amžinai būti pamestas požemyje (atrodo tikrai protingas).

Rekursinės programos vykdymas

Iš esmės tai yra tas pats, kaip rasti lobį. Dungeon yra kompiuterio atmintis, dabar jūsų tikslas yra ne rasti lobį, bet apskaičiuoti tam tikrą funkciją (rasti f (x) tam tikram x). Skaitymai yra tiesiog paprogramės, padedančios išspręsti f (x). Jūsų strategija yra tokia pati, kaip skambučių kamino strategija, nešiojamas kompiuteris yra kamino, numeriai yra funkcijų grąžinimo adresai:

 x = ["over here", "am", "I"] y = sorted(x) # You're about to enter a room named 'sorted', note down the current room address here so you can return back: 0x4004f4 (that room address looks weird) # Seems like you went back from your quest using the return address 0x4004f4 # Let see what you've collected print(' '.join(y)) 

Problema, su kuria susidūrėte požemyje, bus čia, skambučių kaminas turi ribinį dydį (čia 1000), todėl, jei įvesite per daug funkcijų grįžtant atgal, užpildysite skambučių kaminą ir gausite klaidą, kuri atrodo kaip „Gerbiamasis ieškotojas nuotykis, atsiprašau, bet jūsų nešiojamas kompiuteris yra pilnas “ :„ RecursionError: maximum recursion depth exceeded . Atkreipkite dėmesį, kad jums nereikia rekursijos, kad užpildytumėte skambučių steką, bet labai mažai tikėtina, kad ne rekursinė programa skambins 1000 funkcijų be grįžimo. Taip pat svarbu suprasti, kad sugrįžus iš funkcijos, skambučių kaminas atleidžiamas iš naudojamo adreso (taigi pavadinimas „kamino“, grįžimo adresas įterpiamas prieš įvedant funkciją ir ištraukiamas grįžus). В частном случае простой рекурсии (функция f которая вызывает себя один раз - снова и снова) вы будете вводить f снова и снова, пока вычисление не закончится (пока сокровище не будет найдено) и не вернется с f до тех пор, пока вы не пойдете назад к месту, где вы назвали f в первую очередь. Стек вызовов никогда не будет освобожден от чего-либо до конца, где он будет освобожден от всех обратных адресов один за другим.

Как избежать этой проблемы?

Это на самом деле довольно просто: "не используйте рекурсию, если вы не знаете, как глубоко она может идти". Это не всегда так, как в некоторых случаях, рекурсия хвостового звонка может быть оптимизирована (TCO) . Но в python это не так, и даже "хорошо написанная" рекурсивная функция не будет оптимизировать использование стека. Есть интересный пост от Гвидо об этом вопросе: " Устранение хвостовой рекурсии" .

Существует методика, позволяющая сделать любую рекурсивную функцию итеративной, эта техника, которую мы могли бы назвать, приносит ваш собственный ноутбук . Например, в нашем конкретном случае мы просто изучаем список, входя в комнату, эквивалентно вводу подсписок, вопрос, который вы должны задать себе, - как я могу вернуться из списка в его родительский список? Ответ не такой сложный, повторите следующее, пока stack будет пустым:

  1. нажимайте текущий address и index в stack при вводе нового подсписок (обратите внимание, что адрес + индекс также является адресом, поэтому мы используем только тот же метод, который используется стеком вызовов);
  2. каждый раз, когда элемент найден, yield его (или добавьте в список);
  3. как только список будет полностью изучен, вернитесь к родительскому списку, используя address возврата stackindex ).

Также обратите внимание, что это эквивалентно DFS в дереве, где некоторые узлы являются подсписками A = [1, 2] а некоторые являются простыми элементами: 0, 1, 2, 3, 4 (для L = [0, [1,2], 3, 4] ). Дерево выглядит так:

  L | ------------------- | | | | 0 --A-- 3 4 | | 1 2 

Предварительный порядок обхода DFS: L, 0, A, 1, 2, 3, 4. Помните, что для реализации итеративной DFS вам также понадобится стек. Реализация, которую я предложил, flat_list к flat_list , что следующие состояния (для stack и flat_list ):

 init.: stack=[(L, 0)] **0**: stack=[(L, 0)], flat_list=[0] **A**: stack=[(L, 1), (A, 0)], flat_list=[0] **1**: stack=[(L, 1), (A, 0)], flat_list=[0, 1] **2**: stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2] **3**: stack=[(L, 2)], flat_list=[0, 1, 2, 3] **3**: stack=[(L, 3)], flat_list=[0, 1, 2, 3, 4] return: stack=[], flat_list=[0, 1, 2, 3, 4]