合計が任意の値となる整数の組み合わせを求める(部分和問題)

How many ways can you make the sum of a number in javascript. How to code lt in javascript? [on hold] – StackOverflow

def comb(t, tpl=(), s=None):
    if s is None: s = set()
    for i in range(1, t+1):
        res = tuple(sorted((*tpl, i)))
        if res in s:
            break
        elif t - i == 0:
            yield res
            s.add(res)
        else:
            yield from comb(t-i, (*tpl, i), s)            


for x in comb(4):
    print('+'.join(map(str, x)))
1+1+1+1
1+1+2
1+3
2+2
4
def count_dp(S, t):
    dp = [1] + [0]*t
    for i in S:
        for j in range(t-i+1):
            dp[i+j] += dp[j]
    return dp[t]
 

def count_dfs(lst: sorted, t: int) -> int:
    if t == 0:
        return 1
    elif len(lst) == 0:
        return 0
    else:
        return sum(count_dfs(lst[1:], t-lst[0]*i) for i in range(t//lst[0]+1))


lst, t = list(range(1, 5)), 4
count_dp(lst, t), count_dfs(lst, t)
(5, 5)
import numpy as np
 

def print_allcomb(S, t, repeated=True, file=None):
    elm = [np.arange(0, t+1, s).reshape(-1, *[1]*(len(S)-1-i)) for i, s in enumerate(S)]
    idx = np.argwhere(np.sum(elm)==t)
    if not repeated:
        idx = idx[~(idx>1).any(1)]
        out = set()
    for subl in idx.tolist():
        temp = [S[i] for i, n in enumerate(subl) for _ in range(n)]
        if repeated:
            print('+'.join(map(str, temp)), file=file)
        else:
            s = '+'.join(map(str, temp))
            if s not in out:
                print(s, file=file)
            out.add(s)


print_allcomb(lst, t)
4
2+2
1+3
1+1+2
1+1+1+1
%timeit list(comb(4))
%timeit list(comb(10))

f = open('/dev/null', 'w')
%timeit print_allcomb(list(range(1, 5)), 4, file=f)
%timeit print_allcomb(list(range(1, 11)), 10, file=f)
100000 loops, best of 3: 18 µs per loop
1000 loops, best of 3: 1.36 ms per loop

10000 loops, best of 3: 53.1 µs per loop
1000 loops, best of 3: 1.65 ms per loop

 
 
関連:
硬貨の和(任意の合計値を満たす組み合わせの総数)

すべての部分集合和を求める(部分和問題)

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください