Найти число пробегов с настраиваемым расстоянием между числами - PullRequest
Новая
       9

Найти число пробегов с настраиваемым расстоянием между числами

0 голосов
/ 10 июня 2018

У меня есть отсортированный список целых чисел, и я хочу найти число, указанное в этом списке.Я видел много примеров, когда искали прогоны чисел, которые увеличиваются на 1, но я также хочу искать прогоны чисел, где разница между числами настраивается.

Например, скажем, у меня есть следующий список чисел:

nums = [1, 2, 3, 6, 7, 8, 10, 12, 14, 18, 25, 28, 31, 39]

Используя найденный пример здесь , я могу найти следующие числа прогонов: 

[[1, 2, 3], [6, 7, 8], [10], [12], [14], [18], [25], [28], [31], [39]]

Однако я хочу поискать прогоны чиселгде разница между двумя числами может быть больше, чем просто 1. Например, я хочу, чтобы все пробеги чисел проходили с расстоянием, меньшим или равным 2. 

[[1, 2, 3], [6, 7, 8, 10, 12, 14], [18], [25], [28], [31], [39]]

Или, возможно, я хочу, чтобы все пробеги чисел срасстояние меньше или равно 3. 

[[1, 2, 3, 6, 7, 8, 10, 12, 14], [18], [25, 28, 31], [39]]

Вот функция, с которой я сейчас работаю, чтобы получить число пробегов на расстоянии 1. 

def runs(seq, n):
    result = []
    for s in seq:
        if not result or s != result[-1][-1] + n:
            # Start a new run if we can't continue the previous one.
            result.append([])
        result[-1].append(s)
    return result

Стекущая функция, если я установлю n=1, то я найду все последовательные числовые последовательности.Если я установлю n=2, то найду только [8, 10, 12, 14].Как я могу изменить эту функцию, чтобы найти число прогонов, которые меньше или равны n?

Я хочу иметь возможность сделать это: 

runs(num, 2)
[[1, 2, 3], [6, 7, 8, 10, 12, 14], [18], [25], [28], [31], [39]]

Ответы [ 3 ]

0 голосов
/ 10 июня 2018 
def runs(nums, n):
    idx = np.flatnonzero(np.ediff1d(nums, n + 1, n + 1) > n)
    return [nums[i1:i2] for i1, i2 in zip(idx[:-1], idx[1:])]

Тогда 

>>> runs(nums, 3)
[[1, 2, 3, 6, 7, 8, 10, 12, 14], [18], [25, 28, 31], [39]]
0 голосов
/ 10 июня 2018 
In [4]: def runs(seq, n):
   ...:     indexs = [i for i in range(len(seq)) if i==0 or seq[i]-seq[i-1]>n]
   ...:     return [seq[a:b] for a, b in zip(indexs, indexs[1:]+[len(seq)])]
   ...: 
   ...: 

In [5]: runs(nums, 3)
Out[5]: [[1, 2, 3, 6, 7, 8, 10, 12, 14], [18], [25, 28, 31], [39]]

In [6]: runs(nums, 2)
Out[6]: [[1, 2, 3], [6, 7, 8, 10, 12, 14], [18], [25], [28], [31], [39]]
0 голосов
/ 10 июня 2018

Итеративное группирование с for

Я просто исправляю ваш код с этим.Чтобы упростить вещи, вы можете инициализировать result с помощью seq[0]. 

def runs(seq, n):
    result = [[seq[0]]]
    for s in seq[1:]:
        if s - result[-1][-1] > n:  # Keep it simple. Compare the delta.
            result.append([])
        result[-1].append(s)

    return result


>>> runs(nums, 1)
[[1, 2, 3], [6, 7, 8], [10], [12], [14], [18], [25], [28], [31], [39]]
>>> runs(nums, 2)
[[1, 2, 3], [6, 7, 8, 10, 12, 14], [18], [25], [28], [31], [39]]

pandas.GroupBy

Если вы хотите получитьНеобычно, вы можете использовать идиому groupby, упрощенную с помощью панд. 

import pandas as pd

def runs2(seq, n):
    s = pd.Series(seq)
    return s.groupby(s.diff().gt(n).cumsum()).apply(pd.Series.tolist).tolist()


>>> runs2(nums, 3)
[[1, 2, 3, 6, 7, 8, 10, 12, 14], [18], [25, 28, 31], [39]]

Здесь есть два основных компонента: группер (предикат, который вы группируете)on) и функция agg (функция, которую вы примените к каждой группе)

Группер равен s.diff().gt(n).cumsum(), с разбивкой вычисляет три вещи:

  1. Поэлементноразница в seq с использованием diff
  2. Логическая маска, указывающая, больше ли разница, чем n
  3. Выполнение кумулятивной суммы (или подсчета) для определения групп

Вывод этой операции 

s.diff().gt(n).cumsum()

0     0
1     0
2     0
3     1
4     1
5     1
6     1
7     1
8     1
9     2
10    3
11    4
12    5
13    6
dtype: int64

Функция agg pd.Series.tolist, которая преобразует любую серию в список.Вот что нам нужно здесь, вложенный список.

...