Python二次幂的组合以获得目标和

Question

我需要找到二次幂的所有组合，以获得具有特定长度的单个组合的目标和

乙二醇

target_sum = 10
target_len = 3  # (number of powers of two to use)
input_list = [1, 1, 2, 2, 2, 4, 4, 8]

值1、2、4等的重复是可变的，但总是<= target_len

生产中的实际投入约为10000个元素，目标总和为5/50000，目标长度高达1000个

另一种表示输入的方法是[(1, 2), (2, 3), (4, 2), (8, 1)]（与collections.Counter(input_list)相同）

解决办法是： ^后一种表示法中的{}或[((1, 2), (8, 1)), ((2, 1), (4, 2))]

假设：

• 2的幂是连续的（不能是1，1，2，2，8，…）

此函数将被多次调用，而且必须快速，我无法使用itertools探索所有解决方案。*

我已经找到了一个解决方案，速度快但不优雅，我想知道是否有人有一个好主意

（欢迎使用cython或c类代码）

编辑

用作引用的函数为

def pow2_to_target_len_sum_reference(x: (list, tuple), target_sum, target_len):
    return [i for i in set(itertools.combinations(x, target_len)) if sum(i) == target_sum]

这快了约10公里，但很难看

def _make_first_guess(t, target_sum, target_len):
    guess , valid = [], []

    v, n = t
    for i in range(1, n + 1):
        s = v * i
        if s > target_sum:
            break
            
        reach_sum = s == target_sum
        reach_len = i == target_len

        if reach_sum & (i < target_len):
            break
        if reach_len & (s < reach_sum):
            break
        if reach_sum and reach_len:
            valid.append((v, i))
            break

        guess.append(([(v, i)], s, i))
    return guess, valid


def _evaluate_next_guess(t, target_sum, target_len, cur_sum, cur_len):
    guess, valid = [], []

    v, n = t
    for i in range(1, n + 1):

        temp_len = cur_len + i
        temp_sum = cur_sum + (v * i)

        reach_sum = temp_sum == target_sum
        reach_len = temp_len == target_len

        if reach_sum & reach_len:
            valid.append((v, i))
            break
        elif reach_sum | reach_len:
            break
        else:
            if temp_sum > target_sum:
                break
            if temp_len > target_len:
                break

        guess.append(((v, i), temp_sum, temp_len))
    return guess, valid


def _append_guess(comb, list_prev_guess, target_sum, target_len):
    list_new_guess, ret_valid = [], []

    for cur_guess, cur_sum, cur_len in list_prev_guess:
        list_guess_to_append, list_valid = _evaluate_next_guess(comb, target_sum, target_len, cur_sum, cur_len)

        for valid in list_valid:
            ret_valid.append(cur_guess + [valid])
        for new_guess, new_sum, new_len in list_guess_to_append:
            concat_guess = cur_guess + [new_guess]
            list_new_guess.append((concat_guess, new_sum, new_len))

    return list_new_guess, ret_valid


def pow2_to_target_len_sum(li, target_sum: int, target_len: int):
    # list like [1,1,1,2,2,4,4,4,8,8,16,16,16,16]
    list_counts = list(Counter(li).items())
    rev_counts = list_counts[::-1]

    ret = []

    for i in range(len(rev_counts)):
        starting_list = rev_counts[i:]
        list_guess, valid = _make_first_guess(starting_list[0], target_sum, target_len)

        # ret += valid

        if not list_guess:
            continue

        found_solution = False
        for tup in starting_list[1:]:
            new_guess, valid_after = _append_guess(tup, list_guess, target_sum, target_len)
            if valid_after:
                found_solution = True
            valid += valid_after
            # ret += valid
            list_guess += new_guess

        if valid:
            # ret at first guess: List[Tuple[int, int]]
            # ret after first guess: List[List[Tuple[int, int]]]
            # if the right solution is found at first guess ret must be fixed
            ret += valid if found_solution else [valid]

    list_readable = []

    for solution in ret:
        nested = [[i] * j for i, j in solution[::-1]]
        list_readable.append(tuple([i for j in nested for i in j]))

    return list_readable

Answer 1

有效查找与给定结果相加的值组合的一种方法是在每个值的频率范围内迭代，从而仅在单个递归调用中填充输出列表一定次数：

from collections import Counter
target_sum = 10
max_len = 3
input_list = [1, 1, 2, 2, 2, 4, 4, 4, 8]
def ajax_solution1(target_sum, max_len, input_list):
    def get_combos(d, l = 0, c = [], cl = 0):
        if l == target_sum and cl == max_len:
            yield tuple(c)
        elif d and d[0][0] + l <= target_sum:
            for i in range(1, d[0][-1]+1):
                if d[0][0]*i + l <= target_sum and cl + i <= max_len:
                    yield from get_combos(d[1:], l=l+(d[0][0]*i), c = c+([d[0][0]]*i), cl = cl+i)
            yield from get_combos(d[1:], l = l, c = c, cl= cl)
    [(_, x), *vals], r = Counter(input_list).items(), []
    for i in range(1, x+1):
        if target_sum%2 == i%2:
            if i <= max_len and i <= target_sum:
                r.extend(list(get_combos(vals, l = i, c=([1]*i), cl = i)))
    r.extend(list(get_combos(vals)))
    return r

print(ajax_solution1(target_sum, max_len, input_list))

输出：

[(1, 1, 8), (2, 4, 4)]

---

时间：

下图说明了函数ajax_solution1相对于基本itertools实现以及OP代码的更高效率。有关计时源代码的要点，请参见here