代碼，以生成所有可能的組合

如果我有3個蘋果和2桶我可以整理如下：代碼，以生成所有可能的組合

1蘋果在桶A和2個蘋果在桶乙
2蘋果在桶A和1個蘋果在桶中的B桶甲
3蘋果和蘋果0在桶中的B桶乙
3蘋果和在桶甲

等0蘋果1..

我正在嘗試製作某種程序，當蘋果的數量可以是任意數量且桶的數量也可以是任意數量時，這些程序將爲我生成這樣的組合。我的直覺告訴我會涉及一些遞歸，但我甚至無法開始。有人能指引我朝着正確的方向嗎？

來源

2014-12-05 rage

求索排列，你會發現一堆例子 – Steve 2014-12-05 01:53:47

@Steve「排列組合」，因爲他們處理的*不同*的東西的安排聽起來很錯誤的。只要你想要，你就可以排列你的蘋果，什麼都不會發生。 – maaartinus 2014-12-05 02:35:06

@maaartinus這個問題的實際術語實際上是組合，但沒有官方名稱，你會發現一堆無關的帖子，你會發現很多排列的帖子，它提供了'組合'替代品 – Steve 2014-12-05 18:21:33

是的，遞歸可以用於這個問題。

提示，讓您開始：如果你有M蘋果和N桶，那麼解決方案的一個子集，可以通過將m <= M蘋果到第一桶，然後用(M - m)蘋果和N - 1找到的子問題都解決方案找到桶。

來源

2014-12-05 02:35:11

是的，你當然可以使用遞歸，它會通過在堆中保持上下文來簡化事情。但這不是絕對必要的。

這裏有一些（不是很有效，並有很多東西丟失）僞代碼使用interation給你開始的地方，如果你喜歡這種方法。下面的算法看起來有點反直覺，但如果你認爲它通過，你會看到它的作品。我已經試過了，它完美的工作，所以讓我知道如果你卡住了，我會發布一些工作代碼。您可能還想嘗試遞歸和迭代版本，並查看哪一個對您更有意義。

put all apples in first bucket  
while (true) { 
    add the solution to the list   
    firstNonEmptyBucket = find first bucket with any apples; 
    if (firstNonEmptyBucket is the last bucket) 
     break - you are finished 
    shift 1 apple from firstNonEmptyBucket to next bucket 
    if (firstNonEmptyBucket is not the first bucket) 
     shift all apples from firstNonEmptyBucket to previous bucket 
}

來源

2014-12-05 03:22:53 sprinter

代碼，以生成所有可能的組合

回答

相關問題