삽입 알고리즘은

Question

는 파이썬에서 비교적 새로운 오전, 내가 물어보고 싶은이 후 질문을받을 무작위로 삽입 10 개의 번호 순서 (이미 수련자를 알고 있음)를 10 개의 다른 위치에두고 삽입하기 전에 위치를 기록하십시오.

그래서, 기능은 다음과 같습니다

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

내가 어떻게 할 수 있습니까? 나는 임의 위치에 삽입 일을 할 때마다 내가 직면하고있는 문제가, 나중에 위치는 변경됩니다 : 예를 들어

:

내가 한 123456789123456789 순서

이 난에 "999"을 삽입 할 때 두 번째 위치 (129993456789123456789). 그러나 나중에 세 번째 위치에 시퀀스 "888"을 삽입하려면 원래 위치로 원한다. - 129993 * * 456789123456789. 그러나 실제로 129 * * 993456789123456789가됩니다. 나는 이것을 어떻게 고칠 수 있는지 모른다.

내가 심지어이 질문이 속한 모르는 어떤 복제있는 posibility이 있으면 알려 주시기 바랍니다 : 모든 코멘트, 뷰 및 답변

감사합니다 \!

Answer 1

위치를 정렬하고 역순으로 적용하면됩니다. 동점의 경우에 순서가 중요합니까? 그런 다음 위치 및 순서가 아닌 위치별로 정렬해야 올바른 순서로 삽입됩니다. 예를 들어, 999 @ 1 다음에 888 @ 1을 삽입하는 경우 두 값을 모두 정렬하면 888 @ 1,999 @ 1이됩니다.

12345 
18889992345 

하지만 안정된 종류와 위치에 따라 분류하는 것은 999 일

12345 
1999888345 

@ 1888 @ 여기에 코드입니다 제공 :

이

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) 

결과 :

[(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 

Answer 2

이후 위치 만 변경되므로 삽입 작업을 수집하고 정렬 한 다음 가장 먼저 삽입하면 모든 것이 작동합니다.

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

또는 삽입 위치를 음수 위치 즉 끝에서부터 오프셋으로 변환 할 수 있습니다. 당신은 여전히 ​​그들을 먼저 정렬해야합니다.

Answer 3

insertion_sequence_list는 어떤 모습입니까? 그것은이의 라인을 따라 뭔가 경우 : 다음

from operator import itemgetter 

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

, 당신은 그 목록 당신 '에서 삽입을 수행 다음

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

당신은 두 번째 값을 기준으로 내림차순으로 정렬한다 가장 큰 인덱스 1에 추가하기 때문에 이전 삽입이 잘되어야합니다.