Counting all permutations of a substring

[Chris Lasher]

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(targets tr) 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.

Many thanks in advance,
Chris

[mensanator]

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(targets tr) 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.

def ss(a,b): matches = 0
lc = len(a)-len(b)+1
for i in xrange(lc):
if a[i:i+lb]==b:
print a
print ' '*i+b
print
matches += 1
return matches
ss('AAABCDEAAAA ABSAABAWA','AA' )

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

7

Many thanks in advance,
Chris

[mensanator]

me********@aol. com wrote:

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(targets tr) 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.

def ss(a,b): matches = 0
lc = len(a)-len(b)+1
for i in xrange(lc):
if a[i:i+lb]==b:

Oops, should be
if a[i:i+len(b)]==b:
print a
print ' '*i+b
print
matches += 1
return matches
ss('AAABCDEAAAA ABSAABAWA','AA' )

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

AAABCDEAAAAABSA ABAWA
AA

7

Many thanks in advance,
Chris

[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(targets tr) 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_su bstrings_equal_ to(target, probe):
i = 0
count = 0
while i < len(target):
if target[i:].startswith(pro be):
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
ap****@gmail.co m
http://ihadagreatview.org
http://and.rovir.us

[Azolex]

[counting all (possibly overlapping) occurences of a substring in a string]

def count_subs(s,su bs,pos=0) :
pos = 1+s.find(subs,p os)
return pos and 1+count_subs(s, subs,pos)

or equivalently

def count_subs(s,su bs)
pos,cnt = 0,0
while True :
pos = 1+s.find(subs,p os)
if not pos :
return cnt
cnt += 1

or even (using the helper functions of my last post in the "small
challenge" thread)

def count_subs(s,su bs) :
cnt = 0
for pos1 in echoback(1+s.fi nd(subs,pos) for pos in itially(0)) :
if not pos1 :
return cnt
cnt += 1
(I've minimally tested only the first version)

[Chris Lasher]

Great suggestions, guys! Thanks so much!

And yes, I stand corrected. A better suited subject title would have
been "Counting all overlapping substrings".

Thanks again,
Chris

[Azolex]

I wrote:

[counting all (possibly overlapping) occurences of a substring in a string]

def count_subs(s,su bs,pos=0) :
pos = 1+s.find(subs,p os)
return pos and 1+count_subs(s, subs,pos) .

now to push lisp-style to the extreme, a recursive one-liner solution
with presumably better stack behavior (assuming proper tail-recursion
elimination, which I doubt is the case in Python).

Python 2.5a1 (r25a1:43589, Apr 5 2006, 10:36:43) [MSC v.1310 32 bit
(Intel)] on win32
....

cnt_ss = lambda s,ss,p=-1,n=-1 : n if n>p else cnt_ss(s,ss,s.f ind(ss,p+1),n+1 )
cnt_ss("AABBAAA BABAAA","AA") 5 cnt_ss("foolish ","bar") 0 cnt_ss("banana split","ana")

2

note though that the first solution beats this one on token count: 37 vs 42

[Michele Simionato]

Azolex wrote:

Python 2.5a1 (r25a1:43589, Apr 5 2006, 10:36:43) [MSC v.1310 32 bit
(Intel)] on win32
...

cnt_ss = lambda s,ss,p=-1,n=-1 : n if n>p else cnt_ss(s,ss,s.f ind(ss,p+1),n+1 )

<sarcastic-mode>
Ah, the pleasure of having a ternary operator in the language!
</sarcastic-mode>

Michele Simionato