How to count # of patterns in a sequence

Probability theory and statistics

How to count # of patterns in a sequence

Postby rainie » Fri Jan 03, 2020 4:28 pm

Definition: Sequence 'ab' has patterns 'a', 'b', 'ab' but not 'ba', or by codes
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
  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?
Posts: 1
Joined: Fri Jan 03, 2020 4:24 pm
Reputation: 0

Return to Probabilities and Statistics

Who is online

Users browsing this forum: No registered users and 1 guest