Определить различные последовательные кратные в отсортированном списке

Question

У меня есть отсортированный список и вы хотите определить последовательные множественные числа в этом списке. Список может содержать последовательные кратные разного порядка, что делает его более сложным.

В некоторых случаях тест:

[1,3,4,5] -> [[1], [3,4,5]] 
[1,3,5,6,7] -> [[1], [3], [5,6,7]] 
# consecutive multiples of 1 and 2 (or n) 
[1,2,3,7,9,11] -> [[1,2,3], [7,9,11] 
[1,2,3,7,10,12,14,25] -> [[1,2,3], [7], [10,12,14], [25]] 
# overlapping consecutives !!! 
[1,2,3,4,6,8,10] -> [[1,2,3,4], [6,8,10] 

Теперь, я понятия не имею, что я делаю. То, что я сделал это группа попарно на расстояние между числами, что было хорошее начало, но потом меня много вопросов, идентифицирующие, какой элемент в каждой паре идет, где, т.е.

# initial list  
[1,3,4,5] 
# pairs of same distance 
[[1,3], [[3,4], [4,5]] 
# algo to get the final result ? 
[[1], [3,4,5]] 

Любая помощь очень оценили.

EDIT: Возможно, упоминание того, что я хочу для этого, сделает его более понятным.

Я хочу что-то вроде преобразования:

[1,5,10,11,12,13,14,15,17,20,22,24,26,28,30] 

в

1, 5, 10 to 15 by 1, 17, 20 to 30 by 2 

Answer 1

Вот версия, которая включает в себя @ оптимизации Bakuriu в:

MINIMAL_MATCH = 3 

def find_some_sort_of_weird_consecutiveness(data): 
    """ 
    >>> find_some_sort_of_weird_consecutiveness([1,3,4,5]) 
    [[1], [3, 4, 5]] 
    >>> find_some_sort_of_weird_consecutiveness([1,3,5,6,7]) 
    [[1, 3, 5], [6], [7]] 
    >>> find_some_sort_of_weird_consecutiveness([1,2,3,7,9,11]) 
    [[1, 2, 3], [7, 9, 11]] 
    >>> find_some_sort_of_weird_consecutiveness([1,2,3,7,10,12,14,25]) 
    [[1, 2, 3], [7], [10, 12, 14], [25]] 
    >>> find_some_sort_of_weird_consecutiveness([1,2,3,4,6,8,10]) 
    [[1, 2, 3, 4], [6, 8, 10]] 
    >>> find_some_sort_of_weird_consecutiveness([1,5,10,11,12,13,14,15,17,20,22,24,26,28,30]) 
    [[1], [5], [10, 11, 12, 13, 14, 15], [17], [20, 22, 24, 26, 28, 30]] 
    """ 
    def pair_iter(series): 
     from itertools import tee 
     _first, _next = tee(series) 
     next(_next, None) 
     for i, (f, n) in enumerate(zip(_first, _next), start=MINIMAL_MATCH - 1): 
      yield i, f, n 

    result = [] 
    while len(data) >= MINIMAL_MATCH: 
     test = data[1] - data[0] 
     if (data[2] - data[1]) == test: 
      for i, f, n in pair_iter(data): 
       if (n - f) != test: 
        i -= 1 
        break 
     else: 
      i = 1 
     data, match = data[i:], data[:i] 
     result.append(match) 
    for d in data: 
     result.append([d]) 
    return result 

if __name__ == '__main__': 
    from doctest import testmod 
    testmod() 

Он обрабатывает все ваши текущие тестовые примеры. Дайте мне новые неудачные тестовые примеры, если они у вас есть.

Как уже упоминалось в комментариях ниже, я предполагаю, что кратчайшая последовательность представляет собой три элемента, так как последовательность из двух тривиальна.

См. http://docs.python.org/2/library/itertools.html для объяснения попарного итератора.

Answer 2

Я бы начать с перечнем разницы.

length_a = len(list1) 
diff_v = [list1[j+1] - list1[j] for j in range(length_a-1)] 

так [1,2,3,7,11,13,15,17] становится [1,1,4,4,2,2,2]

теперь легко

Answer 3

вы можете просто следить за вашего последнего выходного значения, как вы идете по:

in_ = [1, 2, 3, 4, 5] 
out = [[in[0]]] 
for item in in_[1:]: 
    if out[-1][-1] != item - 1: 
     out.append([]) 
    out[-1].append(item) 

Answer 4

я группа список его разница между индексом и значением:

from itertools import groupby 
lst = [1,3,4,5] 
result = [] 
for key, group in groupby(enumerate(lst), key = lambda (i, value): value - i): 
    result.append([value for i, value in group]) 
print result 
[[1], [3, 4, 5]] 

Что я сделал?

# at first I enumerate every item of list: 
print list(enumerate(lst)) 
[(0, 1), (1, 3), (2, 4), (3, 5)] 

# Then I subtract the index of each item from the item itself: 
print [ value - i for i, value in enumerate(lst)] 
[1, 2, 2, 2] 

# As you see, consecutive numbers turn out to have the same difference between index and value 
# We can use this feature and group the list by the difference of value minus index 
print list(groupby(enumerate(lst), key = lambda (i, value): value - i)) 
[(1, <itertools._grouper object at 0x104bff050>), (2, <itertools._grouper object at 0x104bff410>)] 

# Now you can see how it works. Now I just want to add how to write this in one logical line: 
result = [ [value for i, value in group] 
    for key, group in groupby(enumerate(lst), key = lambda (i, value): value - i)] 
print result 
[[1], [3, 4, 5]] 

подхода для определения последовательных кратного п

Давайте посмотрим на этот список,

lst = [1,5,10,11,12,13,14,15,17,21,24,26,28,30] 

особенно на различиях между соседними элементами и различием разностей три последовательных элементов :

1, 5, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 28, 30 
    4, 5, 1, 1, 1, 1, 1, 2, 4, 3, 2, 2, 2 
     1, -4, 0, 0, 0, 0, 1, 2, -1, -1, 0, 0 

Мы видим, что в третьей строке есть нули, всякий раз, когда в первой строке есть соединительные кратные. Если мы математически мыслим, то 2-я производная от линейных сечений функций также равна нулю. Так что позволяет использовать это свойство ...

«второй производной» списка lst можно вычислить, как этот

lst[i+2]-2*lst[i+1]+lst[i] 

Обратите внимание, что это определение разности второго порядка «выглядит» два индекса вперед. Теперь вот код обнаружения последовательных мультипликатора:

from itertools import groupby 
# We have to keep track of the indexes in the list, that have already been used 
available_indexes = set(range(len(lst))) 
for second_order_diff, grouper in groupby(range(len(lst)-2), key = lambda i: lst[i+2]-2*lst[i+1]+lst[i]): 
    # store all not-consumed indexes in a list 
    grp_indexes = [i for i in grouper if i in available_indexes] 

    if grp_indexes and second_order_diff == 0: 
     # There are consecutive multiples 
     min_index, max_index = grp_indexes[0], grp_indexes[-1] + 2 
     print "Group from ", lst[min_index], "to", lst[max_index], "by", lst[min_index+1]-lst[min_index] 
     available_indexes -= set(range(min_index, max_index+1)) 
    else: 
     # The not "consumed" indexes in this group are not consecutive 
     for i in grp_indexes: 
      print lst[i] 
      available_indexes.discard(i) 
# The last two elements could be lost without the following two lines 
for i in sorted(available_indexes): 
    print lst[i] 

Выход:

1 
5 
Group from 10 to 15 by 1 
17 
21 
Group from 24 to 30 by 2