Сгенерируйте N "случайных" строк длиной K, используя таблицу вероятностей

Как создать N "случайные" строки длины K, используя таблицу вероятностей? K будет некоторое четное число.

prob_table = {'aa': 0.2, 'ab': 0.3, 'ac': 0.5}
Предположим, что вероятность 'acacab' выше, чем вероятность 'aaaaaa'. Это подзадача более крупной задачи, которую я использую для генерации синтетических последовательностей на основе таблицы вероятностей. Я не знаю, как использовать таблицу вероятностей для генерации "случайных" строк?

Что у меня есть до сих пор: 

def seq_prob(fprob_table,K= 6, N= 10):
    #fprob_table is the probability dictionary that you input
    #K is the length of the sequence
    #N is the amount of sequences
    seq_list = []
    #possibly using itertools or random to generate the semi-"random" strings based on the probabilities 
    return seq_list
4 3
python string random itertools probability

4 ответа:

Есть несколько хороших подходов к принятию взвешенных случайных решений, описанных в конце документации для встроенного модуля random :

Общая задача состоит в том, чтобы сделать случайный.choice () с взвешенными вероятностями.

Если веса являются малыми целыми отношениями, простой метод заключается в построении выборочной совокупности с повторами: 

>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'

Более общий подход состоит в том, чтобы расположить веса в кумулятивном распределении с модуле itertools.accumulate (), а затем найдите случайное значение с помощью bisect.bisect (): 

>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]
'Blue'
Чтобы адаптировать этот последний подход к вашей конкретной проблеме, я бы сделал: 
import random
import itertools
import bisect

def seq_prob(fprob_table, K=6, N=10):
    choices, weights = fprob_table.items()
    cumdist = list(itertools.accumulate(weights))

    results = []
    for _ in range(N):
        s = ""
        while len(s) < K:
            x = random.random() * cumdist[-1]
            s += choices[bisect.bisect(cumdist, x)]
        results.append(s)

    return results
Это предполагает, что ключевые строки в вашей таблице вероятностей имеют одинаковую длину, если они имеют несколько разных длин, этот код иногда (возможно, большую часть времени!) дайте ответы, которые длиннее символов K. Я полагаю, что он также предполагает, что K является точным кратным длины ключа, хотя на самом деле это будет работать, если это не так (это просто даст строки результатов, которые все длиннее символов K, так как нет никакого способа получить K точно).
3

Можно использовать random.random: 

from random import random
def seq_prob(fprob_table, K=6, N=10):
    #fprob_table is the probability dictionary that you input
    #K is the length of the sequence
    #N is the amount of sequences
    seq_list = []
    s = ""
    while len(seq_list) < N:
        for k, v in fprob_table.items():
            if len(s) == K:
                seq_list.append(s)
                s = ""
                break
            rn = random()
            if rn <=  v:
                s += k
    return seq_list
Это, без сомнения, может быть улучшено, но random.random полезно при работе с вероятностью.
2

Я уверен, что есть более чистый/лучший способ, но вот один простой способ сделать это.

Здесь мы заполняем pick_list значениями 100 отдельных пар символов, число значений которых определяется вероятностью. В этом случае существуют 20 'aa', 30 'ab' и 50 'ac' записей внутри pick_list. Затем random.choice(pick_list) равномерно вытягивает случайную запись из списка.

import random

prob_table = {'aa': 0.2, 'ab': 0.3, 'ac': 0.5}


def seq_prob(fprob_table, K=6, N=10):
    #fprob_table is the probability dictionary that you input

    # fill list with number of items based on the probabilities
    pick_list = []
    for key, prob in fprob_table.items():
        pick_list.extend([key] * int((prob * 100)))    

    #K is the length of the sequence
    #N is the amount of sequences
    seq_list = []
    for i in range(N):
        sub_seq = "".join(random.choice(pick_list) for _ in range(int(K/2)))
        seq_list.append(sub_seq)
    return seq_list

С результатами: 

 seq_prob(prob_table)
['ababac',
 'aaacab',
 'aaaaac',
 'acacac',
 'abacac',
 'acaaac',
 'abaaab',
 'abaaab',
 'aaabaa',
 'aaabaa']
1

Если ваши таблицы или последовательности большие, использование numpy может быть полезно, Так как это, вероятно, будет значительно быстрее. Кроме того, numpy построен для такого рода задач, и подход прост для понимания и всего 3 или 4 строки.

Идея состояла бы в том, чтобы преобразовать вероятности в кумулятивные вероятности, т. е. отображение (.2, .5, .3) в (.2, .7, 1.), и тогда случайные числа, генерируемые вдоль плоского распределения от 0 до 1, будут попадать в ячейки кумулятивной суммы с частотой соответствует Весам. Включает в searchsorted может использоваться, чтобы быстро найти бин случайных значений лежат в пределах. То есть, 
import numpy as np

prob_table = {'aa': 0.2, 'ab': 0.3, 'ac': 0.5}
N = 10
k = 3   # number of strings (not number of characters)

rvals = np.random.random((N, k))         # generate a bunch of random values
string_indices = np.searchsorted(np.cumsum(prob_table.values()), rvals)   # weighted indices
x = np.array(prob_table.keys())[string_indices]     # get the strings associated with the indices
y = ["".join(x[i,:]) for i in range(x.shape[0])]    # convert this to a list of strings

# y = ['acabab', 'acacab', 'acabac', 'aaacaa', 'acabac', 'acacab', 'acabaa', 'aaabab', 'abacac', 'aaabab']

Здесь я использовал k как количество строк, которое вам нужно, а не K как количество символов, так как постановка задачи неоднозначна относительно строк/символов.

0