List Σⁿ, the strings of length n over an alphabet.
What to build
A program that prints every string of length n over the given alphabet, then how many there are.
Requirements
- Print the strings one per line, in the order product() gives them for the alphabet's order.
- Print ε for the empty string, and finish with
count K.
Input
Line 1: the symbols of the alphabet, separated by spaces. Line 2: n.
Output
The strings, then count K.
Constraints
At most 4 symbols, and 0 ≤ n ≤ 4.
Example
Input:
a b
2
Output:
aa
ab
ba
bb
count 4
Why it works
There are |Σ|ⁿ strings of length n, because each position independently takes any symbol.
Examples
Example 1 · Input
a b 2
Expected output
aa ab ba bb count 4
Example 2 · Input
0 1 0
Expected output
ε count 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
itertools.product(symbols, repeat=n) gives every tuple of n symbols, in order.
Hint 2
For n = 0 the only string is ε.
Solution
Show one correct solution (try it yourself first)
from itertools import product
symbols = input().split()
n = int(input())
count = 0
for letters in product(symbols, repeat=n):
print("".join(letters) or "ε")
count += 1
print("count", count)