목록에서 연속된 번호 그룹 식별

목록에서 연속된 번호 그룹 식별

목록에서 연속된 번호 그룹을 식별하여 다음을 수행하고자 합니다.

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

반품:

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

그리고 이것을 하는 가장 좋은 방법이 무엇인지 궁금했다(특히 Python에 내장된 것이 있다면).

편집: 원래 개별 번호는 범위가 아닌 개별 번호로 반환해야 한다는 것을 깜빡했습니다.

편집 2: 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])

출력:

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

xrange를 범위 또는 다른 사용자 지정 클래스로 대체할 수 있습니다.

---

Python docs에는 매우 깔끔한 레시피가 있습니다.

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

출력:

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

같은 출력을 취득하는 경우는, 다음과 같이 할 수 있습니다.

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

출력:

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

---

편집: 이 예는 이미 매뉴얼에 설명되어 있습니다만, 자세한 내용은 설명하겠습니다.

솔루션의 열쇠는 연속되는 번호가 모두 같은 그룹에 표시되도록 범위와의 차이점을 찾는 것입니다.

가 다음과 같은:[2, 3, 4, 5, 12, 13, 14, 15, 16, 17] ★★★★★★★★★★★★★★★.groupby(enumerate(data), lambda (i,x):i-x)는 다음과

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
)

람다 함수는 요소 값에서 요소 지수를 뺍니다.그래서 각 아이템에 람다를 바르면.groupby에는 다음과 같은 키가 있습니다.

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

groupby는 동일한 키 값을 기준으로 요소를 그룹화합니다.따라서 처음 4개의 요소는 함께 그룹화됩니다.

이게 좀 더 읽기 쉬웠으면 좋겠어요.

python 3에게는 이 될 수 .

먼저 필요한 라이브러리를 Import합니다.

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

more_itertools.consecutive_groups 는 버전 4.0에서 추가되었습니다.

데모

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

코드

이 툴을 사용하여 연속된 번호의 범위를 찾는 제너레이터 함수를 만듭니다.

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]

소스 실장은 (@Nadia Alramli에 의해 증명된) 고전적인 레시피를 모방합니다.

★★★★★★more_itertools는 를 통해 설치할 수 있는 서드파티 패키지입니다.

적어도 어느 정도 읽을 수 있는 "원활한" 솔루션.

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

목록이 정렬되어 있다고 가정합니다.

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

여기에서는 Import를 하지 않아도 동작할 수 있습니다.

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

에는 '먹다'를 사용한다는 하시기 바랍니다.groupbyPython 3에서는 동작하지 않기 때문에, 이것을 사용해 주세요.

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

이것은 표준 함수를 사용하지 않고 입력 위에 반복할 뿐이지만 다음과 같이 작동합니다.

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)

입력에는 오름차순으로 양수만 포함되어 있어야 합니다.입력의 유효성을 확인할 필요가 있습니다만, 알기 쉽게 하기 위해서 이 코드는 생략되어 있습니다.

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)

출력:

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

이것이 제가 가독성을 우선시하려고 했던 방법입니다.그룹에 값이 1개밖에 없는 경우 같은 값의 태플이 반환된다는 점에 유의하십시오.그것은 제가 투고할 두 번째 토막에서 쉽게 수정할 수 있습니다.

def group(values):
    """return the first and last value of each continuous set in a list of sorted values"""

    values = sorted(values)
    first = last = values[0]

    for index in values[1:]:
        if index - last > 1:  # triggered if in a new group
            yield first, last

            first = index  # update first only if in a new group

        last = index  # update last on every iteration

    yield first, last  # this is needed to yield the last set of numbers

테스트 결과는 다음과 같습니다.

values = [0, 5, 6, 7, 12, 13, 21, 22, 23, 24, 25, 26, 30, 44, 45, 50]
result = list(group(values))
print(result)

= = 과[(0, 0), (5, 7), (12, 13), (21, 26), (30, 30), (44, 45), (50, 50)]

그룹의 값이 1개일 경우 1개의 값만 반환할 경우 수율에 조건부 체크를 추가합니다.

def group(values):
    """return the first and last value of each continuous set in a list of sorted values"""

    values = sorted(values)

    first = last = values[0]

    for index in values[1:]:
        if index - last > 1:  # triggered if in a new group
            if first == last:
                yield first

            else:
                yield first, last

            first = index  # update first only if in a new group

        last = index  # update last on every iteration

    if first == last:
        yield first

    else:
        yield first, last

= = 과[0, (5, 7), (12, 13), (21, 26), 30, (44, 45), 50]

이 방법은 여기서 본 어떤 답변보다 간단하다고 생각합니다(편집: Plastry의 코멘트에 근거해 수정).

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

starts = [x for x in data if x-1 not in data and x+1 in data]
ends = [x for x in data if x-1 in data and x+1 not in data and x not in starts]
singles = [x for x in data if x-1 not in data and x+1 not in data]
list(zip(starts, ends)) + singles

출력:

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

---

편집 완료:

@dawg에서 알 수 있듯이 이것은 O(n**2)입니다.성능을 향상시키는 한 가지 방법은 원래 목록을 세트로 변환하는 것입니다. 즉, 시작 목록을 세트로 변환하는 것입니다.

data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
data_as_set = set(data)

starts = [x for x in data_as_set if x-1 not in data_as_set and x+1 in data_as_set]
startset = set(starts)
ends = [x for x in data_as_set if x-1 in data_as_set and x+1 not in data_as_set and x not in startset]
singles = [x for x in data_as_set if x-1 not in data_as_set and x+1 not in data_as_set]

print(list(zip(starts, ends)) + singles) 

용 사?groupby and 그리고.count부에서itertools짧은 해결책을 제시하다간단한 해결책을 제시합니다.즉, 지수와 값 사이의 차이는 증가 시퀀스에서 동일하게 유지된다는 것이다.

인덱스를 추적하기 위해 itertools.count를 사용하면 코드를 보다 깔끔하게 만들 수 있습니다.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

출력 예:

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

print(intervals([2, 3, 4, 5]))
# [[2, 5]]

제가 생각해낸 답은 이렇습니다.나는 다른 사람들이 이해할 수 있도록 코드를 쓰고 있기 때문에 변수 이름과 코멘트를 꽤 장황하게 쓰고 있다.

먼저 빠른 도우미 기능:

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] 

그리고 실제 코드:

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

실행 예:

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

반환:

[[2, 5], [12, 17]]

+ 목록 : numpy + " " " :
numpy diff 함수를 사용하면 그 차이가 1과 같지 않은 입력 벡터 엔트리를 식별할 수 있다.입력 벡터의 시작과 끝을 고려해야 합니다.

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

출력:

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

주의: 개개의 번호가 다르게 취급되어야 한다는 요구(범위가 아닌 개개의 번호로 반환됨)는 생략되었습니다.결과를 추가로 후처리하여 이를 달성할 수 있습니다.일반적으로 이로 인해 어떤 이점도 얻지 못한 채 일이 더 복잡해집니다.

관심 있는 경우 Python 2.7의 원라이너:

x = [2, 3, 6, 7, 8, 14, 15, 19, 20, 21]

d = iter(x[:1] + sum(([i1, i2] for i1, i2 in zip(x, x[1:] + x[:1]) if i2 != i1+1), []))

print zip(d, d)

>>> [(2, 3), (6, 8), (14, 15), (19, 21)]

추가 Import 없이 동작하는 쇼트 솔루션.반복 가능한 입력을 받아들여 정렬되지 않은 입력을 정렬하고 중복 항목을 제거합니다.

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

예를 들어:

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

이것은 @dansalmo의 솔루션과 같은 것으로, (함수로 되어 있지 않기 때문에) 읽고 적용하는 것은 조금 어렵지만, 신기하다고 생각합니다.

레인지인 오픈 레인지로 '인' 오픈 레인지로 할 수 있습니다.[start, end)예를 들어, 반품 명세서를 변경:

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

이 답변을 다른 질문에서 복사하여 쉽게 찾을 수 있도록 했습니다(이 주제를 다시 검색한 후 처음에는 질문만 찾았고 답변에 만족하지 못했습니다).

Mark Byers, Andrea Ambu, SilentGhost, Nadia Alramli, truppo의 버전은 간단하고 빠릅니다.truppo' 버전은 1 이외의 스텝 사이즈(및 주어진 스텝 사이즈로 1단계 이상 확장되지 않는 싱글톤 요소로 나열됨)를 다루면서 동일한 민첩한 동작을 유지하는 버전을 쓰도록 권장했습니다.여기에 있습니다.

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

최선의 접근은 아니지만, 여기 2센트가 있습니다.

def getConsecutiveValues2(arr): 
    x = ""
    final = []
    end = 0
    start = 0
    for i in range(1,len(arr)) :
        if arr[i] - arr[i-1] == 1 :
            end = i
        else :
            print(start,end)
            final.append(arr[start:end+1])
            start = i
        if i == len(arr) - 1 :
            final.append(arr[start:end+1])
    return final

x = [1,2,3,5,6,8,9,10,11,12]
print(getConsecutiveValues2(x))

>> [[1, 2, 3], [5, 6], [8, 9, 10, 11]]

이 실장은, 통상의 순서 또는 불규칙한 순서로 동작합니다.

나는 같은 것을 달성해야 했지만 스텝이 불규칙할 수 있는 약간의 차이를 가지고 있었다.이것이 나의 실장입니다.

def ranges(l):
    if not len(l):
        return range(0,0)
    elif len(l)==1:
        return range(l[0],l[0]+1)
    # get steps
    sl    = sorted(l)
    steps = [i-j for i,j in zip(sl[1:],sl[:-1])]
    # get unique steps indexes range
    groups = [[0,0,steps[0]],]
    for i,s in enumerate(steps):
        if s==groups[-1][-1]:
            groups[-1][1] = i+1
        else:
            groups.append( [i+1,i+1,s] )
            g2 = groups[-2]
            if g2[0]==g2[1]:
                if sl[i+1]-sl[i]==s:
                    _=groups.pop(-2)
                    groups[-1][0] = i
    # create list of ranges 
    return [range(sl[i],sl[j]+s,s) if s!=0 else [sl[i]]*(j+1-i) for i,j,s in groups]

여기 예가 있어요.

from timeit import timeit

# for regular ranges
l = list(range(1000000))
ranges(l)
>>> [range(0, 1000000)]
l = list(range(10)) + list(range(20,25)) + [1,2,3]
ranges(l)
>>> [range(0, 2), range(1, 3), range(2, 4), range(3, 10), range(20, 25)]
sorted(l);[list(i) for i in ranges(l)]
>>> [0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24]
>>> [[0, 1], [1, 2], [2, 3], [3, 4, 5, 6, 7, 8, 9], [20, 21, 22, 23, 24]]

# for irregular steps list
l = [1, 3, 5, 7, 10, 11, 12, 100, 200, 300, 400, 60, 99, 4000,4001]
ranges(l)
>>> [range(1, 9, 2), range(10, 13), range(60, 138, 39), range(100, 500, 100), range(4000, 4002)]

## Speed test
timeit("ranges(l)","from __main__ import ranges,l", number=1000)/1000
>>> 9.303160999934334e-06

또, 입력이 세트라고 생각되는 경우는, 또 하나의 해결 방법이 있습니다.

def group_years(years):
  consecutive_years = []
  for year in years:
    close = {y for y in years if abs(y - year) == 1}
    for group in consecutive_years:
      if len(close.intersection(group)):
        group |= close
        break
    else:
      consecutive_years.append({year, *close})
  
  return consecutive_years

예를 들어:

group_years({2016, 2017, 2019, 2020, 2022})
Out[54]: [{2016, 2017}, {2019, 2020}, {2022}]

언급URL : https://stackoverflow.com/questions/2154249/identify-groups-of-consecutive-numbers-in-a-list