5

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

4

2 回答 2

2

如果输入中存在不能出现的字符，例如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/;
}
于 2013-05-20T23:48:07.993 回答
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)
于 2013-05-20T19:16:30.337 回答