n
各要素が0からm
(両端を含む)になるように、サイズのすべてのリストを生成します。
そのようなリストがあり(m+1)^n
ます。
n
各要素が0からm
(両端を含む)になるように、サイズのすべてのリストを生成します。
そのようなリストがあり(m+1)^n
ます。
これは、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と仮定します)?
上記の制限付きですべての数値を列挙します。また、要素はリスト内の後続の要素よりも大きくなければなりません(つまり、ランクk < n
の桁がランクの桁よりも大きい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'
一般的なケースを書く簡単な方法は2つあります。1つは、@didiercからの既存の回答に記載されています。別の方法は再帰です。
たとえば、文字列を引数として取るメソッドについて考えてみます。
if(input string is long enough)
print or store it
else
iterate over digit range
recursive call with the digit appended to the string