Backtracking all the words in the English alphabet that have 5 letters, where no 2 consecutive letters can be consonants or vowels

Question

I have the following problem in my algorithms textbook:

Write a computer program that generates and counts how many words of 5 letters of the English alphabet can be formed, with the condition that no 2 consecutive letters can be consonants or vowels.

From the statement, I understand that the output should have this form cvcvc or vcvcv, where c means consonant and v means vowel.

The way I approached this problem was to write a function that generates all the words with 5 letters given a permutation of the sets (since there are 2 available sets, consonants and vowels). There are only 2 permutations of the sets available: cvcvc or vcvcv. And I call the function generate_words for every permutation of the sets.

My question is: Is it a good practice to hardcode the permutation of the sets? Would have been a better solution to write a function that generates this information?

# We use this variable just o track the number of generated solutions.
counter = 1

def _print_solution(set_master, solution):
    result = [set_master[set_index][element]
        for set_index, element in enumerate(solution)]

    global counter
    # ljust(6) because, in our case, the maximum number of words is 21 66 00
    # which has 6 digits.
    print str(counter).ljust(6), ', '.join(map(str, result))
    counter += 1

def _generate_words(set_master, solution, set_counter):
    if set_counter == len(set_master):
        _print_solution(set_master, solution)
        return

    for i in range(0, len(set_master[set_counter])):
        solution.append(i)
        _generate_words(set_master, solution, set_counter + 1)
        solution.pop()

def generate_words(set_master):
    solution = []
    _generate_words(set_master, solution, 0)

if __name__ == "__main__":

    vowels = ['a', 'e', 'i', 'o', 'u']
    consonants = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p',
        'q', 'r', 's', 't', 'v', 'x', 'z']

    generate_words([vowels, consonants, vowels, consonants, vowels])
    generate_words([consonants, vowels, consonants, vowels, consonants])

Answer 1

1. In Python, strings support the sequence interface, so you can write the vowels and consonants as strings, which are easier to read than lists:

   vowels = 'aeiou'
   consonants = 'bcdfghjklmnpqrstvxz'
   

2. Writing out the consonants explicitly like this is risky: it would be easy to omit one and not notice. (What happened to w and y?) It would be more reliable to construct the consonants by subtracting the vowels from all lowercase letters:

   from string import ascii_lowercase
   consonants = sorted(set(ascii_lowercase) - set(vowels))
   

3. Generating the words is very simple if you use the built-in itertools.chain and itertools.product:

   from itertools import chain, product
   v, c = vowels, consonants
   words = chain(product(v, c, v, c, v), product(c, v, c, v, c))
   

4. Counting the words is even simpler. If there are \$v\$ vowels and \$c\$ consonants, then there are \$v^3c^2\$ words of the form VCVCV and \$v^2c^3\$ words of the form CVCVC, for \$v^2c^2(v+c)\$ words altogether:

   >>> v, c = len(vowels), len(consonants)
   >>> v ** 2 * c ** 2 * (v + c)
   286650
   

   which is the same as the number of elements emitted by the generator:

   >>> sum(1 for _ in words)
   286650
   

5. You asked, "Is it a good practice to hardcode the permutation of the sets?" Well, good practice is not some magic book of lore, it's the set of techniques that best meet your requirements. In this case, the goal is to answer your algorithms question, so the requirements include things like correct, clear (and so easily marked) and short.

   It's never wrong to think about generalizing your code, but you have to balance the cost of the generalization (in terms of more complex code) against the benefits. If you suspect that in the near future you are going to have to generate and count sets of words under other rules about adjacency of vowels and consonants, then generalizing the code now would be a good idea. But if not, there's no point: you can always generalize it later if you need to.

Answer 2

A quick solution involving itertools

Python has a wonderful module called itertools.

import itertools

v = ['a', 'e', 'i', 'o', 'u']
c = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'x', 'z']

comb = list(itertools.product(v, c, v, c, v)) + list(itertools.product(c, v, c, v, c))
print(comb)
print(len(comb))

A quick solution involving math

If all you want if the number of combinations, you don't actually need to generate them. The number of strings with the cvcvc format corresponds to picking 3 independant consonants and 2 independant vowels which corresponds to len(consonants) * len(vowels) * len(consonants) * len(vowels) * len(consonants). The same idea applies to the vcvcv format. This leads to following code :

v = ['a', 'e', 'i', 'o', 'u']
c = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'x', 'z']

nb_v = len(v)
nb_c = len(c)
print(nb_v ** 3 * nb_c ** 2 + nb_v ** 2 * nb_c ** 3)

As for the actual review, it seems like Gareth already said everything I had to say except for a few details :

• you can rewrite range(0, len(set_master[set_counter])) in a more concise way : range(len(set_master[set_counter])). Also, I usually find the range(len(xxx)) pattern dubious.

• you should try to avoid global variables. In your case, you probably don't need it.