Как сделать случайное, но частичное перемешивание в Python?

Question

Вместо полного shuffle я ищу частичную shuffle функцию в Python.

Пример:"строка" должна вызыватьв «stnrig», но не «nrsgit»

Было бы лучше, если бы я мог определить определенный «процент» символов, которые необходимо переставить.

Цель - проверить алгоритмы сравнения строк.Я хочу определить «процент случайного перемешивания», после которого (мой) алгоритм пометит две (перемешанные) строки как совершенно разные.

Обновление:

Здесьмой кодУлучшения приветствуются!

import random

percent_to_shuffle = int(raw_input("Give the percent value to shuffle : "))
to_shuffle = list(raw_input("Give the string to be shuffled : "))

num_of_chars_to_shuffle = int((len(to_shuffle)*percent_to_shuffle)/100)

for i in range(0,num_of_chars_to_shuffle):
    x=random.randint(0,(len(to_shuffle)-1))
    y=random.randint(0,(len(to_shuffle)-1))
    z=to_shuffle[x]
    to_shuffle[x]=to_shuffle[y]
    to_shuffle[y]=z

print ''.join(to_shuffle)

Answer 1

Это проблема проще, чем кажется.И у языка есть нужные инструменты, чтобы не оставаться между вами и идеей, как обычно:

import random

def pashuffle(string, perc=10):
    data = list(string)
    for index, letter in enumerate(data):
        if random.randrange(0, 100) < perc/2:
            new_index = random.randrange(0, len(data))
            data[index], data[new_index] = data[new_index], data[index]
    return "".join(data)

Answer 2

Ваша проблема хитрая, потому что есть некоторые крайние случаи, о которых нужно подумать:

• Строки с повторяющимися символами (т.е. как бы вы перетасовали "aaaab"?)
• Как сделатьВы измеряете цепочечные перестановки символов или реорганизуете блоки?

В любом случае метрика, заданная для перемешивания строк до определенного процента, вероятно, будет той же, которую вы используете в своем алгоритме, чтобы увидеть, насколько близкоони есть.

Мой код для перемешивания n символов:

import random
def shuffle_n(s, n):
  idx = range(len(s))
  random.shuffle(idx)
  idx = idx[:n]
  mapping = dict((idx[i], idx[i-1]) for i in range(n))
  return ''.join(s[mapping.get(x,x)] for x in range(len(s)))

В основном выбирает n позиций для случайного обмена, а затем обменивает каждую из них на следующую в списке... Таким образом, это гарантирует, что обратные перестановки не генерируются, и точно n символы меняются местами (если есть повторяющиеся символы, неудача).

Объясненный прогон с 'строкой', 3 в качестве ввода:

idx is [0, 1, 2, 3, 4, 5]
we shuffle it, now it is [5, 3, 1, 4, 0, 2]
we take just the first 3 elements, now it is [5, 3, 1]
those are the characters that we are going to swap
s t r i n g
  ^   ^   ^
t (1) will be i (3)
i (3) will be g (5)
g (5) will be t (1)
the rest will remain unchanged
so we get 'sirgnt'

Недостаток этого метода в том, что он не генерирует все возможные варианты, например, он не может сделать 'gnrits' из 'string'.Это можно исправить, перетасовав разделы индексов следующим образом:

import random

def randparts(l):
    n = len(l)
    s = random.randint(0, n-1) + 1
    if s >= 2 and n - s >= 2: # the split makes two valid parts
        yield l[:s]
        for p in randparts(l[s:]):
            yield p
    else: # the split would make a single cycle
        yield l

def shuffle_n(s, n):
    idx = range(len(s))
    random.shuffle(idx)
    mapping = dict((x[i], x[i-1])
        for i in range(len(x))
        for x in randparts(idx[:n]))
    return ''.join(s[mapping.get(x,x)] for x in range(len(s)))

Answer 3

import random

def partial_shuffle(a, part=0.5):
    # which characters are to be shuffled:
    idx_todo = random.sample(xrange(len(a)), int(len(a) * part))

    # what are the new positions of these to-be-shuffled characters:
    idx_target = idx_todo[:]
    random.shuffle(idx_target)

    # map all "normal" character positions {0:0, 1:1, 2:2, ...}
    mapper = dict((i, i) for i in xrange(len(a)))

    # update with all shuffles in the string: {old_pos:new_pos, old_pos:new_pos, ...}
    mapper.update(zip(idx_todo, idx_target))

    # use mapper to modify the string:
    return ''.join(a[mapper[i]] for i in xrange(len(a)))

for i in xrange(5):
    print partial_shuffle('abcdefghijklmnopqrstuvwxyz', 0.2)

отпечатки

abcdefghljkvmnopqrstuxwiyz
ajcdefghitklmnopqrsbuvwxyz
abcdefhwijklmnopqrsguvtxyz
aecdubghijklmnopqrstwvfxyz
abjdefgcitklmnopqrshuvwxyz

Answer 4

может быть так:

>>> s = 'string'
>>> shufflethis = list(s[2:])
>>> random.shuffle(shufflethis)
>>> s[:2]+''.join(shufflethis)
'stingr'

Исходя из идеи Фортрана, я добавляю это в коллекцию. Это довольно быстро:

def partial_shuffle(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

Answer 5

Зло и использование устаревшего API:

import random
# adjust constant to taste
# 0 -> no effect, 0.5 -> completely shuffled, 1.0 -> reversed
# Of course this assumes your input is already sorted ;)
''.join(sorted(
    'abcdefghijklmnopqrstuvwxyz',
    cmp = lambda a, b: cmp(a, b) * (-1 if random.random() < 0.2 else 1)
))