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
risposta
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/;
}
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)
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)? –