使用乘法獲得整數的獨特組合的算法

我得到了一堆2和3，我必須一起乘。現在我想要生成這些數字的每個獨特組合，以便當這些組合相乘時不會超過10.使用乘法獲得整數的獨特組合的算法

例如，我有類似的東西。

2*2*2*2*3*3*3

我可以從上面得到以下有效組合。

4*4*9*3 
8*6*9 
4*2*6*9

但是下面的組合是錯誤的。 16*3*9和4*4*27。

有人可以提出一個算法來做到這一點？

來源

2010-11-12 chappar

作業？一個比賽？對於現實生活中的問題聽起來有些過於虛構。 – Bolo 2010-11-12 18:55:36

對於我試圖解決的投影儀問題:-)。有一個暴力方法，但我不滿意。 – chappar 2010-11-12 19:00:43

因爲這裏的一個被乘數超過10. – chappar 2010-11-12 19:08:55

該解決方案可以遞歸構建。將輸入視爲一個數字列表，如[2,2,2,2,3,3,3]。將列表分成前綴（如[2,2]）和相應的後綴（在這種情況下爲[2,2,3,3,3]）。現在多個條目中的前綴（我們在本例中得到4），並遞歸地解決後綴相同的問題。將多重性中的值插入到每個後綴解決方案的開頭，我們就可以得到原始問題的答案。

在下面的Python代碼中，函數collapse中定義了遞歸邏輯，該函數找到所有有效前綴（其多重性小於10），並將多重性插入切除後摺疊剩餘數據時返回的所有結果前綴（collapse(d[prefix_len:])）。

a = [2,2,2,2,3,3,3] 

def collapse(d): 
    if len(d) > 0: 
     for prefix_len in range(1, len(d) + 1): 
      prefix = reduce(lambda x,y: x*y, d[:prefix_len], 1) 
      if prefix > 10: 
       break 
      for suffix in collapse(d[prefix_len:]): 
       yield [prefix] + suffix 
    else: 
     yield d 

for i in collapse(a): 
    print i

輸出是

[2, 2, 2, 2, 3, 3, 3] 
[2, 2, 2, 2, 3, 9] 
[2, 2, 2, 2, 9, 3] 
[2, 2, 2, 6, 3, 3] 
[2, 2, 2, 6, 9] 
[2, 2, 4, 3, 3, 3] 
[2, 2, 4, 3, 9] 
[2, 2, 4, 9, 3] 
[2, 4, 2, 3, 3, 3] 
[2, 4, 2, 3, 9] 
[2, 4, 2, 9, 3] 
[2, 4, 6, 3, 3] 
[2, 4, 6, 9] 
[2, 8, 3, 3, 3] 
[2, 8, 3, 9] 
[2, 8, 9, 3] 
[4, 2, 2, 3, 3, 3] 
[4, 2, 2, 3, 9] 
[4, 2, 2, 9, 3] 
[4, 2, 6, 3, 3] 
[4, 2, 6, 9] 
[4, 4, 3, 3, 3] 
[4, 4, 3, 9] 
[4, 4, 9, 3] 
[8, 2, 3, 3, 3] 
[8, 2, 3, 9] 
[8, 2, 9, 3] 
[8, 6, 3, 3] 
[8, 6, 9]

來源

2010-11-12 19:17:42

錯過了一些有效的組合，例如'[8，6，9]'。我想你想在範圍（1，len（d）+ 1）中爲'prefix_len：'。 – 2010-11-13 00:59:46

這不會打印所有組合。例如：對於列表[2，2，3，3]，它不會打印[6,6] – chappar 2010-11-13 06:05:39

@matthew感謝您指出了這一點。它是固定的。 @chapprar我認爲OP不希望列表中數字的切換次序，所以[4,9]有效，而[6,6]不是。這只是我的假設。 – 2010-11-13 22:01:47

如果爲了事項（即2 * 4 * 2是不一樣的2 * 2 * 4），你必須將他們列（即「生成」），那麼你應該只是遞歸地做。在斯卡拉：

def combine(who: List[Int], limit: Int=10): List[List[Int]] = who match { 
    case x :: y :: more => 
    combine(y :: more, limit).map(x :: _) ::: 
    (if (x*y<limit) combine((x*y) :: more, limit) else Nil) 
    case x :: Nil => List(who) 
    case Nil => List() 
}

你可能不知道斯卡拉，所以這裏是三種情況下的工作方式。第一種情況：列表中至少剩下兩個元素。選取第一個元素並將其添加到所有可能的後續組合中。然後，如果您可以合併第一個和第二個元素，請執行此操作，並查找以此開頭的列表的所有組合。第二種情況：只有一個元素的平凡列表;作爲列表中唯一的東西返回。第三種情況：退化輸入（沒有給出數值）;返回一個空列表。

（在Scala中，:::連接兩個列表一起，而x :: list棒x上的list前當你匹配，這是不言而喻的其他方式：case x :: stuff使用，如果列表可以分爲元素x 。剩下的，stuffNil是空列表）

這是在行動：

scala> combine(List(2,2,2,2,3,3,3)) 

res18: List[List[Int]] = List(List(2, 2, 2, 2, 3, 3, 3), List(2, 2, 2, 2, 3, 9), 
    List(2, 2, 2, 2, 9, 3), List(2, 2, 2, 6, 3, 3), List(2, 2, 2, 6, 9), 
    List(2, 2, 4, 3, 3, 3), List(2, 2, 4, 3, 9), List(2, 2, 4, 9, 3), 
    List(2, 4, 2, 3, 3, 3), List(2, 4, 2, 3, 9), List(2, 4, 2, 9, 3), List(2, 4, 6, 3, 3), 
    List(2, 4, 6, 9), List(2, 8, 3, 3, 3), List(2, 8, 3, 9), List(2, 8, 9, 3), 
    List(4, 2, 2, 3, 3, 3), List(4, 2, 2, 3, 9), List(4, 2, 2, 9, 3), List(4, 2, 6, 3, 3), 
    List(4, 2, 6, 9), List(4, 4, 3, 3, 3), List(4, 4, 3, 9), List(4, 4, 9, 3), 
    List(8, 2, 3, 3, 3), List(8, 2, 3, 9), List(8, 2, 9, 3), List(8, 6, 3, 3), List(8, 6, 9))

編輯：如果你只是想數它們，你會使用不同類型的重複。假設S(n)是從n開始的組合數，並且L(n)爲列表中n項的值。然後

S(i) = S(i+1) + 
     if (L(i)+L(i+1)<10) S(i+2) + 
     if (L(i)+...+L(i+2)<10) S(i+3) + 
     ....

所以你從最後一項開始 - 只有一種可能性 - 然後按順序使用這個公式。（如果這是你以後的事情，我會寫代碼，但希望算法足夠清晰。）

來源

2010-11-12 19:35:29

使用乘法獲得整數的獨特組合的算法

回答

相關問題