permutation with restriction

Computer Science Level 4

A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all sub-sequences of the word banana.

We are interested in counting the number of distinct sub-sequences of a fixed length of a given word. For example, the word banana has 11 different sub-sequences of length 3: {aaa, aan, ana, ann, baa, ban, bna, bnn, naa, nan, nna}.

For the word "tinnitus", how many different sub-sequences of length 3 does it have?

The answer is 34.

1 solution

Chew-Seong Cheong
Oct 16, 2014

Since it is a CS problem, I solved it a CS way using Python. No good at it, I did as follows:

Get list $a$ of all the combinations of the three-letter sequences which is 56 $(= \left( _3 ^8 \right) )$ .
Sort list $a$ of sequences for ease of checking similar elements. 3, Compile the list $b$ of sequences without repetitions.
Check the length of list $b$ (the number of elements in list $b$ ).

 from itertools import combinations
 a = []
 for c in combinations('tinnitus',3):
      a.append(''.join(c))
 a = sorted(a)
 b = []
 b.append(a[0])
 for i in range(len(a)-1):
     if a[i] != a[i+1]:
         b.append(a[i+1])
 print b, len(b)

permutation with restriction

The answer is 34.

1 solution

0 pending reports