长度为k的非重叠子串的随机采样

Question

给定长度为 n 的字符串，我如何（伪）随机采样 m 大小为 k 的子字符串，使得采样的子字符串不会重叠？我的大部分脚本经验都是使用 Perl，但任何通用语言的易于运行的解决方案就足够了。

Answer 1

如果输入中存在不能出现的字符，例如：

X

，只是：

my $size = 20;
my $count = 20;
my $mark = 'X';
my $input = 'CCACGCATTTTTGTTCATTGTTCTGGCTTCTTACAAGGTTCAGTAGACTTTGTAACACAGTTGTGTCTCTCACAGATTGGCAGATGTTTGGTAAAGGATTGACTTTTCAGCCAACTCATGGGAAAGTGAAATAATGTAAAAAACAGGAAGAATACAGTTTTAGGCCTTTCAAGTGAGGCATGGCTTTCAGCTCTTGGCAAGAACAGGCAAGGAGATGCAAGTTTTAGGACTCTAAGAGGCTAGGCTTTTCAAAGTGCTTCTCTCCCCTTCACCCTCCTTCAGTTACAGCACCAAGCACCACCGAGGTGTTACCTGCAGCCTCACTCTCTACCTGGTTGTGGGATCCTGCCACTTCCTTAACCCACACTGAGTTCCTTGTGGTTCACAGGGTCACACAGAGGGCTGTAGAGATACAAAAGATATATGTGATTTTATATCACCTATCATATGAAGATATATTTATAAAATAGGAAACATATTAACCACTTATCATTTTATATATTTATGGTTTTATGTGTCAAAAATATATTGTTTCATGTATGTATTAAAGGATAAGTATGTATAAGAGGTTTTATAGATGTGTAAAATTATATATTTATACGTATCTTTACAAATTTAAGAATAAAGGAAGGAAAATTCTCAAAGAGGAATTCAGATATCAAGCAGTGCCCTTTGACCAAGAGCCTTGGTTACAACATACCTACAAAAGTGAACTATCATTGAAAGACCTATGGACACTGGATTTCTCTTTCCTTATTTAGAAGGGCAGTCTGTGTCTTGGAAAAGCATACAGTTTGTTGTATCTTGCTGGACAACAGGAGTCA';

if (2*$size*$count-$size-$count >= length($input)) {
    die "selection may not complete; choose a shorter length or fewer substrings, or provide a longer input string\n";
}

my @substrings;
while (@substrings < $count) {
    my $pos = int rand(length($input)-$size+1);
    push @substrings, substr($input, $pos, $size, $mark x $size)
        if substr($input, $pos, $size) !~ /\Q$mark/;
}

Answer 2

这是Python中的递归方法。在每一步中，从字符串的剩余分区中随机选择，然后从所选分区中随机选择长度为 k 的子字符串。将此分区替换为所选子字符串上的分区的分割。过滤掉长度小于k的分区，然后重复。当子串有 m 个，或者不存在长度大于或等于 k 的分区时，返回子串列表。

import random

def f(l, k, m, result=[]):
    if len(result) == m or len(l) == 0:
        return result
    else:
        if isinstance(l, str):
            l = [l]
        part_num = random.randint(0, len(l)-1)
        partition = l[part_num]
        start = random.randint(0, len(partition)-k)
        result.append(partition[start:start+k])
        l.remove(partition)
        l.extend([partition[:start], partition[start+k:]])
        return f([part for part in l if len(part) >= k], k, m, result)