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

Improve this question
$\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, 2020 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$
    – user10364768
    Jun 22, 2020 at 12:07

1 Answer 1

Reset to default
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$.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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