algorithm - 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

这就像枚举 n 位基数 (m+1) 中的所有数字一样。

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

更新：只是为了好玩，如果我们添加所有数字必须保持不同的限制（如彩票号码，如最初所述 - 当然我们假设 m >= n），那么解决方案是什么？

我们继续枚举具有上述限制的所有数字，并且任何元素都必须大于列表中的后继元素（即 rankk < n的数字大于 rank 的数字k+1）。这是通过在计算进位时简单地检查当前数字不会等于其前任数字来实现的，如果是，则进一步传播进位。

然后，对于通过枚举产生的每个列表，计算所有可能的排列。有已知的算法可以执行该计算，例如参见Johnson-Trotter 算法，但可以构建一个更简单的递归算法：

 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'

Answer 2

编写一般情况有两种简单的方法。一个在@didierc 的现有答案中进行了描述。另一种方法是递归。

例如，考虑一个将 String 作为参数的方法：

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