lấy mẫu ngẫu nhiên của chuỗi con không chồng chéo có độ dài k

Question

Cho một xâu có độ dài n, thế nào tôi sẽ (giả) lấy mẫu ngẫu nhiên m chuỗi con của kích thước k như vậy mà không ai trong số các chuỗi con được lấy mẫu chồng chéo? Hầu hết các kinh nghiệm kịch bản của tôi là trong Perl, nhưng một giải pháp dễ chạy trong bất kỳ ngôn ngữ chung nào cũng đủ.

Answer 1

Nếu có một ký tự không thể xảy ra trong đầu vào, ví dụ: X, chỉ:

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

Đây là phương pháp đệ quy trong Python. Tại mỗi bước, chọn ngẫu nhiên trong số các phân vùng còn lại của chuỗi, sau đó chọn ngẫu nhiên chuỗi con có độ dài k từ phân vùng đã chọn. Thay thế phân vùng này bằng cách chia phân vùng trên chuỗi con được chọn. Lọc ra các phân vùng có độ dài nhỏ hơn k và lặp lại. Danh sách các giá trị trả về khi có m, hoặc không có phân vùng nào có chiều dài lớn hơn hoặc bằng 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)