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

Question

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

{ (1, 1, 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

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

Partition a number into a given set of numbers

python

numbers

set

partition