Подсчет количества элементов в неперекрывающихся подинтервалах массива

Question

Я хочу посчитать количество элементов в неперекрывающихся подпоследовательностях списка. Например, в lst, показанном ниже:

lst = [0.2,1.3,2.2,3.5]
L = 0.5
for x in lst:
lb = x   # lowebound
ub = x+L   # upperbound
print(lb,ub)

Выход

  0.2 0.7  count=1
  1.3 1.8  count=1
  2.2 2.7  count=1
  3.5 4.0  count=1

Как мы видим, эти интервалы не перекрываются . Кроме того, в каждом из интервалов [lb, ub] у нас есть только один элемент, который принадлежит lst, поэтому count = 1 за интервал. Однако есть сложный случай, как указано ниже

 nlst = [0.2,0.6,2.2,3.8]

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

  0.2 0.7
  0.6 1.1
  2.2 2.7
  3.8 4.3

Теперь, когда 0,6 входит в первый интервал [0,2,0,7], существует наложение, которое нам не нужно. Желаемый вывод

  0.2 0.7   count = 2
  2.2 2.7   count = 1
  3.8 4.3   count = 1

Эта проблема может быть легко решена, если исходный массив разбить на подмассивы, однако в массивах, содержащих тысячи чисел, такие методы становятся вычислительно интенсивными. В приведенных выше примерах в качестве выходных данных я показываю интервалы, что просто объясняет мою проблему. Я только хочу рассчитывать за интервал. Могу ли я помочь?

Заранее спасибо.

Answer 1

Это будет работать

list = [0.2,0.3,0.4,2.2,2.3,3.5,3.8,3.9,7.1]
interval = 0.5
list.sort()
answer = []
def calculate (list):
  count = 1
  check = list[0]
  del list[0] 
  list_copy = [i for i in list]
  for index, item in enumerate(list_copy):
    if check + interval > list_copy[index] :
      count += 1
      list.remove(item)
  answer.append(count)
  if (len(list)):
    calculate(list)
  else:
    return 
calculate(list);
print answer

Answer 2

Как насчет этого?

lst = [0.2, 0.6, 2.2, 3.8]
L = 0.5

count = None
counts = []
append = counts.append
ub = lst[0]

for x in lst:
    if x < ub:
        count += 1
    else:
        append(count)
        count = 1
        ub = x + L

counts = counts[1:] + [count]

print(counts)

Обновление: и если вы хотите собрать интервалы:

lst = [0.2, 0.6, 2.2, 3.8]
L = 0.5

ival = count = None
ivals, counts = [], []
ival = (None, lst[0])

for x in lst:
    if x < ival[1]:
        count += 1
    else:
        ivals.append(ival)
        counts.append(count)
        ival = x, x + L
        count = 1

ivals = ivals[1:] + [ival]
counts = counts[1:] + [count]

print(ivals)
print(counts)

В качестве альтернативы вы можете создать список с тройками (нижняя граница, верхняя граница, количество) аналогичным образом.