CODEWITHSUNDEEP
pythonalgorithmsequences
windsound
windsound

Reputation: 666

Insertions algorithm in sequence python

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!

Upvotes: 0

Views: 342

Answers (3)

Mark Tolonen
Mark Tolonen

Reputation: 177610

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

Upvotes: 2

g.d.d.c
g.d.d.c

Reputation: 47988

What does your insertion_sequence_list look like? If it is something along the lines of this:

[('999', 2),
 ('888', 3)]

Then you should sort it in descending order based on the second value:

from operator import itemgetter

ins_seq_li.sort(key = itemgetter(1), reverse = True)

Then, when you do your inserts from that list you're adding at the greatest index 1st, so your prior inserts should be fine.

Upvotes: 1

ecatmur
ecatmur

Reputation: 157344

Since only the later positions will change, if you collect your insertion operations, sort them and then insert latest-first then everything will work.

insertion_ops = [(position, insertion) for ...]
for position, insertion in reversed(sorted(insertion_ops)):
    sequence[position:position] = insertion

Alternatively you can convert insertion positions to negative positions i.e. offsets from the end; you will still need to sort them first though.

Upvotes: 2

Related Questions