Insertions algorithm in sequence python

Question

I am relatively new in Python, and get this quesiton I want to ask:

There is a length of 10000 sequence made by number 0~9,

Goal: Randomly inserting 10 number sequences (already know their nunbers) in 10 different location, and record the location before insertion.

So, the function will be:

def insertion( insertion_sequence_list, long_sequence ):
    #modifying the long sequence
    return inserted_long_sequence and inserted_positions

How can I do it? The problem I am facing is whenever I make an insert 1 at random location, the later positions will change:

For example:

I have 123456789123456789 as long sequence

When I insert "999" into the 2nd position (129993456789123456789). But later, when I want to insert a sequence "888" at 3rd position, I want it to be original position, I want it to be-- 129993*888*456789123456789. But in fact it will be 129*888*993456789123456789 instead. I dont know how it can fix this.

Please let me know if there is any duplication posibility, I do not even know what this question belongs :\

Thanks for all comments, views, and answers!

Answer 1

You can do this by sorting on location and applying in reverse order. Is order important in case of ties? Then sort only by location, not location and sequence, so they will insert in the correct order. For example, if inserting 999@1 then 888@1, if you sorted on both values you'd get 888@1,999@1.

12345
18889992345

But sorting only by location with a stable sort gives 999@1,888@1

12345
1999888345

Here's the code:

import random
import operator

# Easier to use a mutable list than an immutable string for insertion.
sequence = list('123456789123456789')
insertions = '999 888 777 666 555 444 333 222 111'.split()
locations = [random.randrange(len(sequence)) for i in xrange(10)]
modifications = zip(locations,insertions)
print modifications
# sort them by location.
# Since Python 2.2, sorts are guaranteed to be stable,
# so if you insert 999 into 1, then 222 into 1, this will keep them
# in the right order
modifications.sort(key=operator.itemgetter(0))
print modifications
# apply in reverse order
for i,seq in reversed(modifications):
    print 'insert {} into {}'.format(seq,i)
    # Here's where using a mutable list helps
    sequence[i:i] = list(seq)
    print ''.join(sequence)

Result:

[(11, '999'), (8, '888'), (7, '777'), (15, '666'), (12, '555'), (11, '444'), (0, '333'), (0, '222'), (15, '111')]
[(0, '333'), (0, '222'), (7, '777'), (8, '888'), (11, '999'), (11, '444'), (12, '555'), (15, '666'), (15, '111')]
insert 111 into 15
123456789123456111789
insert 666 into 15
123456789123456666111789
insert 555 into 12
123456789123555456666111789
insert 444 into 11
123456789124443555456666111789
insert 999 into 11
123456789129994443555456666111789
insert 888 into 8
123456788889129994443555456666111789
insert 777 into 7
123456777788889129994443555456666111789
insert 222 into 0
222123456777788889129994443555456666111789
insert 333 into 0
333222123456777788889129994443555456666111789