这里有一个处理重复项的解决方案。
首先，如前所述，找到任何解决方案的问题是NP完全的。因此，在某些情况下，这将花费很长时间才能意识到没有解决方案。我应用了合理的启发式方法来限制这种情况发生的频率。这些启发式方法可以改进。但请注意，有时根本没有解决方案。
这个解决方案的第一步是将数字列表转换为[(value1, repeat), (value2, repeat), ...]。其中一个启发式要求首先按绝对值降序排序，然后按值递减排序。这是因为我尝试首先使用第一个元素，我们期望一堆小的剩余数字仍然能给我们带来总和。
接下来，我将尝试将其拆分为可能的最大子集，具有正确的目标总和和所有剩余元素。
然后，我将把剩余部分拆分为可能的最大剩余子集不大于第一个，以及在此之后产生的那些元素。
递归执行此操作，我们就会找到一个解决方案。然后我们将其返回到上层。
但是，这里有一个棘手的地方，我不会通过查看组合来进行拆分。相反，我将使用动态规划，就像我们通常用于子集和伪多项式算法一样，只是我将用它来构建一个数据结构，从中我们可以进行拆分。这个数据结构将包含以下字段：
value 是该元素的值。repeat 是在子集和中使用它的次数。skip 是我们拥有但没有在子集和中使用的副本数量。tail 是这些解决方案的尾部。prev 是其他一些解决方案，其中我们做了其他事情。
下面是一个构建此数据结构的类，其中包含将元素拆分为子集和仍可用于进一步拆分的方法。
from collections import namedtuple
class RecursiveSums (
namedtuple('BaseRecursiveSums',
['value', 'repeat', 'skip', 'tail', 'prev'])):
def sum_and_rest(self):
if self.tail is None:
if self.skip:
yield ([self.value] * self.repeat, [(self.value, self.skip)])
else:
yield ([self.value] * self.repeat, [])
else:
for partial_sum, rest in self.tail.sum_and_rest():
for _ in range(self.repeat):
partial_sum.append(self.value)
if self.skip:
rest.append((self.value, self.skip))
yield (partial_sum, rest)
if self.prev is not None:
yield from self.prev.sum_and_rest()
你可能需要多看几次才能理解它的工作原理。
接下来，记住我说过我使用一种启发式方法尝试在使用小元素之前使用大元素。这是我们需要进行比较的一些代码。
class AbsComparator(int):
def __lt__ (self, other):
if abs(int(self)) < abs(int(other)):
return True
elif abs(other) < abs(self):
return False
else:
return int(self) < int(other)
def abs_lt (x, y):
return AbsComparator(x) < AbsComparator(y)
我们需要两种形式。一种是用于直接比较的函数，另一种是用于Python的
sort函数中的
key参数的类。有关后者的更多信息，请参见
使用比较器函数进行排序。
现在是方法的核心。这会找到所有分成子集（在我们使用的比较度量中不大于
bound）和更多拆分的剩余元素的方法。
这个想法与动态规划方法解决子集和问题的方法相同
https://www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/，但有两个主要区别。第一个区别是，我们正在构建数据结构而不是计算答案。第二个区别是，我们的键是
(partial_sum, bound_index)，因此我们知道我们的
bound当前是否满足，如果不满足，我们知道下一个要比较的元素是什么来测试它。
def lexically_maximal_subset_rest (elements, target, bound=None):
"""
elements = [(value, count), (value, count), ...]
with largest absolute values first.
target = target sum
bound = a lexical bound on the maximal subset.
"""
if 0 == len(elements):
if 0 == target:
yield []
elif bound is None or 0 == len(bound):
yield from lexically_maximal_subset_rest(elements, target, [abs(elements[0][0]) + 1])
elif abs_lt(bound[0], elements[0][0]):
pass
else:
bound_satisfied = (bound[0] != elements[0][0])
recurse_by_sum = {}
(init_value, init_count) = elements[0]
for i in range(init_count):
if not bound_satisfied:
if len(bound) <= i or abs_lt(bound[i], init_value):
break
elif abs_lt(init_value, bound[i]):
bound_satisfied = True
if bound_satisfied:
key = (init_value * (i+1), None)
else:
key = (init_value * (i+1), i)
recurse_by_sum[key] = RecursiveSums(
init_value, i+1, init_count-i-1, None, recurse_by_sum.get(key))
for j in range(1, len(elements)):
value, repeat = elements[j]
next_recurse_by_sum = {}
for key, tail in recurse_by_sum.items():
partial_sum, bound_index = key
next_recurse_by_sum[key] = RecursiveSums(
value, 0, repeat, tail, next_recurse_by_sum.get(key))
for i in range(1, repeat+1):
if bound_index is not None:
if len(bound) <= bound_index + i:
break
elif abs_lt(bound[bound_index + i], value):
break
elif abs_lt(value, bound[bound_index + i]):
bound_index = None
if bound_index is None:
next_key = (partial_sum + value * i, None)
else:
next_key = (partial_sum + value * i, bound_index + i)
next_recurse_by_sum[next_key] = RecursiveSums(
value, i, repeat - i, tail, next_recurse_by_sum.get(next_key))
recurse_by_sum = next_recurse_by_sum
bound_index = len(bound)
while 0 < bound_index:
bound_index -= 1
if (target, bound_index) in recurse_by_sum:
yield from recurse_by_sum[(target, bound_index)].sum_and_rest()
if (target, None) in recurse_by_sum:
yield from recurse_by_sum[(target, None)].sum_and_rest()
现在我们来实现剩下的部分。
def elements_split (elements, target, k, bound=None):
if 0 == len(elements):
if k == 0:
yield []
elif k == 0:
pass
else:
for (subset, rest) in lexically_maximal_subset_rest(elements, target, bound):
for answer in elements_split(rest, target, k-1, subset):
answer.append(subset)
yield answer
def subset_split (raw_elements, k):
total = sum(raw_elements)
if 0 == (total % k):
target = total // k
counts = {}
for e in sorted(raw_elements, key=AbsComparator, reverse=True):
counts[e] = 1 + counts.get(e, 0)
elements = list(counts.items())
yield from elements_split(elements, target, k)
这里是使用您的列表进行演示，它被加倍了。我们将其分成4个相等的部分。在我的笔记本电脑上，它在0.084秒内找到了所有10个解决方案。
n = 0
for s in subset_split([4, 3, 5, 6, 4, 3, 1]*2, 4):
n += 1
print(n, s)
所以...没有性能保证。但这通常应该能够快速找到每个分割点。当然，通常还有指数级别的分割点。例如，如果您将列表复制16次并尝试将其分成32组，则在我的笔记本电脑上需要大约8分钟才能找到所有224082个解决方案。
如果我不尝试处理负数，这可以加快速度。（使用更便宜的比较，删除已超过target的所有部分和以避免计算大部分动态规划表。）
这是加速版本。对于仅包含非负数的情况，它的速度大约快两倍。如果存在负数，则会产生错误结果。
from collections import namedtuple
class RecursiveSums (
namedtuple('BaseRecursiveSums',
['value', 'repeat', 'skip', 'tail', 'prev'])):
def sum_and_rest(self):
if self.tail is None:
if self.skip:
yield ([self.value] * self.repeat, [(self.value, self.skip)])
else:
yield ([self.value] * self.repeat, [])
else:
for partial_sum, rest in self.tail.sum_and_rest():
for _ in range(self.repeat):
partial_sum.append(self.value)
if self.skip:
rest.append((self.value, self.skip))
yield (partial_sum, rest)
if self.prev is not None:
yield from self.prev.sum_and_rest()
def lexically_maximal_subset_rest (elements, target, bound=None):
"""
elements = [(value, count), (value, count), ...]
with largest absolute values first.
target = target sum
bound = a lexical bound on the maximal subset.
"""
if 0 == len(elements):
if 0 == target:
yield []
elif bound is None or 0 == len(bound):
yield from lexically_maximal_subset_rest(elements, target, [abs(elements[0][0]) + 1])
elif bound[0] < elements[0][0]:
pass
else:
bound_satisfied = (bound[0] != elements[0][0])
recurse_by_sum = {}
(init_value, init_count) = elements[0]
for i in range(init_count):
if not bound_satisfied:
if len(bound) <= i or bound[i] < init_value:
break
elif init_value < bound[i]:
bound_satisfied = True
if bound_satisfied:
key = (init_value * (i+1), None)
else:
key = (init_value * (i+1), i)
recurse_by_sum[key] = RecursiveSums(
init_value, i+1, init_count-i-1, None, recurse_by_sum.get(key))
for j in range(1, len(elements)):
value, repeat = elements[j]
next_recurse_by_sum = {}
for key, tail in recurse_by_sum.items():
partial_sum, bound_index = key
next_recurse_by_sum[key] = RecursiveSums(
value, 0, repeat, tail, next_recurse_by_sum.get(key))
for i in range(1, repeat+1):
if target < partial_sum + value * i:
break
if bound_index is not None:
if len(bound) <= bound_index + i:
break
elif bound[bound_index + i] < value:
break
elif value < bound[bound_index + i]:
bound_index = None
if bound_index is None:
next_key = (partial_sum + value * i, None)
else:
next_key = (partial_sum + value * i, bound_index + i)
next_recurse_by_sum[next_key] = RecursiveSums(
value, i, repeat - i, tail, next_recurse_by_sum.get(next_key))
recurse_by_sum = next_recurse_by_sum
bound_index = len(bound)
while 0 < bound_index:
bound_index -= 1
if (target, bound_index) in recurse_by_sum:
yield from recurse_by_sum[(target, bound_index)].sum_and_rest()
if (target, None) in recurse_by_sum:
yield from recurse_by_sum[(target, None)].sum_and_rest()
def elements_split (elements, target, k, bound=None):
if 0 == len(elements):
if k == 0:
yield []
elif k == 0:
pass
else:
for (subset, rest) in lexically_maximal_subset_rest(elements, target, bound):
for answer in elements_split(rest, target, k-1, subset):
answer.append(subset)
yield answer
def subset_split (raw_elements, k):
total = sum(raw_elements)
if 0 == (total % k):
target = total // k
counts = {}
for e in sorted(raw_elements, key=AbsComparator, reverse=True):
counts[e] = 1 + counts.get(e, 0)
elements = list(counts.items())
yield from elements_split(elements, target, k)
n = 0
for s in subset_split([4, 3, 5, 6, 4, 3, 1]*16, 32):
n += 1
print(n, s)
if len(l) < 2 or sum(l) % 2 != 0:。在您的示例[1,2]中，列表的总和（3）不可被2整除，因此我的代码返回[]。 - Bsh