- Code: Select all
`def has_pattern(pat, lst):`

pat_i = 0

for el in lst:

if el == pat[pat_i]:

pat_i += 1

if pat_i == len(pat):

return True

continue

return False

What I want is given a pattern and a sequence, the probability of a permutation of the sequence has the pattern. This function does the job

- Code: Select all
`def prob(pat, lst):`

all_perm = list(itertools.permutations(lst, len(lst)))

return Fraction(sum((has_pattern(pat, p) for p in all_perm)), len(all_perm))

but it's slow and I want a general formula so I can get, for example, prob(‘abc’, ‘aabbcc’) = 47/90, quickly.

What I can see is

1. Letters in the sequence but not in the pattern doesn't matter. prob('ab', 'abc') = prob('ab', 'ab')

2. The order of pattern doesn't matter. prob('ab', 'ab') = prob('ba', 'ab')

3, then?

Thanks.