Insérer un élément entre deux éléments de liste adjacents répondant à une condition

Question

En python, comment insérer un élément entre deux éléments répondant à une condition?

Un appel comme:

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

devrait produire:

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

Y at-il une meilleure façon que pour itérer et ajouter à la deuxième liste?

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] 

C'est à peu près aussi efficace que vous aurez, parce que vous allez devoir faire un passage à travers la liste de toute façon et cela fait une seule passe. Notez qu'il s'agit d'un générateur, vous devez donc le convertir en liste si vous avez besoin de toutes les valeurs à la fois.

Answer 2

@ La version de katrielalex est probablement la façon la plus efficace de le faire, à la fois en termes de temps et de mémoire. Voici une version similaire qui renvoie une nouvelle liste plutôt qu'un itérateur.

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 

Si vous devez modifier une liste en place, sans utiliser la mémoire pour deux listes, vous pouvez effectuer une attribution de tranches. Je déteste utiliser l'index et la boucle while ici, mais puisque nous modifions la liste au fur et à mesure, nous semblons la méthode la plus simple dans ce cas. Ce sera plus lent, surtout avec de grandes listes, mais vous économiserez aussi le plus de mémoire avec de grandes listes.

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

peut se faire facilement en utilisant la fonction lambda et réduire

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]