campionamento casuale di sottostringhe non sovrapposti di lunghezza k

Data una stringa di lunghezza n , come avrei (pseudo) campionare casualmente m sottostringhe di formato k tale che nessuna delle sottostringhe campione sovrappongono? La maggior parte della mia esperienza di scripting è in Perl, ma una soluzione facile da eseguire in qualsiasi linguaggio comune sarà sufficiente.campionamento casuale di sottostringhe non sovrapposti di lunghezza k

fonte

2013-05-20 Daniel Standage

Dividere la stringa in campioni della lunghezza desiderata; possibilmente popolando array, e poi 'my $ rnd = $ array [int rand @array]' –

Penso che ci avvicinerei considerando che ci sono caratteri 'nm * k' che _will not_ be used, e' m + 1 'lacune in cui possono andare. Scegli le lunghezze di questi spazi 'm + 1' in modo che sommano esattamente a' n-m * k'. (In questo modo, non è necessario considerare le sovrapposizioni.) – cjm

Suppongo che le sottostringhe debbano essere contigue (altrimenti sarebbe molto facile fare con un iteratore)? –

Se è presente un carattere che non può verificarsi nell'input, ad es. X, solo:

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/; 
}

fonte

2013-05-20 23:48:07 ysth

Risposta molto chiara e semplice. Una domanda però, qual è lo scopo del '\ Q' nell'espressione regolare? –

Sembra che abbia anche una distribuzione abbastanza imparziale: http://i.imgur.com/EPLexRr.png. –

se si imposta $ segno su qualcosa come '|'. sì, questo dovrebbe essere imparziale (ma si rifiuta di provare anche se si sta andando a prendere molto più della metà della stringa) – ysth

Questo è un approccio ricorsivo in Python. Ad ogni passo, selezionare casualmente tra le restanti partizioni della stringa, quindi selezionare casualmente una sottostringa di lunghezza k dalla partizione scelta. Sostituisci questa partizione con la divisione della partizione sulla sottostringa selezionata. Filtra le partizioni di lunghezza inferiore a k e ripeti. L'elenco delle sottostringhe ritorna quando ce ne sono m o non ci sono partizioni con lunghezza maggiore o uguale a 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)

fonte

2013-05-20 19:16:30

campionamento casuale di sottostringhe non sovrapposti di lunghezza k

risposta

Problemi correlati