couple implementations of partial shuffling of a string

partialshuffle.py

import random

def partial_shuffle(st, p=20):
    p = int(round(p/100.0*len(st)))
    ds = dict([(c, i) for c, i in enumerate(st)])

    shuffled = list()
    pick_index = random.choice
    add_to_list = shuffled.append
    
    for i in range(p):
        ci = pick_index(ds.keys())
        add_to_list(ds[ci])
        del ds[ci]

    res = str()
    for i in xrange(len(st)):
        if i in ds.keys():
            res = res + ds[i]
            continue
        res = res + shuffled.pop()

    return res

from collections import OrderedDict

def partial_shuffle2(st, p=20):
    p = int(round(p/100.0*len(st)))
    ds = dict([(c, i) for c, i in enumerate(st)])

    shuffled = list()
    pick_index = random.choice
    add_to_list = shuffled.append
    
    for i in range(p):
        ci = pick_index(ds.keys())
        add_to_list(ds[ci])
        del ds[ci]

    res = str()
    for i in xrange(len(st)):
        if ds.has_key(i):
            res = res + ds[i]
            continue
        res = res + shuffled.pop()

    return res

def partial_shuffle3(st, p=20):
    p = int(round(p/100.0*len(st)))
    ds = dict([(c, i) for c, i in enumerate(st)])

    shuffled = list()

    for i in range(p):
        ci = random.choice(ds.keys())
        shuffled.append(ds[ci])
        del ds[ci]

    res = str()
    for i in xrange(len(st)):
        if ds.has_key(i):
            res = res + ds[i]
            continue
        res = res + shuffled.pop()

    return res

from copy import deepcopy
def partial_shuffle4(st, p=20):
    p = int(round(p/100.0*len(st)))

    idx = range(len(s))
    sample = random.sample(idx, p)

    sampleq = deepcopy(sample)
    
    res=str()
    for i in range(len(st)):
        if i in sample:
            res += st[sampleq.pop()]
            idx.remove(i)
            continue
        res += st[i]

    return res

def partial_shuffle5(st, p=20):
    p = int(round(p/100.0*len(st)))

    idx = range(len(s))
    sample = random.sample(idx, p)
    
    res=str()
    samptrav = 1
    for i in range(len(st)):
        if i in sample:
            res += st[sample[-samptrav]]
            samptrav += 1
            continue
        res += st[i]

    return res

from ngram import NGram
import time
results = dict()
iters = 200000

print 'partial_shuffle'
start1 = time.clock()
for i in range(iters):
    s = 'abcdefghij'
    r = s
#    while r == s:
    r = partial_shuffle(s, 20)
    #print 'r: ', r, NGram.compare(r, s)
end1 = time.clock() - start1
print end1
results['partial_shuffle'] = end1

print '------------'
print 'partial_shuffle2'
start1 = time.clock()
for i in range(iters):
    s = 'abcdefghij'
    r=s
#    while r == s:
    r = partial_shuffle2(s, 20)
        
    #print 'r: ', r, NGram.compare(r, s)
end1 = time.clock() - start1
print end1
results['partial_shuffle2'] = end1

print '------------'
print 'partial_shuffle3'
start1 = time.clock()
for i in range(iters):
    s = 'abcdefghij'
    r=s
#    while r == s:
    r = partial_shuffle3(s, 20)
        
    #print 'r: ', r, NGram.compare(r, s)
end1 = time.clock() - start1
print end1
results['partial_shuffle3'] = end1

print '------------'
print 'partial_shuffle4'
start1 = time.clock()
for i in range(iters):
    s = 'abcdefghij'
    r=s
#    while r == s:
    r = partial_shuffle4(s, 20)
        
    #print 'r: ', r, NGram.compare(r, s)
end1 = time.clock() - start1
print end1
results['partial_shuffle4'] = end1

print '------------'
print 'partial_shuffle5'
start1 = time.clock()
for i in range(iters):
    s = 'abcdefghij'
    r=s
    #while r == s:
    r = partial_shuffle5(s, 20)
        
    #print 'r: ', r, NGram.compare(r, s)
end1 = time.clock() - start1
print end1
results['partial_shuffle5'] = end1


print ''
for k, v in sorted(results.iteritems(), key=lambda (k, v): (v, k)):
    print("{:<20} => {}".format(k, v))

In response to question