Python中的子序列和递归

Question

上周末，我在HackerRank上做广告无限挑战赛。在

一个问题是计算一个有限序列的所有子序列的和，如果每个子序列被认为是一个整数。在

例如，序列4,5,6会给出答案4+5+6+45+46+56+456=618。在

我找到了一个递归，并编写了下面的Python代码。它解决了5/13个测试用例。在

剩下的8/13个测试用例有运行时错误。在

我希望有人能发现代码中效率低下的地方，以及如何加快速度。或者，帮我决定递归不是最好的策略。在

# Input is a list, representing the given sequence, e.g. L = [4,5,6]

def T(L): 
    limit = 10**9 + 7  # answer is returned modulo 10**9 + 7
    N = len(L)
    if N == 1: 
        return L[0]
    else:
        last = L[-1] 
        K = L[:N-1]
        ans =  T(K)%limit + 10*T(K)%limit + (last%limit)*pow(2,N-1,limit)
        return ans%limit

Answer 1

假设你指的是连续的子序列。在

test = [4, 5, 6]

def coms(ilist):
    olist = []
    ilist_len = len(ilist)
    for win_size in range(ilist_len, 0, -1):
        for offset in range((ilist_len - win_size) + 1):
            subslice = ilist[offset: offset + win_size]
            sublist  = [value * (10 ** power) for (power, value) in enumerate(reversed(subslice))]
            olist.extend(sublist)
    return olist

print sum(coms(test))

Answer 2

这是我对同一个问题（玛纳萨和子序列）的意见。 https://www.hackerrank.com/contests/infinitum-may14/challenges/manasa-and-sub-sequences

我希望这能帮助你想出更好的办法。在

ans = 0
count = 0
for item in raw_input():
    temp = (ans * 10 + (count + 1)*(int(item)))%1000000007
    ans = (ans + temp)%1000000007
    count = (count*2 + 1)%1000000007

print ans

Answer 3

好吧，你想要组合：

from itertools import combinations

def all_combinations(iterable):
    for r in range(len(digits)):
        yield from combinations(digits, r+1)

你想把它们转换成整数：

^{pr2}$

你想把它们相加：

sum(map(digits_to_int, all_combinations([4, 5, 6])))

然后关注速度。在