Counting all permutations of a substring

[Andrew Gwozdziewycz]

On Apr 5, 2006, at 5:07 PM, Chris Lasher wrote:

> Hi all,
> How can one count all the permutations of a substring in a string? For
> a more concrete example, let's say
> targetstr = 'AAA'
> and
> probestr = 'AA'
>
> I want to consider how many times one can count probestr ('AA') in
> targetstr ('AAA'). The value in this example is, obviously, 2: you can
> match the first and second A's as 'AA' and also the second and third
> A's as 'AA'. Compiling a regular expression of the probestr and  
> doing a
> findall(targetstr) will not work because the RE stops on the first
> combination of 'AA' that it finds (the first and second A's of the
> targetstr). The regular expression re.compile(r'A{2,}'} will not work,
> either; it simply consumes all three A's as one match. The string
> method count('AA') acts similarly to the findall of the 'AA' RE,
> returning 1, as it only matches the first and second A's.
>
> Any suggestions on how to get at that 2nd pair of A's and count it?
> Humbly, I'm a bit stumped. Any help would be appreciated.


I don't think you're describing a permutation. A permutation of a
string 'ABC' would be 'CBA', or 'BCA'.

You're describing something like the number of proper substrings of a
given value, and the easiest way to do that is to just check to see if
the probestring starts a string at the current index of the string...

def count_proper_substrings_equal_to(target, probe):
       i = 0
       count = 0
       while i < len(target):
            if target[i:].startswith(probe):
                    count = count + 1
            i = i + 1
        return i

And of course there's a more 'pythonic' way to do it, but this would
be a generalized algorithm suitable for most languages.

---
Andrew Gwozdziewycz
apgwoz at gmail.com
http://ihadagreatview.org
http://and.rovir.us