1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jun 22 '20 at 11:37
  • $\begingroup$ 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. $\endgroup$ – Oren Jun 22 '20 at 12:07
1
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.