Получить N случайных непересекающихся подстрок длины K - PullRequest
Новая
       34

Получить N случайных непересекающихся подстрок длины K

2 голосов
/ 10 ноября 2019

Допустим, у нас есть строка R длиной 20000 (или другой произвольной длины). Я хочу получить 8 случайных неперекрывающихся подстрок длины k из строки R.

Я попытался разбить строку R на 8 разделов равной длины и получить [: k] каждого раздела, но этого недостаточно. быть использованным в моем приложении, и условие метода для работы не может быть легко выполнено.

Интересно, смогу ли я использовать встроенный случайный пакет для выполнения работы, но я не могу думатьспособа сделать это, как я могу это сделать?

Ответы [ 3 ]

0 голосов
/ 10 ноября 2019

Вы можете использовать цикл while для обеспечения уникальности: 

import random
result, n, k = set(), 20000, 10
for _ in range(8):
  a = random.randint(0, n-k) 
  while any(a >= i and a <= i+k for i in result):
     a = random.randint(0, n-k) 
  result.add(a)

final_result = [(i, i+k) for i in result]

Вывод: 

[(13216, 13226), (10400, 10410), (4290, 4300), (14499, 14509), (7985, 7995), (9363, 9373), (1181, 1191), (14526, 14536)]
0 голосов
/ 10 ноября 2019

Ну, нет необходимости делать петли. Если мы хотим разбить строку s на m подстроки длиной k каждая, эта проблема эквивалентна выборке m+1 интервалов между подстроками с общей длиной, равной len (s) -m * k.

Существует довольно хорошее дискретное распределение со свойством, что выборочные значения суммируются до фиксированного количества - Многочленное распределение . Расщепление строки по интервалам тогда довольно тривиально, возможно, можно оптимизировать

Код, Python 3.7.5 Anaconda x64, Win10. 

import numpy as np
from typing import List

LoS = List[str]

def string2substrings(s: str, m:int, k: int) -> LoS:
    """
    split string s into m substrings with length k each
    """

    l = len(s)

    if l == 0:
        raise RuntimeError(f"Empty input string")

    if k <= 0:
        raise RuntimeError(f"Bad substrung length {k}")

    if m <= 0:
        raise RuntimeError(f"Bad substrung count {m}")

    if l < m*k:
        raise RuntimeError(f"cannot split string {s} into {m} pieces with length {k} - source length {l} is too short")

    if l == m*k: # trivial case of all zero intervals
        rv = [s[t*k:t*k+k] for t in range(0, m)]
        return rv

    # we will sample m+1 intervals which sum to l-m*k
    # for that we will use multinomial distribution which
    # sums to fixed value by itself

    p = np.full(m+1, 1.0/np.float64(m+1), dtype=np.float64) # equal m+1 probabilities

    intervals = np.random.multinomial(n = l - m*k, pvals = p)
    print((intervals, np.sum(intervals)))

    rv = list()
    end = 0
    for count, i in enumerate(intervals):
        if count == m:
            break
        start = end+i
        end   = start + k
        rv.append(s[start:end])

    return rv

print(string2substrings("qwertyuiopas", 3, 3))
0 голосов
/ 10 ноября 2019

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

Причина, по которой я упоминаю размер k, заключается в том, что если он достаточно большой, то можно будет выбратьподстроки, которые не позволяют найти 8 непересекающихся. Но это необходимо учитывать, только если k достаточно велико по отношению к длине исходной строки.

...