Create all lists of size n so that each element is between 0 and m (inclusive)
There are two easy ways to write the general case. One of them is described in the existing answer from @didierc. An alternative is recursion.
For example, think of 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
source to share
This is exactly the same as listing all numbers in the 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 constraint that all numbers must remain different (like the lottery amount as originally stated), and of course we assume m> = n)?
Let's move on by listing all numbers with the above constraint, and also that any element must be greater than its successor in the list (i.e., the rank digit is k < n
greater than the rank digit k+1
) .This is implemented by a simple check when calculating the carry that the current digit is not will become equal to its predecessor, and if so propagates the transfer further.
Then, for each list generated by the enumeration, calculate all possible permutations. Algorithms are known to perform this computation, see, for example, the Johnson-Trotter algorithm , but a simpler recursive algorithm can be constructed:
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'
source to share