Как заменить последовательные значения в списке, используя другой список в качестве ссылки?

Question

У меня есть такой список:

list_target = [4, 5, 6, 7, 12, 13, 14]
list_primer = [3, 11]

Итак, list_target состоит из блоков последовательных значений, между которыми находятся скачки значений (например, от 7 до 12). list_primer состоит из значений в начале этих блоков. Элементы в list_primer генерируются в другом процессе.

Мой вопрос таков: для каждого элемента list_primer как я могу идентифицировать блок в list_target и заменить их значения тем, что я хочу? Например, если я решу заменить значения в первом блоке на 1, а во втором на 0, результат будет выглядеть следующим образом:

list_target_result = [1, 1, 1, 1, 0, 0, 0]

Answer 1

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

list_target = [4, 5, 6, 7, 12, 13, 14]
list_primer = [3, 11]

block_values = [1, 0]

result = []

for i, primer in enumerate(list_primer):
    for j, target in enumerate(list_target):
        if target == primer+1:
            primer += 1
            result.append(block_values[i])
        else:
            continue
print(result)

[1, 1, 1, 1, 0, 0, 0]

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

Answer 2

Вот решение с использованием numpy.

import numpy as np

list_target = np.array([4, 5, 6, 7, 12, 13, 14])
list_primer = np.array([3, 11])

values = [1, 0]

ix  = np.searchsorted(list_target, list_primer)
# [0,4]

blocks = np.split(list_target, ix)[1:]
# [array([4, 5, 6, 7]), array([12, 13, 14])]

res = np.concatenate([np.full(s.size, values[i]) for i,s in enumerate(blocks)])
# array([1, 1, 1, 1, 0, 0, 0])

Answer 3

Вот решение, которое работает в O(n), где n=len(list_target). Предполагается, что ваш список list_target является последовательным в описанном вами порядке (увеличивается на единицу внутри блока, увеличивается на единицу между блоками).

Возвращает словарь с началом каждого блока в качестве ключа (потенциал праймеры) и нижний и верхний индексы этого блока в list_target в качестве значений. Тогда доступ к этому диктату будет O(1).

list_target = [4, 5, 6, 7, 12, 13, 14]
list_primer = [3, 11]

block_dict = dict()
lower_idx = 0
upper_idx = 0 

for i, val in enumerate(list_target):  # runs in O(n)
  upper_idx = i + 1
  if i == len(list_target) - 1:  # for last block in list
    block_dict[list_target[lower_idx] - 1] = (lower_idx, upper_idx)
    break
  if list_target[i + 1] - list_target[i] != 1:  #if increment more than one, save current block to dict, reset lower index
    block_dict[list_target[lower_idx] - 1] = (lower_idx, upper_idx)
    lower_idx = i + 1

Вот результаты:

print(block_dict)  # quick checks
>>>> {3: (0,4), 11: (4,7)}

for p in list_primer:  # printing the corresponding blocks.
    lower, upper = block_dict[p]  # dict access in O(1)
    print(list_target[lower:upper])
>>>> [4, 5, 6, 7]
     [12, 13, 14]

# getting the indices for first primer marked as in your original question:
list_target_result = [0] * len(list_target)
lower_ex, upper_ex = block_dict[3]
list_target_result[lower_ex: upper_ex] = [1]*(upper_ex-lower_ex)
print(list_target_result)
>>>> [1, 1, 1, 1, 0, 0, 0]

Answer 4

Модификация метода для поиска групп строго увеличивающихся чисел в списке

def group_seq(l, list_primer): 
    " Find groups which are strictly increasing or equals next list_primer value "
    temp_list = cycle(l)
    temp_primer = cycle(list_primer)

    next(temp_list) 
    groups = groupby(l, key = lambda j: (j + 1 == next(temp_list)) or (j == next(temp_primer))) 
    for k, v in groups: 
        if k: 
            yield tuple(v) + (next((next(groups)[1])), )

Использование group_seq для поиска строго увеличивающихся блоков в list_target

list_target = [4, 5, 6, 7, 12, 13, 14]
list_primer = [3, 11]
block_values = [1, 0]

result = []
for k, v in zip(block_values, group_seq(list_target, list_primer)):
    result.extend([k]*len(v))  # k is value from block_values
                               # v is a block of strictly increasing numbers
                               # ie. group_seq(list_target) creates sublists
                               # [(4, 5, 6, 7), (12, 13, 14)]

print(result)
Out: [1, 1, 1, 1, 0, 0, 0]