Identifikasi kelompok bilangan kontinu dalam daftar

94

Saya ingin mengidentifikasi kelompok bilangan kontinu dalam daftar, sehingga:

myfunc([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

Pengembalian:

[(2,5), (12,17), 20]

Dan bertanya-tanya apa cara terbaik untuk melakukan ini (terutama jika ada sesuatu yang terintegrasi ke dalam Python).

Edit: Catatan Saya awalnya lupa menyebutkan bahwa nomor individu harus dikembalikan sebagai nomor individu, bukan rentang.

mikemaccana
sumber
3
Apakah nilai yang dikembalikan itu string?
Mark Byers
Idealnya lebih suka sesuatu yang menggunakan tipe terpisah untuk rentang vs nomor mandiri.
mikemaccana

Jawaban:

53

more_itertools.consecutive_groups telah ditambahkan di versi 4.0.

Demo

import more_itertools as mit


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
[list(group) for group in mit.consecutive_groups(iterable)]
# [[2, 3, 4, 5], [12, 13, 14, 15, 16, 17], [20]]

Kode

Dengan menerapkan alat ini, kami membuat fungsi generator yang menemukan rentang angka berurutan.

def find_ranges(iterable):
    """Yield range of consecutive numbers."""
    for group in mit.consecutive_groups(iterable):
        group = list(group)
        if len(group) == 1:
            yield group[0]
        else:
            yield group[0], group[-1]


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
list(find_ranges(iterable))
# [(2, 5), (12, 17), 20]

The Sumber pelaksanaan mengemulasi resep klasik (seperti yang ditunjukkan oleh @Nadia Alramli).

Catatan: more_itertoolsadalah paket pihak ketiga yang dapat diinstal melalui pip install more_itertools.

pylang
sumber
121

EDIT 2: Untuk menjawab persyaratan baru OP

ranges = []
for key, group in groupby(enumerate(data), lambda (index, item): index - item):
    group = map(itemgetter(1), group)
    if len(group) > 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])

Keluaran:

[xrange(2, 5), xrange(12, 17), 20]

Anda dapat mengganti xrange dengan range atau kelas kustom lainnya.


Dokumen Python memiliki resep yang sangat rapi untuk ini:

from operator import itemgetter
from itertools import groupby
data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    print map(itemgetter(1), g)

Keluaran:

[2, 3, 4, 5]
[12, 13, 14, 15, 16, 17]

Jika Anda ingin mendapatkan hasil yang sama persis, Anda dapat melakukan ini:

ranges = []
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    group = map(itemgetter(1), g)
    ranges.append((group[0], group[-1]))

keluaran:

[(2, 5), (12, 17)]

EDIT: Contohnya sudah dijelaskan di dokumentasi tapi mungkin saya harus menjelaskannya lebih lanjut:

Kunci solusinya adalah membedakan dengan rentang sehingga semua angka yang berurutan muncul dalam kelompok yang sama.

Jika datanya adalah: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] Maka groupby(enumerate(data), lambda (i,x):i-x)ekivalen dengan berikut ini:

groupby(
    [(0, 2), (1, 3), (2, 4), (3, 5), (4, 12),
    (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)],
    lambda (i,x):i-x
)

Fungsi lambda mengurangi indeks elemen dari nilai elemen. Jadi ketika Anda menerapkan lambda pada setiap item. Anda akan mendapatkan kunci berikut untuk groupby:

[-2, -2, -2, -2, -8, -8, -8, -8, -8, -8]

mengelompokkan elemen berdasarkan nilai kunci yang sama, sehingga 4 elemen pertama akan dikelompokkan dan seterusnya.

Saya harap ini membuatnya lebih mudah dibaca.

python 3 versi mungkin berguna untuk pemula

impor perpustakaan yang diperlukan terlebih dahulu

from itertools import groupby
from operator import itemgetter

ranges =[]

for k,g in groupby(enumerate(data),lambda x:x[0]-x[1]):
    group = (map(itemgetter(1),g))
    group = list(map(int,group))
    ranges.append((group[0],group[-1]))
Nadia Alramli
sumber
4
hampir bekerja di py3k, kecuali yang dibutuhkan lambda x:x[0]-x[1].
SilentGhost
Bisakah Anda menggunakan harap menggunakan nama variabel multi-karakter? Bagi seseorang yang tidak familiar dengan map () atau groupby (), arti dari kg, i dan x tidak jelas.
mikemaccana
1
Ini disalin dari dokumentasi Python dengan nama variabel yang sama. Saya mengubah nama sekarang.
Nadia Alramli
1
Anda harus menaikkan angka ke-2 dalam xrange / range karena ini tidak inklusif. Dengan kata lain [2,3,4,5] == xrange(2,6), tidak xrange(2,5). Mungkin ada baiknya mendefinisikan tipe data rentang inklusif baru.
IceArdor
10
Python 3 memunculkan kesalahan sintaks pada contoh pertama. Berikut 2 baris pertama yang diperbarui untuk bekerja pada python 3:for key, group in groupby(enumerate(data), lambda i: i[0] - i[1]): group = list(map(itemgetter(1), group))
derek73
16

Solusi "naif" yang menurut saya agak mudah dibaca.

x = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 22, 25, 26, 28, 51, 52, 57]

def group(L):
    first = last = L[0]
    for n in L[1:]:
        if n - 1 == last: # Part of the group, bump the end
            last = n
        else: # Not part of the group, yield current group and start a new
            yield first, last
            first = last = n
    yield first, last # Yield the last group


>>>print list(group(x))
[(2, 5), (12, 17), (22, 22), (25, 26), (28, 28), (51, 52), (57, 57)]
truppo
sumber
Saya sangat menyukai jawaban ini karena singkat namun dapat dibaca. Namun angka yang berada di luar rentang harus dicetak sebagai digit tunggal, bukan tupel (karena saya akan memformat keluaran dan memiliki persyaratan pemformatan yang berbeda untuk nomor individu versus rentang angka.
mikemaccana
4
Jawaban lain tampak cantik dan cerdas, tetapi yang ini lebih dapat dimengerti oleh saya dan memungkinkan pemula seperti saya untuk mengembangkannya sesuai dengan kebutuhan saya.
Benny
Bisa menggunakan pemahaman daftar untuk mencetak tupel non-range sebagai satu digit: print([i if i[0] != i[1] else i[0] for i in group(x)])
Nexus
14

Dengan asumsi daftar Anda diurutkan:

>>> from itertools import groupby
>>> def ranges(lst):
    pos = (j - i for i, j in enumerate(lst))
    t = 0
    for i, els in groupby(pos):
        l = len(list(els))
        el = lst[t]
        t += l
        yield range(el, el+l)


>>> lst = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
>>> list(ranges(lst))
[range(2, 6), range(12, 18)]
SilentGhost
sumber
2
[j - i for i, j in enumerate(lst)]pintar :-)
Jochen Ritzel
9

Ini dia sesuatu yang seharusnya berfungsi, tanpa perlu impor:

def myfunc(lst):
    ret = []
    a = b = lst[0]                           # a and b are range's bounds

    for el in lst[1:]:
        if el == b+1: 
            b = el                           # range grows
        else:                                # range ended
            ret.append(a if a==b else (a,b)) # is a single or a range?
            a = b = el                       # let's start again with a single
    ret.append(a if a==b else (a,b))         # corner case for last single/range
    return ret
Andrea Ambu
sumber
6

Harap dicatat bahwa kode yang menggunakan groupbytidak berfungsi seperti yang diberikan di Python 3 jadi gunakan ini.

for k, g in groupby(enumerate(data), lambda x:x[0]-x[1]):
    group = list(map(itemgetter(1), g))
    ranges.append((group[0], group[-1]))
Mark Lawrence
sumber
3

Ini tidak menggunakan fungsi standar - itu hanya iiterasi atas input, tetapi seharusnya berfungsi:

def myfunc(l):
    r = []
    p = q = None
    for x in l + [-1]:
        if x - 1 == q:
            q += 1
        else:
            if p:
               if q > p:
                   r.append('%s-%s' % (p, q))
               else:
                   r.append(str(p))
            p = q = x
    return '(%s)' % ', '.join(r)

Perhatikan bahwa itu mensyaratkan bahwa input hanya berisi bilangan positif dalam urutan naik. Anda harus memvalidasi masukan, tetapi kode ini dihilangkan untuk kejelasan.

Mark Byers
sumber
2

Menggunakan groupbydan countdari itertoolsmemberi kami solusi singkat. Idenya adalah bahwa, dalam urutan yang meningkat, perbedaan antara indeks dan nilai akan tetap sama.

Untuk melacak indeks, kita dapat menggunakan itertools.count , yang membuat kode lebih bersih seperti enumerate:

from itertools import groupby, count

def intervals(data):
    out = []
    counter = count()

    for key, group in groupby(data, key = lambda x: x-next(counter)):
        block = list(group)
        out.append([block[0], block[-1]])
    return out

Beberapa keluaran sampel:

print(intervals([0, 1, 3, 4, 6]))
# [[0, 1], [3, 4], [6, 6]]

print(intervals([2, 3, 4, 5]))
# [[2, 5]]
Thierry Lathuille
sumber
1

Inilah jawaban yang saya dapatkan. Saya menulis kode untuk dipahami orang lain, jadi saya cukup bertele-tele dengan nama variabel dan komentar.

Pertama, fungsi pembantu cepat:

def getpreviousitem(mylist,myitem):
    '''Given a list and an item, return previous item in list'''
    for position, item in enumerate(mylist):
        if item == myitem:
            # First item has no previous item
            if position == 0:
                return None
            # Return previous item    
            return mylist[position-1] 

Dan kemudian kode sebenarnya:

def getranges(cpulist):
    '''Given a sorted list of numbers, return a list of ranges'''
    rangelist = []
    inrange = False
    for item in cpulist:
        previousitem = getpreviousitem(cpulist,item)
        if previousitem == item - 1:
            # We're in a range
            if inrange == True:
                # It's an existing range - change the end to the current item
                newrange[1] = item
            else:    
                # We've found a new range.
                newrange = [item-1,item]
            # Update to show we are now in a range    
            inrange = True    
        else:   
            # We were in a range but now it just ended
            if inrange == True:
                # Save the old range
                rangelist.append(newrange)
            # Update to show we're no longer in a range    
            inrange = False 
    # Add the final range found to our list
    if inrange == True:
        rangelist.append(newrange)
    return rangelist

Contoh run:

getranges([2, 3, 4, 5, 12, 13, 14, 15, 16, 17])

kembali:

[[2, 5], [12, 17]]
mikemaccana
sumber
>>> getranges([2, 12, 13])Output: [[12, 13]]. Apakah itu disengaja?
SilentGhost
Ya, saya perlu memperbaiki nomor individu (sesuai sebagian besar jawaban di halaman). Sedang mengerjakannya sekarang.
mikemaccana
Sebenarnya saya lebih suka jawaban Nadia, groupby () sepertinya fungsi standar yang saya inginkan.
mikemaccana
1
import numpy as np

myarray = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
sequences = np.split(myarray, np.array(np.where(np.diff(myarray) > 1)[0]) + 1)
l = []
for s in sequences:
    if len(s) > 1:
        l.append((np.min(s), np.max(s)))
    else:
        l.append(s[0])
print(l)

Keluaran:

[(2, 5), (12, 17), 20]

sumber
0

Menggunakan daftar pemahaman + numpy:
Dengan fungsi numpy diff, entri vektor masukan konsekuensi yang perbedaannya tidak sama dengan satu dapat diidentifikasi. Awal dan akhir vektor masukan perlu dipertimbangkan.

import numpy as np
data = np.array([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

d = [i for i, df in enumerate(np.diff(data)) if df!= 1] 
d = np.hstack([-1, d, len(data)-1])  # add first and last elements 
d = np.vstack([d[:-1]+1, d[1:]]).T

print(data[d])

Keluaran:

 [[ 2  5]   
  [12 17]   
  [20 20]]

Catatan: Permintaan bahwa nomor individu harus diperlakukan berbeda, (dikembalikan sebagai individu, bukan rentang) dihilangkan. Ini dapat dicapai dengan pasca-pemrosesan hasil lebih lanjut. Biasanya ini akan membuat segalanya menjadi lebih kompleks tanpa mendapatkan keuntungan apapun.

Nir
sumber
0

Solusi singkat yang berfungsi tanpa impor tambahan. Ini menerima setiap iterable, mengurutkan input yang tidak diurutkan, dan menghapus item duplikat:

def ranges(nums):
    nums = sorted(set(nums))
    gaps = [[s, e] for s, e in zip(nums, nums[1:]) if s+1 < e]
    edges = iter(nums[:1] + sum(gaps, []) + nums[-1:])
    return list(zip(edges, edges))

Contoh:

>>> ranges([2, 3, 4, 7, 8, 9, 15])
[(2, 4), (7, 9), (15, 15)]

>>> ranges([-1, 0, 1, 2, 3, 12, 13, 15, 100])
[(-1, 3), (12, 13), (15, 15), (100, 100)]

>>> ranges(range(100))
[(0, 99)]

>>> ranges([0])
[(0, 0)]

>>> ranges([])
[]

Ini sama dengan solusi @ dansalmo yang menurut saya luar biasa, meskipun agak sulit untuk dibaca dan diterapkan (karena tidak diberikan sebagai fungsi).

Perhatikan bahwa ini dapat dengan mudah dimodifikasi untuk mengeluarkan rentang terbuka "tradisional" [start, end), misalnya dengan mengubah pernyataan return:

    return [(s, e+1) for s, e in zip(edges, edges)]

Saya menyalin jawaban ini dari pertanyaan lain yang ditandai sebagai duplikat dari pertanyaan ini dengan maksud agar lebih mudah ditemukan (setelah saya baru saja mencari lagi untuk topik ini, hanya menemukan pertanyaan di sini pada awalnya dan tidak puas dengan jawabannya diberikan).

perbaikan dingin
sumber
0

Versi Mark Byers , Andrea Ambu , SilentGhost , Nadia Alramli , dan truppo sederhana dan cepat. Versi 'truppo' mendorong saya untuk menulis versi yang mempertahankan perilaku gesit yang sama saat menangani ukuran langkah selain 1 (dan mencantumkan sebagai elemen tunggal yang tidak memperpanjang lebih dari 1 langkah dengan ukuran langkah tertentu). Itu diberikan di sini .

>>> list(ranges([1,2,3,4,3,2,1,3,5,7,11,1,2,3]))
[(1, 4, 1), (3, 1, -1), (3, 7, 2), 11, (1, 3, 1)]
smichr
sumber