將數字分隔成給定的一組數字

以下是我正在嘗試的操作。給定一個數字和一組數字，我想將該數字分成組中給出的數字（帶有重複）。例如：取數字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

將數字分隔成給定的一組數字

回答

相關問題