Generate all lists of size n, such that each element is between 0 and m (inclusive)

Question

Generate all lists of size n, such that each element is between 0 and m (inclusive).

There are (m+1)^n such lists.

Answer 1

There are two easy ways of writing the general case. One is described in the existing answer from @didierc. The alternative is recursion.

For example, think about a method that takes a String as an argument:

if(input string is long enough)
  print or store it
else
  iterate over digit range
    recursive call with the digit appended to the string

Answer 2

This is just like enumerating all the numbers in base (m+1) of n digits.

start with a list of n zeros
do the following loop
    yeld the list as a new answer
    increment the first element, counting in base (m+1), and propagate the carry recursively on its next element
    if there is a carry left, exit the loop

Update: just for fun, what would be the solution, if we add the restriction that all digits must remain different (like a lottery number, as it was initially stated - and of course we suppose that m >= n) ?

We proceed by enumerating all the numbers with the restriction stated above, and also that any element must be greater than its successor in the list (ie the digit of rank k < n is larger than the digit of rank k+1). This is implemented by simply checking when computing the carry that the current digit will not become equal to its predecessor, and if so propagate the carry further.

Then, for each list yelded by enumeration, compute all the possible permutations. There are known algorithms to perform that computation, see for instance the Johnson-Trotter algorithm, but one can build a simpler recursive algorithm:

 function select l r:
   if the list r is empty, yeld l
   else
     for each element x of the list r
        let l' be the list of x and l
        and r' the remaining elements of r
        call select l' r'