試圖在Python中實現子集的總和解決方案

我想寫一個蠻力解決方案，以在Python中的子集問題的總和，但沒有得到任何輸出...我是否正確的方式/任何想法我做錯了什麼？試圖在Python中實現子集的總和解決方案

我的代碼：

def ss(set, tVal): 
    #remove items greater than target from list 
    cleaned = [c for c in set if c < tVal] 
    #sort the list 
    cleaned.sort() 

    occurance = 0 
    leftIndex = 0 
    rightIndex = len(cleaned) - 1 
    print("rI length: ", rightIndex) 

    while(leftIndex < rightIndex): 
     #if target value found 
     if cleaned[leftIndex] + cleaned[rightIndex] == tVal: 
      print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex]) 
      #occurance += 1 
      leftIndex += 1 
      rightIndex += 1 
     #else if left index + right index < target increment left index 
     elif cleaned[leftIndex] + cleaned[rightIndex] < tVal: 
      leftIndex += 1 
     #otherwise decrement right index 
     else: 
      rightIndex -= 1 

cities = [18897109, 12828837, 9661105, 6371773, 5965343, 5926800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279933, 3095213, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411] 
target = 101000000 

ss(cities, target)

來源

2017-08-24 user2094257

'set'是Python中的保留字，更好地改變它。 – Vinny

這是有點不清楚你想通過閱讀代碼而不是你的問題描述說明什麼。當你說：「子集總和」時，你是否試圖對這25個城市中的每個可能的子集（例如powerset）進行求和？

如果是這樣，那麼有2^n-1個可能的子集，或者對於n = 25,33554,433。如果您嘗試通過創建一個列表或所有這些子集的集合來將它們讀入內存，您可能會佔用所有內存。

您可以使用發電機來流在時間的結果之一，併爲您的解決方案如：

import itertools 

cities = [18897109, 12828837, 9661105, 6371773, 5965343, 5926800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279933, 3095213, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411] 
target = 101000000 
ps = (set(itertools.combinations(cities,i)) for i in range(len(cities))) 
for s in ps: 
    for x in s: 
     if sum(x) == target: 
      print ('target reached:', x)

接受的答案固定立即解決問題，但我不知道這是否是正確的解決你所描述的問題。

來源

2017-08-24 18:19:51 Solaxun

我正試圖在總共達到目標值的城市原始集合中找到所有可能的人口組合。 – user2094257

感謝您的回答。我從未見過Python中使用的生成器......看起來非常強大。 – user2094257

是的，他們很棒。任何時候你正在處理一個非常大的物品集合，思考生成器。這個具體的例子是一個生成器表達式，它就像一個列表理解但簡單地用圓括號替換括號。 – Solaxun

你確定你的target不關閉的數量級？您的left + right款項永遠不會接近tVal。你的代碼運行正常，循環只是不斷增加leftIndex，直到while失敗。一些print聲明將有助於看到發生了什麼。

修改的ss()裏面咯：

def ss(set, tVal): 

    # ... 

    print("target:  ", tVal) # spacing aligned for printing 

    while(leftIndex < rightIndex): 
     left_plus_right = cleaned[leftIndex] + cleaned[rightIndex] 
     print("left + right: ", left_plus_right) 

     if left_plus_right == tVal: 
      print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex]) 
      leftIndex += 1 
      rightIndex += 1 
     elif left_plus_right < tVal: 
      leftIndex += 1 
     else: 
      rightIndex -= 1 

    # ...

顯示了我們的資金總是大致的比target幅度要小的順序：

target:  101000000 
left + right: 21031520 
left + right: 21039617 
left + right: 21046236 
left + right: 21123118 
left + right: 21253394 
left + right: 21440591 
left + right: 21607598 
left + right: 21680352 
left + right: 21710005 
left + right: 21992322 
left + right: 22177042 
left + right: 22336918 
left + right: 23089996 
left + right: 23121960 
left + right: 23193359 
left + right: 23232500 
left + right: 23449511 
left + right: 24165969 
left + right: 24461744 
left + right: 24479279 
left + right: 24823909 
left + right: 24862452 
left + right: 25268882 
left + right: 28558214 
left + right: 31725946

來源

2017-08-24 18:08:16

似乎有在測試不匹配，這是爲什麼沒有輸出。我添加了一些調試代碼打印每一個計算：

val is lower than tval 21031520 101000000 
val is lower than tval 21039617 101000000 
val is lower than tval 21046236 101000000 
val is lower than tval 21123118 101000000 
val is lower than tval 21253394 101000000 
val is lower than tval 21440591 101000000 
val is lower than tval 21607598 101000000 
val is lower than tval 21680352 101000000 
val is lower than tval 21710005 101000000 
val is lower than tval 21992322 101000000 
val is lower than tval 22177042 101000000 
val is lower than tval 22336918 101000000 
val is lower than tval 23089996 101000000 
val is lower than tval 23121960 101000000 
val is lower than tval 23193359 101000000 
val is lower than tval 23232500 101000000 
val is lower than tval 23449511 101000000 
val is lower than tval 24165969 101000000 
val is lower than tval 24461744 101000000 
val is lower than tval 24479279 101000000 
val is lower than tval 24823909 101000000 
val is lower than tval 24862452 101000000 
val is lower than tval 25268882 101000000 
val is lower than tval 28558214 101000000 
val is lower than tval 31725946 101000000

當我的目標變到的款項之一，它發現它。

>>> ss(cities, 21039617) 
val is lower than tval 21031520 21039617 
found. 1 25

而且，你有這個代碼的問題：

if cleaned[leftIndex] + cleaned[rightIndex] == tVal: 
      print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex]) 
      #occurance += 1 
      leftIndex += 1 
      rightIndex += 1

如果你進入這個狀態，你會嘗試1。如果它沒有在以前的循環減少，增加rightIndex，在下一個電話cleaned[rightIndex] - >
IndexError: list index out of range。

如果rightIndex先小於len(cleaned) - 1，那麼您需要添加一個檢查，然後纔可以增加它。否則，保持原樣。

來源

2017-08-24 18:08:52 Vinny

您的清潔用法不正確。我向你的代碼添加了一個調試打印，發現總數總是超過tVal。因此，如果您的測試總是失敗並且未打印出找到的消息。

舉個例子

lIndex = 24 rIndex = 25 
c[lIndex] = 12828837 c[rIndex] = 18897109 
total - 31725946 tval = 101000000

或者放在一個別人的沒有發現看到這一點。

調試打印即表明這是

while(leftIndex < rightIndex): 
    print 'lIndex = ', leftIndex, 'rIndex = ', rightIndex 
    print 'c[lIndex] = ', cleaned[leftIndex], 'c[rIndex] =', cleaned[rightIndex] 
    mytot = cleaned[leftIndex] + cleaned[rightIndex] 
    print 'total - ', mytot, 'tval = ', tVal 
    if mytot == tVal: 
     print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex]) 
     leftIndex += 1 
     rightIndex +=1 
    elif cleaned[leftIndex] + cleaned[rightIndex] < tVal: 
     leftIndex += 1 
    else: 
     rightIndex -= 1

來源

2017-08-24 18:30:50 sabbahillel

試圖在Python中實現子集的總和解決方案

回答

相關問題