Hadron DaVinci

Count Number of Strings of Length N

24 Oct 2020 - Hadron DaVinci

Problem

Count the number of strings of length n=3,
that can be made using a, b, and c with at most one b and two c’s allowed.

Examples

When n = 3, here are some possible strings:

• aaa, aab, aba, baa, aac, acc

Truths

1. We must consider permutations of letters since order matters, aab != aba
2. The maximum number of a’s possible is n
3. The maximum number of b’s possible is 1
4. The maximum number of c’s possible is 2
5. The independent variables are n, b, and c
   • Note, a is not an independent variable since it can be described by a = n - (b + c)
   • Therefore, in our solutions, we can omit a from the input

Methods

Method 1

Use itertools to find the permutations.
Imagine having a bag of all possible letters and selecting n of them.
TC: exponential
SC: O(n)

Steps:

• Make list of all possible letters

  n = 3
  possible_letters = n*['a'] + 1*['b'] + 2*['c']
  

• Use itertools to find permutations

  from itertools import permutations
  possibilities = permutations(possible_letters, n)
  

• Get rid of duplicates

  unique_possibilities = set(possibilities)
  

• Get count

  count = len(unique_possibilities)
  

Method 2

Use counting rules to make a formula by summing the number_of_ways of all possibilities.
Given: number_of_ways = (number_of_letters!) / π (repeated_letter !)
TC: O(1)
SC: O(1)

Steps:

• Create formula by summing the numbers of ways for each possible case

      Factorial Tip:
        **remember the last term keeps the factorial: example: (n-2)! = (n-2)(n-3)(n-4)(n-5)!
        **expand it out as much as is needed
        source: https://www.coolmath.com/algebra/20-combinatorics/04-permutations-repeats-reruns-02

    Case1: All the characters are A's
        example: (a, a, a)
        N! is because 'a' is present N times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / N! = 1
    
    Case2: One character is B
        example: (a, a, b)
        (N-1)! is because 'a' is present (N-1) times
        1! is because 'b' is present 1 times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / ((N-1)! 1!) = (N (N-1)!) / (N-1)! = N
    
    Case3: One character is C
        example: (a, a, c)
        (N-1)! is because 'a' is present (N-1) times
        1! is because 'c' is present 1 times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / ((N-1)! 1!) = (N (N-1)!) / (N-1)! = N
    
    Case4: One character is B and One character is C
        examples: (a, b, c), (a, a, a, a, b, c)
        (N-2)! is because 'a' is present (N-2) times
        1! is because 'b' is present 1 times
        1! is because 'c' is present 1 times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / (N-2)! = (N (N-1)(N-2)!) / (N-2)! = N (N-1)
    
    Case5: Two characters are C
        examples: (a, c, c), (a, a, a, a, c, c)
        (N-2)! is because 'a' is present (N-2) times
            2! is because 'c' is present 2 times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / ((N-2)! (2!)) = (N (N-1)(N-2)!) / ((N-2)! 2!) = N (N-1)/2
    
    Case 6: One character is a B and Two characters are C
        examples: (b, c, c), (a, a, a, b, c, c)
        (N-3)! is because 'a' repeats (N-3) times
        1! is because 'b' is present 1 times
        2! is because 'c' is present 2 times
        use number of ways = (number_of_letters!) / π (repeated_letter !)  = N! / ((N-3)! 1! 2!) = (N (N-1)(N-2)(N-3)!) / ((N-3)! 1! 2!)

		           = N (N-1)(N-2) / 2		

The sum of all possible cases is:

     count = case1 + case2 + case3 + case4 + case5 + case6
             = 1 + N + N + N(N-1) + N(N-1)/2 + N(N-1)(N-2)/2
             = 1+2*N+N(N-1) [1+1/2+(N-2)/2]
             = 1+2*N+N(N-1)(N+1)/2

Method 3

If Method 1 and Method 2 had a baby, this would be it. This automates method 2 by
determining the unique cases then using the counting rules to determine
the total number of ways.

Let m = sum(b + c)
TC: m!
SC: O(M)

• To clarify here, the time and spatial complexity is more related to the sum of (b and c)
• In other words, n, the size of the string could be a trillion but only the sum of (b and c) actually matter

Steps:

• Determine the unique cases.

For method 2, you may have asked yourself:

• How did we come up with 6 cases?
  
• Do we really have to come up with those 6 cases by trial and error?
  

The answer is that trial and error is not necessary.
Imagine we have a bag with the maximum number of b and c characters inside.
To get the unique cases, we can pull out combinations between 0 to (b + c) times via a for loop.
This produces the following:

(b,c,c), 0 -> ()            # (case 1) All the characters are A's
(b,c,c), 1 -> (b), (c)      # (case 2) One character is B; (case 3) One character is C
(b,c,c), 2 -> (b,c), (c,c)  # (case 4) One character is B and One character is C; (case 5) Two characters are C
(b,c,c), 3 -> (b,c,c)       # (case 6) One character is B and Two characters are C

• For each unique case calculate the number of ways.
  

  • Determine the count of a, b, c characters
  • use counting rule to calculate number of ways for that particular case:
    number_of_ways_in_case_i = (n!) / π (count_of_character !)
  • Sum to get total number of ways with a running total

Method 4

Use Recursion. This uses a count-down approach which starts with n = 3
and counts down to n = 0.

TC: exponential
SC: O(1)

Steps:

• Define function

  way_count(n, b, c)
  

  • where n represents the number of characters in the string to be selected
    • as we select characters, n will decrement to zero.
      Note, n==0 would indicate that we can select no more characters.
  • where b, c represent the number of characters which can be selected of b and c

• Define base cases

  • if any character count is negative, then return 0
    since a negative quantity is not a valid possibility

  • if n == 0, then return 1
    since the only valid possibility is an empty string which is: ""

  • if b and c are zero, then return 1
    since the only valid possibility is: (a, a, a)

• Define count from the non-base cases

            count = way_count(n is decreased, b is same, c is same)       # when a is selected
            
            count += way_count(n is decreased, b is decreased, c is same) # when b is selected
            
            count += way_count(n is decreased, b is same, c is decreased) # when c is selected

Files

method1.py

method2.py

method3.py

method4.py