Re^3: Permutation with repetitions

Replies are listed 'Best First'.
Re^4: Permutation with repetitions by umeboshi (Acolyte) on Jun 07, 2010 at 10:22 UTC
I am looking in a long string of the sort: aaaabdbbdaccdacdaaabdcd... and thus want to know the number of occurrences of any of the substrings of size 3 (as in the example). Sure, I could leave out the ones which are zero, don't need them. But I thought that I will have to loop over all possible substrings of size 3 anyway and count their occurrences. Thanks, Hadassa	[reply]
Re^5: Permutation with repetitions by ambrus (Abbot) on Jun 07, 2010 at 11:06 UTC
Oh, now your question is clearer. The easiest thing is to use a hash to track the frequencies, eg. `my $str = "aaaabdbbdaccdacdaaabdcd"; my $n = 3; my %freq; for my $p (0 .. length($str) - $n) { $freq{substr($str, $p, $n)}++; } for my $ng (sort keys %freq) { printf "%3d %s\n", $freq{$ng}, $ng; }` [download]	[reply] [d/l]
Re^5: Permutation with repetitions by bart (Canon) on Jun 07, 2010 at 11:23 UTC
What ambrus says. However, what it won't do, is give you the names of permutations with no occurrence in the string. If you need those, I think I can find a shortcut. Think of such a string as a 4 digit number, in base 4, with an a posteriori mapping of `( 0 => 'a', 1 => 'b', 2 => 'c', 3 => 'd' )` [download] or, in Perl code: `tr/0-3/a-d/` [download] so all you really need is a 4 digit base 4 counter and this mapping. If you don't want to code this by hand, you might make use of a module like the one I found using a quick Google search, Math::BaseArith.	[reply] [d/l] [select]
Re^5: Permutation with repetitions by ikegami (Patriarch) on Jun 12, 2010 at 23:37 UTC
Why loop (444(23-2)) times when you can simply loop (23-2) times. `$_ = 'aaaabdbbdaccdacdaaabdcd'; ++$counts{$1} while /(?=([abcd]{4}))/g; print("$_: $counts{$_}\n") for sort keys %counts;` [download] If you want to see the "0" results, you can loop (44*4)+(23-2) times. `$_ = 'aaaabdbbdaccdacdaaabdcd'; ++$counts{$1} while /(?=([abcd]{4}))/g; print("$_: $counts{$_}\n") for glob "{a,b,c,d}{a,b,c,d}{a,b,c,d}";` [download]	[reply] [d/l] [select]