Ratakan daftar yang tidak teratur

440

Ya, saya tahu subjek ini telah dibahas sebelumnya (di sini , di sini , di sini , di sini ), tetapi sejauh yang saya tahu, semua solusi, kecuali satu, gagal pada daftar seperti ini:

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

Di mana output yang diinginkan

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

Atau mungkin lebih baik, sebuah iterator. Satu-satunya solusi yang saya lihat yang berfungsi untuk bersarang sembarang ditemukan dalam pertanyaan ini :

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)

Apakah ini model terbaik? Apakah saya mengabaikan sesuatu? Masalah apapun?

telliott99
sumber
16
Fakta bahwa ada banyak jawaban dan begitu banyak tindakan pada pertanyaan ini benar-benar menunjukkan bahwa ini harus menjadi fungsi bawaan di suatu tempat, kan? Sayang sekali compiler.ast dihapus dari Python 3.0
Mittenchops
3
Saya akan mengatakan bahwa apa yang benar-benar dibutuhkan Python adalah rekursi yang tak terputus daripada builtin lain.
liat
2
@Mittenchops: sama sekali tidak setuju, fakta bahwa orang yang bekerja dengan API yang jelas buruk / struktur data yang terlalu rumit (hanya sebuah catatan: list yang dimaksudkan untuk menjadi homogen) tidak berarti itu adalah kesalahan Python dan kita membutuhkan builtin untuk tugas tersebut
Azat Ibrakov
1
Jika Anda mampu menambahkan paket ke proyek Anda - saya kira solusi more_itertools.collapse akan melakukan yang terbaik. Dari jawaban ini: stackoverflow.com/a/40938883/3844376
viddik13

Jawaban:

382

Menggunakan fungsi generator dapat membuat contoh Anda sedikit lebih mudah dibaca dan mungkin meningkatkan kinerja.

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

Saya menggunakan Iterable ABC ditambahkan pada 2.6.

Python 3

Dalam Python 3, basestringtidak lebih, tetapi Anda bisa menggunakan tuplestr dan bytesuntuk mendapatkan efek yang sama di sana.

The yield fromOperator mengembalikan sebuah item dari satu generator pada suatu waktu. Ini sintaks untuk mendelegasikan ke subgenerator sebuah ditambahkan dalam 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
Cristian
sumber
6
Dari semua saran di halaman ini, ini adalah satu-satunya yang meratakan daftar ini l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))dalam sekejap ketika saya melakukan ini list(flatten(l)). Yang lainnya, akan mulai bekerja dan mengambil selamanya!
nemesisfixx
7
Ini juga meratakan kamus. Mungkin Anda ingin menggunakan, collections.Sequencebukan collections.Iteratable?
josch
1
Ini tidak berfungsi dengan hal-hal yang awalnya bukan daftar, mis for i in flatten(42): print (i). Ini bisa diperbaiki dengan memindahkan isinstance-test dan yang lain-klausa di luar for el-loop. (Maka Anda bisa melempar apa saja padanya, dan itu akan membuat daftar yang rata dari itu)
RolKau
6
Untuk Python 3.7, penggunaan collections.Iterablesudah tidak digunakan lagi. Gunakan collections.abc.Iterablesebagai gantinya.
dawg
5
Memang, rekursi tidak pernah dibutuhkan. Dalam kasus khusus ini menggunakan rekursi bukan solusi terbaik karena akan crash pada daftar yang sangat bersarang (kedalaman> 1000). Tetapi jika Anda tidak bertujuan memiliki sesuatu yang aman, maka ya fungsi rekursif lebih baik karena mereka lebih mudah dibaca / ditulis.
cglacet
50

Solusi saya:

import collections


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

Sedikit lebih ringkas, tetapi hampir sama.

Josh Lee
sumber
5
Anda dapat melakukan ini tanpa mengimpor apa pun jika Anda hanya try: iter(x)ingin menguji apakah itu dapat diubah ... Tapi saya tidak berpikir harus mengimpor modul stdlib adalah kerugian yang patut dihindari.
abarnert
8
Layak untuk dicatat bahwa solusi ini hanya berfungsi jika semua item bertipeint
alfasin
1
Bisa membuatnya lebih ringkas, def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]- tetapi keterbacaan mungkin subjektif di sini.
Nol
4
ini tidak berfungsi pada string karena string juga dapat diubah. Ganti kondisinya denganif isinstance(x, collections.Iterable) and not isinstance(x, basestring)
aandis
36

Generator menggunakan rekursi dan mengetik bebek (diperbarui untuk 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]
dansalmo
sumber
1
Terima kasih, itu bekerja dengan baik untuk Python 3. Untuk 2.x sebelumnya diperlukan: for i in flatten(item): yield i
dansalmo
daftar (ratakan ([['X'], 'Y'])) gagal pada varian 2.X
sten
@ user1019129 lihat komentar saya di atas milik Anda
dansalmo
ya gagal dengan siklus .. saya pikir karena sebuah string juga merupakan "array" -of-chars
sten
35

Versi generator dari solusi non-rekursif @ unutbu, seperti yang diminta oleh @Andrew dalam komentar:

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

Versi generator ini sedikit disederhanakan:

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)
Alex Martelli
sumber
itu adalah pre-order traversal dari pohon yang dibentuk oleh daftar bersarang. hanya daun yang dikembalikan. Perhatikan bahwa implementasi ini akan menggunakan struktur data asli, baik atau buruk. Mungkin menyenangkan untuk menulis satu yang mempertahankan pohon asli, tetapi juga tidak perlu menyalin entri daftar.
Andrew Wagner
6
Saya pikir Anda perlu menguji untuk string - misalnya menambahkan "dan bukan isinstance (l [0], basestring)" seperti dalam solusi Cristian. Kalau tidak, Anda mendapatkan loop tak terbatas sekitar l [0: 1] = l [0]
c-urchin
Ini adalah contoh yang baik untuk membuat generator, tetapi seperti c-urchin menyebutkan, algoritma itu sendiri gagal ketika urutan berisi string.
Daniel 'Dang' Griffith
28

Ini adalah versi fungsional saya dari perataan rekursif yang menangani tupel dan daftar, dan memungkinkan Anda untuk melempar semua campuran argumen posisi. Mengembalikan generator yang menghasilkan seluruh urutan, arg oleh arg:

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

Pemakaian:

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]
samplebias
sumber
1
solusi yang bagus, namun akan banyak membantu jika Anda menambahkan beberapa komentar untuk menggambarkan apa e, a, nmerujuk ke
Kristof Pal
2
@WolfgangKuehne: Coba argsuntuk n, intermediate(atau yang lebih pendek midatau Anda lebih suka element) untuk adan resultuntuk e, jadi:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
Berhenti sebentar sampai pemberitahuan lebih lanjut.
Ini secara signifikan lebih cepat daripada compiler.ast.flatten. Bagus, kode ringkas, bekerja untuk semua jenis objek (saya pikir).
bcdan
Wow ini seharusnya jawaban yang paling banyak dipilih dan diterima ... bekerja seperti pesona!
U10-Forward
27

Versi ini flattenmenghindari batas rekursi python (dan dengan demikian bekerja dengan iterables yang bersarang mendalam). Ini adalah generator yang dapat menangani string dan iterables sewenang-wenang (bahkan yang tak terbatas).

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, (str, bytes)):
            remainder = IT.chain(first, remainder)
        else:
            yield first

Berikut adalah beberapa contoh yang menunjukkan penggunaannya:

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 range(ord('a'), ord('z')+1)] + list(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]

Meskipun flattendapat menangani generator yang tak terbatas, ia tidak dapat menangani sarang yang tak terbatas:

def infinitely_nested():
    while True:
        yield IT.chain(infinitely_nested(), IT.repeat(1))

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs
unutbu
sumber
1
Adakah konsensus tentang apakah akan menggunakan ABC Iterable atau ABC Sequence?
wim
sets, dicts, deques, listiterators, generators, Filehandles, dan kelas kustom dengan __iter__didefinisikan semua contoh collections.Iterable, tapi tidak collections.Sequence. Hasil meratakan a dictagak rapuh, tetapi jika tidak, saya pikir collections.Iterableadalah default yang lebih baik daripada collections.Sequence. Ini jelas lebih liberal.
unutbu
@wim: Satu masalah dengan penggunaan collections.Iterableadalah ini termasuk generator yang tak terbatas. Saya sudah mengubah jawaban saya menangani kasus ini.
unutbu
1
Ini sepertinya tidak berfungsi untuk contoh ke-3 dan ke-4. Itu melempar StopIteration. Juga, sepertinya while True: first = next(remainder) bisa diganti oleh for first in remainder:.
Georgy
@ Georgy ini bisa diperbaiki dengan mengenkapsulasi tubuh rata dalam try-except StopIteration block.
baduker
12

Inilah jawaban lain yang bahkan lebih menarik ...

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)

Pada dasarnya, ini mengubah daftar bersarang menjadi string, menggunakan regex untuk menghapus sintaks bersarang, dan kemudian mengubah hasilnya kembali ke daftar (diratakan).

tanah liat
sumber
Jika Anda mencoba untuk menggeneralisasi ini ke sesuatu selain nilai int, itu akan menyenangkan dengan, misalnya, [['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]:) Di sisi lain, mengingat daftar yang berisi dirinya sendiri, itu akan melakukan sedikit lebih baik daripada jawaban lain, menaikkan pengecualian alih-alih hanya mengulang sampai kehabisan memori / berulang hingga Anda kehabisan tumpukan ...
abarnert
Prompt asli adalah tentang meratakan daftar bilangan bulat. Jika Anda hanya mengubah pemahaman daftar menjadi d = [x untuk x dalam c] itu akan berfungsi dengan baik untuk sampel Anda.
clay
Pertama, [x for x in c]hanya cara lambat dan verbal untuk membuat salinan c, jadi mengapa Anda melakukan itu? Kedua, kode Anda jelas akan dikonversi 'APPLE ]['menjadi 'APPLE ', karena tidak menangani penawaran, hanya mengasumsikan bahwa tanda kurung adalah tanda kurung daftar.
abarnert
Ha! Cara komentar Anda diformat di komputer saya, saya bahkan tidak menyadari bahwa itu seharusnya Apple II seperti yang muncul di komputer lama. Bagaimanapun, jawaban saya untuk kedua pertanyaan Anda adalah bahwa latihan ini - bagi saya - hanyalah sebuah eksperimen untuk menemukan solusi kreatif untuk meratakan daftar. Saya tidak yakin saya akan menggeneralisirnya untuk meratakan setiap daftar di luar sana.
clay
Anda hanya perlu arr_str = str(arr)dan [int(s) for s in re.findall(r'\d+', arr_str)]benar-benar. Lihat github.com/jorgeorpinel/flatten_nested_lists/blob/master/…
Jorge Orpinel
10
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
kev
sumber
8

Anda bisa menggunakan deepflattendari paket pihak ke-3 iteration_utilities:

>>> 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]

Ini adalah iterator sehingga Anda harus mengulanginya (misalnya dengan membungkusnya dengan listatau menggunakannya dalam satu lingkaran). Secara internal ia menggunakan pendekatan berulang bukan pendekatan rekursif dan itu ditulis sebagai ekstensi C sehingga bisa lebih cepat daripada pendekatan python murni:

>>> %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)

Saya penulis iteration_utilitiesperpustakaan.

MSeifert
sumber
7

Itu menyenangkan mencoba untuk membuat fungsi yang bisa meratakan daftar tidak teratur di Python, tapi tentu saja itu untuk apa Python (untuk membuat pemrograman menyenangkan). Generator berikut bekerja dengan cukup baik dengan beberapa peringatan:

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

Ini akan meratakan tipe data yang mungkin ingin ditinggalkan sendirian (seperti bytearray, bytes, dan strbenda-benda). Juga, kode bergantung pada fakta bahwa meminta iterator dari non-iterable memunculkan a TypeError.

>>> 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]
>>>

Edit:

Saya tidak setuju dengan implementasi sebelumnya. Masalahnya adalah Anda seharusnya tidak bisa meratakan sesuatu yang tidak bisa diubah. Ini membingungkan dan memberikan kesan yang salah dari argumen.

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

Generator berikut hampir sama dengan yang pertama tetapi tidak memiliki masalah mencoba meratakan objek yang tidak dapat diubah. Gagal seperti yang diharapkan ketika argumen yang tidak tepat diberikan padanya.

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

Menguji generator berfungsi dengan baik dengan daftar yang disediakan. Namun, kode baru akan memunculkan TypeErrorketika objek yang tidak dapat diubah diberikan padanya. Contoh ditunjukkan di bawah ini dari perilaku baru.

>>> 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
>>>
Noctis Skytower
sumber
5

Meskipun jawaban yang elegan dan sangat pythonic telah dipilih, saya akan menyajikan solusi saya hanya untuk ulasan:

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

Tolong beri tahu seberapa baik atau buruk kode ini?

Xolve
sumber
1
Gunakan isinstance(i, (tuple, list)). Menginisialisasi variabel kosong adalah tanda bagi saya untuk mencari struktur kode alternatif, biasanya pemahaman, generator, rekursi, dll.
dansalmo
3
return type(l)(ret)akan membuat Anda mendapatkan jenis kontainer yang sama seperti yang diteruskan, juga. :)
dash-tom-bang
@ dash-tom-bang Bisakah Anda jelaskan apa artinya sedikit detail.
Xolve
1
Jika Anda memasukkan daftar, Anda mungkin ingin daftar kembali. Jika Anda memasukkan tuple, Anda mungkin ingin tuple kembali. Jika Anda melewatkan mishmash dari keduanya, Anda akan mendapatkan apapun yang terlampir.
dash-tom-bang
4

Saya lebih suka jawaban sederhana. Tidak ada generator. Tidak ada batas rekursi atau rekursi. Hanya iterasi:

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

Ini bekerja dengan dua daftar: bagian dalam untuk loop dan loop sementara luar.

Bagian dalam untuk loop berulang melalui daftar. Jika ia menemukan elemen daftar, itu (1) menggunakan list.extend () untuk meratakan bagian itu satu tingkat bersarang dan (2) beralih keepChecking ke True. keepchecking digunakan untuk mengontrol loop sementara luar. Jika loop luar disetel ke true, itu memicu loop dalam untuk lintasan lain.

Pass tersebut terus terjadi sampai tidak ada lagi daftar bersarang yang ditemukan. Ketika pass akhirnya terjadi di mana tidak ada yang ditemukan, keepChecking tidak pernah tersandung ke true, yang berarti listIsNested tetap salah dan loop keluar sementara keluar.

Daftar yang rata kemudian dikembalikan.

Uji coba

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

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

tanah liat
sumber
Saya suka sederhana juga. Namun dalam kasus ini, Anda mengulangi daftar sebanyak yang ada di sarang atau level. Bisa jadi mahal.
telliott99
@ telliott99: Anda benar jika daftar Anda benar-benar besar dan / atau bersarang dengan sangat mendalam. Namun, jika itu tidak terjadi, maka solusi yang lebih sederhana berfungsi dengan baik, dan tanpa keajaiban mendalam dari beberapa jawaban lainnya. Ada tempat untuk pemahaman generator rekursif multi-tahap, tapi saya tidak yakin itu harus di mana Anda melihat pertama. (Saya kira Anda tahu di mana saya termasuk dalam debat "Worse is Better".)
clay
@ telliott99: Atau dengan kata lain, Anda tidak perlu "mencoba Grok" solusi saya. Jika kinerja bukan hambatan, apa yang paling penting bagi Anda sebagai seorang programmer?
tanah liat
Solusi yang lebih sederhana memiliki sedikit logika. Rekursi adalah konstruksi pemrograman yang cukup mendasar yang siapa pun yang menganggap dirinya seorang programmer harus benar-benar nyaman. Generator sangat Python Way dan (bersama dengan pemahaman) adalah sesuatu yang harus diprogram oleh programmer Python profesional secara instan.
dash-tom-bang
1
Saya setuju tentang rekursi. Ketika saya menulis jawaban saya, python masih mematahkan rekursi pada 1000 siklus. Sudahkah mereka mengubah ini? Adapun menjadi programmer python profesional, saya tidak. Selain itu, saya membayangkan banyak orang pemrograman dengan python tidak melakukannya penuh waktu.
clay
4

Berikut adalah fungsi sederhana yang meratakan daftar kedalaman sewenang-wenang. Tanpa rekursi, untuk menghindari stack overflow.

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
Wilfred Hughes
sumber
Iya! Sangat mirip dengan kode saya di github.com/jorgeorpinel/flatten_nested_lists/blob/master/…
Jorge Orpinel
3

Saya terkejut tidak ada yang memikirkan hal ini. Rekursi sial Saya tidak mendapatkan jawaban rekursif yang dibuat oleh orang-orang lanjut di sini. Lagi pula di sini adalah upaya saya dalam hal ini. peringatan itu sangat spesifik untuk kasus penggunaan OP

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)

keluaran:

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

Saya tidak membahas semua jawaban yang sudah tersedia di sini, tetapi di sini ada satu liner yang saya buat, meminjam dari cara Lisp tentang pemrosesan daftar pertama dan sisanya

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

di sini adalah satu kasus sederhana dan satu tidak terlalu sederhana -

>>> 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]
>>> 
Shreyas
sumber
Ini bukan liner satu. Tidak peduli berapa banyak Anda berusaha untuk menyesuaikannya menjadi satu, itu def foo():adalah baris yang terpisah. Juga, ini sangat tidak bisa dibaca.
cs95
Saya telah membatalkan kode ini, dan melakukan refactoring lebih lanjut. (sunting sedang menunggu peer review saat saya menulis ini) Metode khusus ini tampaknya sangat mudah dibaca oleh saya, meskipun kode aslinya memang memerlukan beberapa refactoring.
Emilio M Bumachar
3

Ketika mencoba menjawab pertanyaan seperti itu, Anda benar-benar perlu memberikan batasan kode yang Anda usulkan sebagai solusi. Jika itu hanya tentang kinerja saya tidak akan terlalu keberatan, tetapi sebagian besar kode yang diusulkan sebagai solusi (termasuk jawaban yang diterima) gagal untuk meratakan daftar yang memiliki kedalaman lebih dari 1000.

Ketika saya mengatakan sebagian besar kode saya maksud adalah semua kode yang menggunakan segala bentuk rekursi (atau memanggil fungsi pustaka standar yang rekursif). Semua kode ini gagal karena untuk setiap panggilan rekursif yang dibuat, tumpukan (panggilan) bertambah satu unit, dan tumpukan panggilan python (default) memiliki ukuran 1000.

Jika Anda tidak terlalu terbiasa dengan tumpukan panggilan, maka mungkin yang berikut ini akan membantu (jika tidak, Anda bisa menggulir ke Implementasi ).

Panggil ukuran tumpukan dan pemrograman rekursif (analogi penjara)

Menemukan harta dan keluar

Bayangkan Anda memasuki ruang bawah tanah besar dengan kamar-kamar bernomor , mencari harta karun. Anda tidak tahu tempat itu tetapi Anda memiliki beberapa indikasi tentang bagaimana menemukan harta karun itu. Setiap indikasi adalah teka-teki (kesulitan bervariasi, tetapi Anda tidak dapat memprediksi seberapa sulit mereka akan). Anda memutuskan untuk berpikir sedikit tentang strategi menghemat waktu, Anda membuat dua pengamatan:

  1. Sulit (lama) untuk menemukan harta karun itu karena Anda harus menyelesaikan (berpotensi sulit) teka-teki untuk sampai ke sana.
  2. Setelah harta ditemukan, kembali ke pintu masuk mungkin mudah, Anda hanya perlu menggunakan jalur yang sama di arah lain (meskipun ini membutuhkan sedikit memori untuk mengingat jalan Anda).

Saat memasuki ruang bawah tanah, Anda melihat notebook kecil di sini. Anda memutuskan untuk menggunakannya untuk menuliskan setiap kamar yang Anda keluar setelah menyelesaikan teka-teki (saat memasuki ruangan baru), dengan cara ini Anda akan dapat kembali ke pintu masuk. Itu ide jenius, Anda bahkan tidak akan menghabiskan satu sen menerapkan strategi Anda.

Anda memasuki ruang bawah tanah, menyelesaikan dengan sukses besar teka-teki 1001 pertama, tetapi inilah sesuatu yang belum Anda rencanakan, Anda tidak memiliki ruang tersisa di notebook yang Anda pinjam. Anda memutuskan untuk meninggalkan pencarian karena Anda lebih suka tidak memiliki harta daripada hilang selamanya di dalam penjara bawah tanah (yang memang terlihat pintar).

Menjalankan program rekursif

Pada dasarnya, itu sama persis dengan menemukan harta karun itu. Penjara bawah tanah adalah memori komputer , tujuan Anda sekarang bukan untuk menemukan harta tetapi untuk menghitung beberapa fungsi (temukan f (x) untuk x yang diberikan ). Indikasinya sederhana adalah sub-rutin yang akan membantu Anda memecahkan f (x) . Strategi Anda sama dengan strategi tumpukan panggilan , notebook adalah tumpukan, kamar-kamar adalah alamat pengirim fungsi:

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's see what you've collected 
print(' '.join(y))

Masalah yang Anda temui di ruang bawah tanah akan sama di sini, tumpukan panggilan memiliki ukuran yang terbatas (di sini 1000) dan oleh karena itu, jika Anda memasukkan terlalu banyak fungsi tanpa kembali maka Anda akan mengisi tumpukan panggilan dan memiliki kesalahan yang terlihat seperti "Sayang petualang, aku sangat menyesal tapi notebook Anda penuh" : RecursionError: maximum recursion depth exceeded. Perhatikan bahwa Anda tidak perlu rekursi untuk mengisi tumpukan panggilan, tetapi sangat tidak mungkin bahwa program non-rekursif memanggil 1000 fungsi tanpa pernah kembali. Penting juga untuk memahami bahwa begitu Anda kembali dari suatu fungsi, tumpukan panggilan dibebaskan dari alamat yang digunakan (karenanya nama "tumpukan", alamat pengirim didorong masuk sebelum memasukkan suatu fungsi dan ditarik keluar ketika kembali). Dalam kasus khusus rekursi sederhana (fungsifpanggilan itu sendiri sekali - lagi dan lagi -) Anda akan masuk fberulang sampai perhitungan selesai (sampai harta ditemukan) dan kembali dari fsampai Anda kembali ke tempat di mana Anda memanggil ftempat pertama. Tumpukan panggilan tidak akan pernah dibebaskan dari apa pun sampai akhir di mana ia akan dibebaskan dari semua alamat pengirim satu demi satu.

Bagaimana cara menghindari masalah ini?

Itu sebenarnya cukup sederhana: "jangan menggunakan rekursi jika Anda tidak tahu seberapa dalam itu bisa terjadi". Itu tidak selalu benar seperti dalam beberapa kasus, rekursi Tail Call dapat Dioptimalkan (TCO) . Tetapi dalam python, ini tidak terjadi, dan bahkan fungsi rekursif "ditulis dengan baik" tidak akan mengoptimalkan penggunaan stack. Ada pos menarik dari Guido tentang pertanyaan ini: Penghapusan Rekursi Ekor .

Ada teknik yang dapat Anda gunakan untuk membuat fungsi berulang berulang, teknik ini bisa kita sebut membawa notebook Anda sendiri . Misalnya, dalam kasus khusus kami, kami hanya menjelajahi daftar, memasuki ruangan sama dengan memasukkan sublist, pertanyaan yang harus Anda tanyakan pada diri sendiri adalah bagaimana saya bisa kembali dari daftar ke daftar induknya? Jawabannya tidak rumit, ulangi yang berikut sampaistack kosong:

  1. dorong daftar saat ini addressdanindex di stacksaat memasuki sublist baru (catatan bahwa alamat daftar + indeks juga alamat, oleh karena itu kita hanya menggunakan teknik yang sama persis digunakan oleh panggilan stack);
  2. setiap kali item ditemukan, yield itu (atau menambahkannya dalam daftar);
  3. setelah daftar dieksplorasi sepenuhnya, kembali ke daftar induk menggunakan stack pengembalian address(dan index) .

Perhatikan juga bahwa ini setara dengan DFS di pohon di mana beberapa node adalah daftar A = [1, 2]dan beberapa item sederhana: 0, 1, 2, 3, 4(untuk L = [0, [1,2], 3, 4]). Pohon itu terlihat seperti ini:

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

Pre-order traversal DFS adalah: L, 0, A, 1, 2, 3, 4. Ingat, untuk menerapkan iteratif DFS Anda juga "perlu" tumpukan. Implementasi yang saya usulkan sebelum menghasilkan negara-negara berikut (untuk stackdan 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]

Dalam contoh ini, ukuran maksimum tumpukan adalah 2, karena daftar input (dan karenanya pohon) memiliki kedalaman 2.

Penerapan

Untuk implementasinya, dalam python Anda dapat menyederhanakan sedikit dengan menggunakan iterator dan bukan daftar sederhana. Referensi ke (sub) iterator akan digunakan untuk menyimpan sublists mengembalikan alamat (bukan memiliki kedua daftar alamat dan indeks). Ini bukan perbedaan besar tapi saya merasa ini lebih mudah dibaca (dan juga sedikit lebih cepat):

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

Juga, perhatikan bahwa di is_list_likeI have isinstance(item, list), yang bisa diubah untuk menangani lebih banyak tipe input, di sini saya hanya ingin memiliki versi paling sederhana di mana (iterable) hanya daftar. Tetapi Anda juga bisa melakukannya:

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

Ini menganggap string sebagai "item sederhana" dan karenanya flatten_iter([["test", "a"], "b])akan kembali ["test", "a", "b"]dan tidak ["t", "e", "s", "t", "a", "b"]. Komentar bahwa dalam kasus itu,iter(item) disebut dua kali pada setiap item, mari kita berpura-pura sebagai latihan bagi pembaca untuk membuat ini lebih bersih.

Menguji dan memberi komentar tentang implementasi lain

Pada akhirnya, ingat bahwa Anda tidak dapat mencetak daftar jauh bersarang Lmenggunakan print(L)karena internal akan menggunakan panggilan rekursif untuk __repr__( RecursionError: maximum recursion depth exceeded while getting the repr of an object). Untuk alasan yang sama, solusi untuk flattenmelibatkan strakan gagal dengan pesan kesalahan yang sama.

Jika Anda perlu menguji solusi Anda, Anda dapat menggunakan fungsi ini untuk menghasilkan daftar bersarang sederhana:

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

Yang memberi: build_deep_list(5)>>> [4, [3, [2, [1, [0]]]]].

cglacet
sumber
2

Berikut compiler.ast.flattenimplementasinya di 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

Ada metode yang lebih baik, lebih cepat (Jika Anda sudah sampai di sini, Anda sudah melihatnya)

Juga mencatat:

Tidak digunakan lagi sejak versi 2.6: Paket compiler telah dihapus dengan Python 3.

pradyunsg
sumber
2

benar-benar gila tapi saya pikir itu akan berhasil (tergantung pada data_type Anda)

flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list)))
Joran Beasley
sumber
2

Cukup gunakan funcyperpustakaan: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list
ADR
sumber
1
FYI: menggunakan solusi rekursif: tautan ke sumber
Georgy
1

Berikut ini adalah pendekatan py2 lain, saya tidak yakin apakah ini yang tercepat atau yang paling elegan ...

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))

Itu dapat mengabaikan jenis spesifik (atau turunan) yang Anda inginkan, mengembalikan iterator, sehingga Anda dapat mengonversinya ke wadah tertentu seperti daftar, tuple, dict atau cukup mengkonsumsinya untuk mengurangi jejak memori, baik atau buruk dapat menangani objek non-iterable awal seperti ...

Perhatikan sebagian besar pengangkatan berat dilakukan dalam C, karena sejauh yang saya tahu itulah cara itertools diimplementasikan, jadi saat ini bersifat rekursif, AFAIK tidak dibatasi oleh kedalaman rekursi python karena pemanggilan fungsi terjadi di C, meskipun ini tidak berarti Anda dibatasi oleh memori, khususnya di OS X di mana ukuran tumpukannya memiliki batas yang sulit pada hari ini (OS X Mavericks) ...

ada pendekatan yang sedikit lebih cepat, tetapi metode yang lebih portabel, hanya gunakan jika Anda dapat mengasumsikan bahwa elemen dasar dari input dapat ditentukan secara eksplisit, jika tidak, Anda akan mendapatkan rekursi tak terbatas, dan OS X dengan ukuran stack yang terbatas, akan melempar kesalahan segmentasi dengan cukup cepat ...

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))

di sini kita menggunakan set untuk memeriksa jenis sehingga dibutuhkan O (1) vs O (jumlah jenis) untuk memeriksa apakah suatu elemen harus diabaikan, meskipun tentu saja nilai apa pun dengan jenis turunan dari jenis yang diabaikan akan dinyatakan gagal. , ini sebabnya penggunaannya str, unicodejadi gunakan dengan hati-hati ...

tes:

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
Samy Vilar
sumber
1

Tanpa menggunakan perpustakaan apa pun:

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]
Alfasin
sumber
1

Menggunakan 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

Atau tanpa rantai:

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)
Saksham Varma
sumber
1

Saya menggunakan rekursif untuk memecahkan daftar bersarang dengan kedalaman apa pun

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

Jadi setelah saya mendefinisikan fungsi fungsi_next, mudah untuk menggunakan fungsi ini melakukan flatting. Atau Anda bisa menggabungkannya menjadi satu fungsi. Saya suka solusi saya karena dapat diterapkan ke daftar bersarang.

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

hasil

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]
Tua muda
sumber
"daftar bersarang dengan kedalaman apa pun" tidak benar. Coba saja, Anda akan melihat: current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
cglacet
hmmm Saya mencoba daftar dengan lebih dari 1000 lapisan?
Oldyoung
Tentu saja, itulah inti dari diskusi tentang solusi rekursif vs iteratif. Jika Anda tahu sebelumnya bahwa jumlah layer adalah <dari 1000 maka solusi paling sederhana akan berhasil. Ketika Anda mengatakan "kedalaman apa pun" ini termasuk daftar dengan kedalaman> 1000.
cglacet
1

Cara termudah adalah menggunakan perpustakaan morf menggunakan pip install morph.

Kode tersebut adalah:

import morph

list = [[[1, 2, 3], [4, 5]], 6]
flattened_list = morph.flatten(list)  # returns [1, 2, 3, 4, 5, 6]
YPCrumble
sumber
1

Saya sadar bahwa sudah ada banyak jawaban yang luar biasa tetapi saya ingin menambahkan jawaban yang menggunakan metode pemrograman fungsional untuk menyelesaikan pertanyaan. Dalam jawaban ini saya menggunakan rekursi ganda:

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]]))

keluaran:

[1, 2, 3, 4, 5, 6, 7]
Leo wahyd
sumber
1

Saya tidak yakin apakah ini perlu lebih cepat atau lebih efektif, tetapi inilah yang saya lakukan:

def flatten(lst):
    return eval('[' + str(lst).replace('[', '').replace(']', '') + ']')

L = [[[1, 2, 3], [4, 5]], 6]
print(flatten(L))

The flattenFungsi sini ternyata daftar ke string, mengeluarkan semua dari kurung persegi, menempel kurung kembali ke ujung, dan mengubahnya kembali ke dalam daftar.

Meskipun, jika Anda tahu Anda akan memiliki tanda kurung siku dalam daftar dalam string [[1, 2], "[3, 4] and [5]"], Anda harus melakukan sesuatu yang lain.

diligar
sumber
Ini tidak memiliki keunggulan dibandingkan solusi sederhana karena gagal memproses daftar dalam, yaitu "RecursionError: kedalaman rekursi maksimum terlampaui saat mendapatkan repr dari suatu objek".
cglacet
1

Ini adalah alat sederhana ratakan pada python2

flatten=lambda l: reduce(lambda x,y:x+y,map(flatten,l),[]) if isinstance(l,list) else [l]

test=[[1,2,3,[3,4,5],[6,7,[8,9,[10,[11,[12,13,14]]]]]],]
print flatten(test)

#output [1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Statham
sumber
1

Ini akan meratakan daftar atau kamus (atau daftar daftar atau kamus kamus dll). Itu mengasumsikan bahwa nilai-nilai adalah string dan itu menciptakan string yang menyatukan setiap item dengan argumen pemisah. Jika mau, Anda bisa menggunakan pemisah untuk membagi hasilnya menjadi objek daftar sesudahnya. Ini menggunakan rekursi jika nilai berikutnya adalah daftar atau string. Gunakan argumen kunci untuk mengetahui apakah Anda ingin kunci atau nilai-nilai (atur kunci ke salah) dari objek kamus.

def flatten_obj(n_obj, key=True, my_sep=''):
    my_string = ''
    if type(n_obj) == list:
        for val in n_obj:
            my_sep_setter = my_sep if my_string != '' else ''
            if type(val) == list or type(val) == dict:
                my_string += my_sep_setter + flatten_obj(val, key, my_sep)
            else:
                my_string += my_sep_setter + val
    elif type(n_obj) == dict:
        for k, v in n_obj.items():
            my_sep_setter = my_sep if my_string != '' else ''
            d_val = k if key else v
            if type(v) == list or type(v) == dict:
                my_string += my_sep_setter + flatten_obj(v, key, my_sep)
            else:
                my_string += my_sep_setter + d_val
    elif type(n_obj) == str:
        my_sep_setter = my_sep if my_string != '' else ''
        my_string += my_sep_setter + n_obj
        return my_string
    return my_string

print(flatten_obj(['just', 'a', ['test', 'to', 'try'], 'right', 'now', ['or', 'later', 'today'],
                [{'dictionary_test': 'test'}, {'dictionary_test_two': 'later_today'}, 'my power is 9000']], my_sep=', ')

hasil:

just, a, test, to, try, right, now, or, later, today, dictionary_test, dictionary_test_two, my power is 9000
Matt Farguson
sumber
0

Jika Anda menyukai rekursi, ini mungkin solusi yang menarik bagi Anda:

def f(E):
    if E==[]: 
        return []
    elif type(E) != list: 
        return [E]
    else:
        a = f(E[0])
        b = f(E[1:])
        a.extend(b)
        return a

Saya sebenarnya mengadaptasi ini dari beberapa kode praktek Skema yang saya tulis beberapa waktu lalu.

Nikmati!

inspectorG4dget
sumber
0

Saya baru mengenal python dan berasal dari latar belakang cadel. Inilah yang saya buat (lihat nama var untuk lulz):

def flatten(lst):
    if lst:
        car,*cdr=lst
        if isinstance(car,(list,tuple)):
            if cdr: return flatten(car) + flatten(cdr)
            return flatten(car)
        if cdr: return [car] + flatten(cdr)
        return [car]

Tampaknya bekerja. Uji:

flatten((1,2,3,(4,5,6,(7,8,(((1,2)))))))

pengembalian:

[1, 2, 3, 4, 5, 6, 7, 8, 1, 2]
Michael Puckett
sumber