Inserting while itterating

[Samuel Walters]

| Thomas Guettler said |

> Hi,
> 
> Simple excerise:
> 
> You have a sorted list of integers:
> l=[1, 2, 4, 7, 8, 12]
> 
> and you should fill all gaps:
> 
> result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
> 
> How would you code this?
> 
> Constrain: The original list should be changed, don't create a copy.
> 
>   thomas

The word "exercise" raises my suspicions that this is a homework problem.
You know you only cheat yourself when you ask others to do your homework.

#simple, but only works for ints
l = [1, 2, 4, 7, 8, 12]
l = range(l[0],l[-1]+1)
print l


#naive, but broader
#only use when sorting is cheap.
l = [1, 2, 4, 7, 8, 12]
#iterate through each possible item.
for x in range(l[0],l[-1]+1): 
    if x not in l:
        l.append(x)
l.sort()
print l


#missing-merge: more general pattern
#useful for strange, hard to sort data:
#where sorting is expensive, 
#but comparison is cheap.
l = [1, 2, 4, 7, 8, 12]
missing = []
#iterate through each possible item
for x in range(l[0], l[-1]+1):
    #build a list of each missing item.
    if x not in l:
        missing.append(x)
#merge the two lists
for x in range(0, len(l) + len(missing) - 1):
    if l[x] > missing[0]:
        l = l[:x] + missing[0:1] + l[x:]
        missing.pop(0)
print l

Sam Walters.

-- 
Never forget the halloween documents.
http://www.opensource.org/halloween/
""" Where will Microsoft try to drag you today?
    Do you really want to go there?"""