Theory: Every string of a given length

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)

Lesson: Alphabets, strings and languages →