長度爲k

的非重疊子串的隨機取樣給定長度Ñ的字符串，如何將I（僞）隨機抽樣米子大小的ķ使得沒有采樣串的重疊？我的大部分腳本編程經驗都是用Perl編寫的，但是使用任何通用語言的一個易於運行的解決方案就足夠了。長度爲k

2013-05-20 Daniel Standage

將字符串分成所需長度的樣本;可能通過填充數組，然後'我的$ rnd = $ array [int rand @array]' –

我想我會考慮有'nm * k'字符，不會被使用，'m + 1他們可以去的差距。選擇這些「m + 1」間隙的長度，使它們加起來恰好爲「n-m * k」。（這樣，你不需要考慮重疊。） – cjm

我假設子串需要是連續的（否則使用迭代器會很容易）？ –

如果有一個字符不能在輸入中出現， 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-20 23:48:07 ysth

非常清楚和簡單的答案。但有一個問題，正則表達式中'\ Q'的目的是什麼？ –

看起來它也有一個相當公正的分佈：http://i.imgur.com/EPLexRr.png。 –

以防您將$標記設置爲'|'之類的內容。是的，這應該是沒有偏見的（但是如果你要採取比這一串更多的話，甚至拒絕嘗試） – ysth

這是一個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-20 19:16:30

回答

相關問題