我需要找到二次幂的所有组合,以获得具有特定长度的单个组合的目标和
乙二醇
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))]
假设:
此函数将被多次调用,而且必须快速,我无法使用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
有效查找与给定结果相加的值组合的一种方法是在每个值的频率范围内迭代,从而仅在单个递归调用中填充输出列表一定次数:
输出:
时间:
下图说明了函数
ajax_solution1
相对于基本itertools
实现以及OP代码的更高效率。有关计时源代码的要点,请参见here相关问题 更多 >
编程相关推荐