将一个数字划分为一组给定的数字

Question

这就是我要做的。给定一个数字和一组数字，我想将该数字划分为集合中给出的数字（重复）。例如：取数字 9，一组数字 = {1， 4， 9}。它将产生以下分区：

{ （1， 1， 1， 1， 1， 1， 1， 1）， （1， 1， 1， 1， 4）， （1， 4

， 4）， （9，）}

不能形成使用集合 {1， 4， 9} 的其他可能的分区来对数字 9 求和。

我用Python写了一个函数来执行任务：

S = [ 1, 4, 9, 16 ]
def partition_nr_into_given_set_of_nrs(nr , S):
   lst = set()
   # Build the base case :
   M = [1]*(nr%S[0]) + [S[0]] * (nr //S[0])
   if set(M).difference(S) == 0  :
      lst.add(M)
   else :
      for x in S :
         for j in range(1, len(M)+1):
            for k in range(1, nr//x +1 ) :
               if  k*x ==  sum(M[:j]) :
                  lst.add(  tuple(sorted([x]*k + M[j:])) )
   return lst

它

工作正常，但我想看看一些关于它的意见。我对它使用 3 个循环的事实不满意，我想它可以以更优雅的方式改进。也许递归更适合这种情况。任何建议或更正将不胜感激。提前谢谢。

Answer 1

我会使用递归函数来解决这个问题，从最大的数字开始，然后递归地找到剩余值的解决方案，使用越来越小的数字。

def partition_nr_into_given_set_of_nrs(nr, S):
    nrs = sorted(S, reverse=True)
    def inner(n, i):
        if n == 0:
            yield []
        for k in range(i, len(nrs)):
            if nrs[k] <= n:
                for rest in inner(n - nrs[k], k):
                    yield [nrs[k]] + rest
    return list(inner(nr, 0))
S = [ 1, 4, 9, 16 ]
print(partition_nr_into_given_set_of_nrs(9, S))
# [[9], [4, 4, 1], [4, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1]]

当然，您也可以通过更改函数的参数并假设列表已经以相反的顺序排序来不使用内部函数。

如果要限制大数字的零件数，可以添加一个附加参数，指示剩余允许的元素数，并且仅在该数字仍大于零时才产生结果。

def partition_nr_into_given_set_of_nrs(nr, S, m=10):
    nrs = sorted(S, reverse=True)
    def inner(n, i, m):
        if m > 0:
            if n == 0:
                yield []
            for k in range(i, len(nrs)):
                if nrs[k] <= n:
                    for rest in inner(n - nrs[k], k, m - 1):
                        yield [nrs[k]] + rest
    return list(inner(nr, 0, m))

Answer 2

这是一个使用 itertools 的解决方案，有两个 for 循环，因此时间复杂度约为 O（n*n）（大致）

通过删除任何大于所需最大总和的元素来应用于重塑列表的一点记忆。

假设您取的总和是集合的最大值（在本例中为 9）。

源代码

import itertools
x = [ 1, 4, 9, 16 ]
s = []
n = 9
#Remove elements >9
x = [ i for i in x if i <= n]
for i in xrange(1,n + 1):
    for j in itertools.product(x,repeat = i):
        if sum(j) == n:
            s.append(list(j))
#Sort each combo
s =[sorted(i) for i in s]
#group by unique combo
print list(k for k,_ in itertools.groupby(s))

结果

>>> 
>>> 
[[9], [1, 4, 4], [1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1]]

编辑

您可以通过在产品总和> 9后停止查找组合来进一步优化速度（如果需要）例如

if sum(j) > n + 2:
            break