93053


次の条件を満たす数列を列挙する方法はありますか．

  * 長さがNの正整数列
  * 1 <= A_1 <= A_2 <= ... <= A_N <= M
  * 1 <= N, M <= 10

再帰関数を用いることにより目的は一先ず達成出来ましたが，配列のコピーのためパフォーマンスは悪いものと想像します．

[code]

    N = 2
    M = 3
    
    a = [0] * N
    def dfs(pre_a, depth):
        if depth == N:
            pool.append(a.copy())
            return
        for i in range(pre_a, M + 1):
            a[depth] = i
            dfs(i, depth + 1)
    
    pool = []
    dfs(1, 0)
    pool  # [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
    
[/code]

`itertools`等を用いてスマートに書く方法が御座いましたらご教示下さい．


CC BY-SA 4.0
2022-12-27T15:33:45.627
93052
2022-12-27T21:03:39.260
51374
question
python python3 アルゴリズム
ある範囲で広義単調増加する数列を列挙する


[combinations_with_replacement](https://docs.python.org/ja/3/library/itertools.html#itertools.combinations_with_replacement)を使いましょう。

[code]

    from itertools import combinations_with_replacement
    
    N = 2
    M = 3
    
    print(list(combinations_with_replacement(range(1, M + 1), N)))
    #[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
    
[/code]

各要素をタプルではなくリストにしたいなら、`map(list, ...)`で囲みましょう。

[code]

    print(list(map(list, combinations_with_replacement(range(1, M + 1), N))))
    #[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
    
[/code]


CC BY-SA 4.0
2022-12-27T21:03:39.260
93053
2022-12-27T21:03:39.260
43506
93052
answer