将数字分隔成给定的一组数字

以下是我正在尝试的操作。给定一个数字和一组数字，我想将该数字分成组中给出的数字（带有重复）。例如：取数字9，而数字集= {1,4,9}。它将产生以下分区：将数字分隔成给定的一组数字

{（1,1,1,1,1,1,1,1），（1,1,1,1,1,4），（1,1,1,1,1,1），（1,1,1,1,1,1,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个循环的事实并不满意，我想它可以以更优雅的方式进行改进。也许在这种情况下递归更适合。任何建议或更正将不胜感激。提前致谢。

来源

2017-10-06 youth4ever

16'in S' is correct？ –

是的，因为它会忽略它，因为它大于9，是要分区的数字。该功能适用于或不适用。较大的数字不能成为分区的一部分。 – youth4ever

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

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]]

当然，你也可以通过改变函数的参数和假设列表已经排序按相反的顺序离不开内部的功能。

如果要限制大数字部分的数量，您可以添加一个aditional参数，指示剩余的允许的元素数量，如果该数字仍然大于零，则只返回结果。

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))

来源

2017-10-06 18:01:50

Hi Tobias_k。如果我想要限制列表中元素的数量？例如：我不能使用以下函数：nr = 1000和集合S = {1,4,9,16,25,36,49,64,81}。显然是太多了，代码冻结。但是我想限制结果分区的元素数量为10个。这是可以实现的。那么如何做到这一点呢？非常感谢。 – youth4ever

@ youth4ever看我的编辑。但是，请注意，对于您的示例输入，似乎只有10个术语没有解决方案。 –

下面是使用itertools的溶液，并且具有两个for循环所以时间复杂度约为O（N * N）（大致）

小memoization的施加通过去除较大的任何元件来重塑列表比最大总和需要。

假设您将总和设为您设置的最大值（本例中为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

来源

2017-10-06 18:22:12

将数字分隔成给定的一组数字

回答

相关问题