Làm cách nào để thực hiện một `phạm vi nghịch đảo`, tức là tạo một phạm vi nhỏ gọn dựa trên một tập hợp các số?

Question

Python có một phương pháp range, cho phép cho các công cụ như:

>>> range(1, 6) 
[1, 2, 3, 4, 5] 

Những gì tôi đang tìm kiếm là loại ngược lại: mất một danh sách các số, và trở về điểm bắt đầu và kết thúc.

>>> magic([1, 2, 3, 4, 5]) 
[1, 5] # note: 5, not 6; this differs from `range()` 

Đây là đủ dễ dàng để làm cho ví dụ trên, nhưng là nó có thể cho phép những khoảng trống hoặc nhiều dãy là tốt, trở về phạm vi trong một định dạng chuỗi PCRE-như thế nào? Something như thế này:

>>> magic([1, 2, 4, 5]) 
['1-2', '4-5'] 
>>> magic([1, 2, 3, 4, 5]) 
['1-5'] 

Edit: Tôi đang tìm kiếm một giải pháp Python, nhưng tôi chào đón ví dụ làm việc trong các ngôn ngữ khác là tốt. Tìm hiểu thêm về thuật toán hiệu quả, thanh lịch. Câu hỏi về tiền thưởng: có bất kỳ ngôn ngữ lập trình nào có phương pháp tích hợp cho điều này không?

Answer 1

Một thủ thuật rất hay để đơn giản hóa mã là nhìn vào sự khác biệt của mỗi phần tử của danh sách được sắp xếp và chỉ số của nó:

a = [4, 2, 1, 5] 
a.sort() 
print [x - i for i, x in enumerate(a)] 

bản in

[1, 1, 2, 2] 

Mỗi lần chạy cùng một số tương ứng với một số liên tiếp trong a. Bây giờ chúng tôi có thể sử dụng itertools.groupby() để trích xuất các lần chạy này.Dưới đây là đoạn code hoàn chỉnh:

from itertools import groupby 

def sub(x): 
    return x[1] - x[0] 

a = [5, 3, 7, 4, 1, 2, 9, 10] 
ranges = [] 
for k, iterable in groupby(enumerate(sorted(a)), sub): 
    rng = list(iterable) 
    if len(rng) == 1: 
     s = str(rng[0][1]) 
    else: 
     s = "%s-%s" % (rng[0][1], rng[-1][1]) 
    ranges.append(s) 
print ranges 

in

['1-5', '7', '9-10'] 

Answer 2

Sắp xếp các số, tìm phạm vi liên tiếp (nhớ nén RLE?).

Something như thế này:

input = [5,7,9,8,6, 21,20, 3,2,1, 22,23, 50] 

output = [] 
first = last = None # first and last number of current consecutive range 
for item in sorted(input): 
    if first is None: 
    first = last = item # bootstrap 
    elif item == last + 1: # consecutive 
    last = item # extend the range 
    else: # not consecutive 
    output.append((first, last)) # pack up the range 
    first = last = item 
# the last range ended by iteration end 
output.append((first, last)) 

print output 

Kết quả: [(1, 3), (5, 9), (20, 23), (50, 50)]. Bạn tìm ra phần còn lại :)

Answer 3

Đây là loại thanh lịch nhưng cũng khá kinh tởm, tùy thuộc vào quan điểm của bạn. :)

import itertools 

def rangestr(iterable): 
    end = start = iterable.next() 
    for end in iterable: 
     pass 
    return "%s" % start if start == end else "%s-%s" % (start, end) 

class Rememberer(object): 
    last = None 

class RangeFinder(object): 
    def __init__(self): 
     self.o = Rememberer() 

    def __call__(self, x): 
     if self.o.last is not None and x != self.o.last + 1: 
      self.o = Rememberer() 
     self.o.last = x 
     return self.o 

def magic(iterable): 
    return [rangestr(vals) for k, vals in 
      itertools.groupby(sorted(iterable), RangeFinder())] 


>>> magic([5,7,9,8,6, 21,20, 3,2,1, 22,23, 50]) 
['1-3', '5-9', '20-23', '50'] 

Giải thích: nó sử dụng itertools.groupby vào nhóm các yếu tố được sắp xếp lại với nhau bằng một chìa khóa, nơi chính là một đối tượng Rememberer. Lớp RangeFinder giữ đối tượng Rememberer miễn là một loạt các mục liên tiếp thuộc cùng một khối phạm vi. Khi bạn đã thoát khỏi một khối nhất định, nó sẽ thay thế Rememberer để khóa sẽ không so sánh bằng nhau và groupby sẽ tạo một nhóm mới. Khi groupby đi qua danh sách được sắp xếp, nó sẽ chuyển từng phần tử thành rangestr, cấu trúc chuỗi bằng cách ghi nhớ phần tử đầu tiên và phần tử cuối cùng và bỏ qua mọi thứ ở giữa.

Có lý do thực tế nào để sử dụng thay vì 9000's answer không? Chắc là không; về cơ bản nó là cùng một thuật toán.

Answer 4

Kể từ 9000 đánh tôi với nó, tôi sẽ chỉ gửi phần thứ hai của mã, đó in dãy PCRE giống như từ tính trước đây output cộng với loại kiểm tra thêm:

for i in output: 
    if not isinstance(i, int) or i < 0: 
     raise Exception("Only positive ints accepted in pcre_ranges") 
result = [ str(x[0]) if x[0] == x[1] else '%s-%s' % (x[0], x[1]) for x in output ] 
print result 

Output: ['1-3', '5-9', '20-23', '50']

Answer 5

tôi nghĩ bạn có thể muốn giải pháp clojure khái quát hóa của tôi.

(def r [1 2 3 9 10]) 

(defn successive? [a b] 
    (= a (dec b))) 

(defn break-on [pred s] 
    (reduce (fn [memo n] 
      (if (empty? memo) 
       [[n]] 
       (if (pred (last (last memo)) n) 
       (conj (vec (butlast memo)) 
         (conj (last memo) n)) 
       (conj memo [n])))) 
      [] 
      s)) 

(break-on successive? r) 

Answer 6

Hãy thử máy phát điện!

# ignore duplicate values 
l = sorted(set([5,7,9,8,6, 21,20, 3,2,1, 22,23, 50])) 

# get the value differences 
d = (i2-i1 for i1,i2 in zip(l,l[1:])) 

# get the gap indices 
gaps = (i for i,e in enumerate(d) if e != 1) 

# get the range boundaries 
def get_ranges(gaps, l): 
    last_idx = -1 
    for i in gaps: 
    yield (last_idx+1, i) 
    last_idx = i 
    yield (last_idx+1,len(l)-1) 

# make a list of strings in the requested format (thanks Frg!) 
ranges = [ "%s-%s" % (l[i1],l[i2]) if i1!=i2 else str(l[i1]) \ 
    for i1,i2 in get_ranges(gaps, l) ] 

này đã trở nên khá đáng sợ, tôi nghĩ :)