Tìm cụm số trong một danh sách

Question

Tôi đang phải vật lộn với điều đó, vì tôi chắc chắn rằng một chục cho-vòng không phải là giải pháp cho vấn đề này:

Có một danh sách sắp xếp các con số như

numbers = [123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430] 

và tôi muốn tạo một dict với danh sách các số, trong đó sự khác biệt của những con số (sau mỗi khác) là không quá 15. vì vậy, đầu ra sẽ là:

clusters = { 
    1 : [123, 124, 128], 
    2 : [160, 167], 
    3 : [213, 215, 230, 245, 255, 257], 
    4 : [400, 401, 402], 
    5 : [430] 
} 

My hiện tại solutio n là một chút xấu xí (tôi phải loại bỏ các bản sao ở cuối ...), tôi chắc chắn nó có thể được thực hiện theo một cách nhiệt tình.

Đây là những gì tôi làm bây giờ:

clusters = {} 
dIndex = 0 
for i in range(len(numbers)-1) : 
    if numbers[i+1] - numbers[i] <= 15 : 
     if not clusters.has_key(dIndex) : clusters[dIndex] = [] 
     clusters[dIndex].append(numbers[i]) 
     clusters[dIndex].append(numbers[i+1]) 
    else : dIndex += 1 

Answer 1

Không cần thiết nếu danh sách của bạn nhỏ, nhưng có lẽ tôi sẽ tiếp cận điều này theo kiểu "xử lý luồng": xác định trình tạo tính năng đưa đầu vào của bạn có thể lặp lại và cho các phần tử được nhóm thành các số khác nhau theo < = 15. Sau đó, bạn có thể sử dụng nó để tạo từ điển của bạn một cách dễ dàng.

def grouper(iterable): 
    prev = None 
    group = [] 
    for item in iterable: 
     if not prev or item - prev <= 15: 
      group.append(item) 
     else: 
      yield group 
      group = [item] 
     prev = item 
    if group: 
     yield group 

numbers = [123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430] 
dict(enumerate(grouper(numbers), 1)) 

in:

{1: [123, 124, 128], 
2: [160, 167], 
3: [213, 215, 230, 245, 255, 257], 
4: [400, 401, 402], 
5: [430]} 

Như một phần thưởng, điều này cho phép bạn thậm chí có nhóm của bạn chạy cho các danh sách có khả năng vô hạn (miễn là họ đang sắp xếp, tất nhiên). Bạn cũng có thể dính phần tạo chỉ mục vào chính bộ tạo (thay vì sử dụng enumerate) như là một phụ kiện nhỏ.

Answer 2

import itertools 
import numpy as np 

numbers = np.array([123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430]) 
nd = [0] + list(np.where(np.diff(numbers) > 15)[0] + 1) + [len(numbers)] 

a, b = itertools.tee(nd) 
next(b, None) 
res = {} 
for j, (f, b) in enumerate(itertools.izip(a, b)): 
    res[j] = numbers[f:b] 

Nếu bạn có thể sử dụng itertools và NumPy. Đã chỉnh sửa pairwise cho các thủ thuật lặp. Cần +1 để thay đổi chỉ mục, thêm 0 và len(numbers) vào danh sách đảm bảo các mục nhập đầu tiên và cuối cùng được bao gồm chính xác.

Bạn rõ ràng có thể làm điều này với số itertools, nhưng tôi thích tee.

Answer 3

Sử dụng máy phát điện để tách logic: (một chức năng không có một điều)

numbers = [123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430] 

def cut_indices(numbers): 
    # this function iterate over the indices that need to be 'cut' 
    for i in xrange(len(numbers)-1): 
     if numbers[i+1] - numbers[i] > 15: 
      yield i+1 

def splitter(numbers): 
    # this function split the original list into sublists. 
    px = 0 
    for x in cut_indices(numbers): 
     yield numbers[px:x] 
     px = x 
    yield numbers[px:] 

def cluster(numbers): 
    # using the above result, to form a dict object. 
    cluster_ids = xrange(1,len(numbers)) 
    return dict(zip(cluster_ids, splitter(numbers))) 

print cluster(numbers) 

Các mã trên cho tôi

{1: [123, 124, 128], 2: [160, 167], 3: [213, 215, 230, 245, 255, 257], 4: [400, 401, 402], 5: [430]} 

Answer 4

Dưới đây là một giải pháp tương đối đơn giản mà làm việc cho các danh sách hoặc máy phát điện. Nó lười biếng mang lại các cặp (group_number, element) vì vậy bạn phải thực hiện nhóm riêng biệt một cách riêng biệt nếu bạn cần nó. (Hoặc có thể bạn chỉ cần số nhóm.)

from itertools import tee 

def group(xs, gap=15): 
    # use `tee` to get two efficient iterators 
    xs1, xs2 = tee(xs) 

    # the first element is in group 0, also advance the second iterator 
    group = 0 
    yield (group, next(xs2)) 

    # after advancing xs2, this zip is pairs of consecutive elements 
    for x, y in zip(xs1, xs2): 
     # whenever the gap is too large, increment the group number 
     if y - x > gap: 
      group += 1 
     # and yield the second number in the pair 
     yield group, y