# Find all words of length $k$ in lexicographic order

Given the alphabet $$\Sigma = \{1,2,\dots, n \}$$ and a parameter $$k$$ how can we find all words of length $$k$$ over $$\Sigma$$ in lexicographic order?

I thought of doing this recursively, but although the task is basic it seems pretty hard to come up with a general algorithm, even when using the last word as a parameter using recursion.

Will be glad for any help

• Suppose that $\Sigma = \{0,1,\ldots,9\}$, and consider the decimal representation of the first $10^k$ natural numbers (starting with zero). Can you solve the problem in this case? – Yuval Filmus Jun 22 '20 at 11:37
• Oh well thanks, I guess it is the $n^k$ first natural numbers starting from zero presented in base $n$ padded with zeros to the left with $\Sigma = \{0,1,\dots,n-1\}$. Somehow thought this is much more complicated. – Oren Jun 22 '20 at 12:07

You can do it either inductively or recursively.

Inductively, you just write out the numbers from $$0$$ to $$n^{k-1}$$ in base $$n$$, adding $$1$$ to all digits.

Alternatively, you can simulate a counter in base $$n$$ – that would be faster.

Recursively, you can proceed as follows:

• Generate all solutions for $$k-1$$, and output them with prefix 1.
• Generate all solutions for $$k-1$$, and output them with prefix 2.
• ...
• Generate all solutions for $$k-1$$, and output them with prefix $$n$$.

Alternatively:

– Generate all solutions for $$k-1$$.

• For each solution $$s$$, output $$s1, s2, \ldots, sn$$.