Вставить элемент между двумя соседними элементами списка, которые удовлетворяют условию

Question

В python, что такое чистый способ вставки элемента между любыми двумя элементами, которые удовлетворяют условию?

Вызов как:

insert_between([1,2,3,4,7,8,9,15,16], 0, lambda x,y: x + 1 != y) 

следует производить:

[1,2,3,4,0,7,8,9,0,15,16] 

Есть ли лучший способ, чем перебирать и добавить ко второму списку?

Answer 1

>>> def insert_between(iterable, fill, cond): 
...  iterable = iter(iterable) 
...  prev = next(iterable) 
...  yield prev 
...  for cur in iterable: 
...    if cond(prev, cur): 
...      yield fill 
...    yield cur 
...    prev = cur 
... 
>>> 
>>> list(insert_between([1,2,3,4,7,8,9,15,16], 0, lambda x,y: x + 1 != y)) 
[1, 2, 3, 4, 0, 7, 8, 9, 0, 15, 16] 

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

Answer 2

версия katrielalex, вероятно, является наиболее эффективным способом ее выполнения, как с точки зрения времени, так и с точки зрения памяти. Вот аналогичная версия, которая возвращает новый список, а не итератор.

def insert_between(items, insert_item, compare): 
    result = items[:1] 
    prev = result[0] 
    for item in items[1:]: 
     if not compare(prev, item): 
      result.append(insert_item) 
     result.append(item) 
     prev = item 
    return result 

Если вам нужно изменить список на месте, без использования памяти для двух списков, вы можете выполнить назначение среза. Мне не нравится использование индекса и while здесь, но поскольку мы изменяем список, как мы идем, это кажется самым простым способом в этом случае. Это будет медленнее, особенно с большими списками, но вы также сохраните большую часть памяти с большими списками.

def insert_between(items, insert_item, compare): 
    i = 1 
    while i < len(items): 
     if not compare(items[i-1], items[i]): 
      items[i:i] = [insert_item] 
      i += 1 
     i += 1 
    return items 

Answer 3

Может быть легко сделать с помощью функции лямбды и уменьшить

l=[1, 2, 3, 4, 7, 8, 9, 15, 16] 
f = lambda l, i: l+[0,i] if l and l[-1]+1!=i else l+[i] 
print reduce(f, l, []) 
[1, 2, 3, 4, 0, 7, 8, 9, 0, 15, 16]