Search type | Search syntax |
---|---|
タグ | [タグ] |
完全一致 | "ここの単語" |
作成者 |
user:1234 user:me (あなたの) |
スコア |
score:3 (3+) score:0 (なし) |
回答 |
answers:3 (3+) answers:0 (なし) isaccepted:yes hasaccepted:no inquestion:1234 |
閲覧数 | views:250 |
コード | code:"if (foo != bar)" |
セクション |
title:リンゴ body:"リンゴ オレンジ" |
URL | url:"*.example.com" |
セーブ | in:saves |
状態 |
closed:yes duplicate:no migrated:no wiki:no |
種類 |
is:question is:answer |
除外 |
-[タグ] -リンゴ |
高度な検索の詳細については、ヘルプ ページをご覧ください。 |
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
0
票
和がkとなるようなn個の非負整数の順列を全列挙する
若干計算量が改善された解法を共有します.
# Python 3.10.5
from itertools import product
def sol(n, k):
for perm in product(range(k+1), repeat=n-1):
if (x := sum(perm)) <= k:
yield *perm, k-x
1
票
2
回答
251
閲覧数
和がkとなるようなn個の非負整数の順列を全列挙する
和がkとなるようなn個の非負整数の順列を重複なく全列挙する方法が知りたいです.
ナイーブに実装しましたがO(k^n),これより計算量が改善される解法は存在しますか.
# Python 3.10.5
from itertools import product
def sol(n, k):
for perm in product(range(k+1), repeat=n):
…
1
票
Python で再帰処理を高速化するには?
コード6行目if i not in traced:がボトルネックになっているものと思われます.
参考:
Python - TimeComplexity
実装は単にDFSを行うだけですが,「このノードはどこのノードから遷移してきたのか」という情報を持つリストを用意し,遷移時にこのリストを更新します.探索終了後,逆順に(yから)辿っていくとxからyへのパスが得られます.
以下実装例.
import …
2
票
1
回答
224
閲覧数
ある範囲で広義単調増加する数列を列挙する
次の条件を満たす数列を列挙する方法はありますか.
長さがNの正整数列
1 <= A_1 <= A_2 <= ... <= A_N <= M
1 <= N, M <= 10
再帰関数を用いることにより目的は一先ず達成出来ましたが,配列のコピーのためパフォーマンスは悪いものと想像します.
N = 2
M = 3
a = [0] * N
def dfs(pre_a, depth):
if …