確定可能的項目羣的算法

Question

我正在抓我的頭試圖做到這一點，它讓我吃了起來。我知道這並不複雜。我有一些項目，這個數字可以等於或大於三。然後我需要確定將完成總計的一組項目的可能組合。唯一的限制就是團體應該有三件或更多的物品，不超過（但包括）七件物品。

例如：

如果我有7個項目，然後我可以有這些可能的組：

• 1組7項。
• 1組4件商品和1組3件商品。

如果我有12個項目，我可以有這些可能的組：

• 4組，每組3個項目。
• 3組4項。
• 2組6件商品。
• 1組7件商品+ 1組5件商品。
• 2組3個和1組6個項目。
• 1組3,1組4,1組5項。
• ...

我想到了遞歸和開始實施的算法。這顯然不起作用。我吮吸遞歸。很多。

//Instance Fields 
public List<ArrayList<String>> options; 

//Method that will generate the options. The different options are 
//stored in a list of "option". An individual option will store a list of 
//strings with the individual groups. 
public void generateOptions(int items, ArrayList<String> currentOption){ 

    //If the current option is null, then create a new option. 
    if(currentOption == null){ 
     currentOption = new ArrayList<String>(); 
    } 
    if(items < 3){ 
     //If the number of items is less than three then it doesn't comply with the 
     //requirements (teams should be more or equal than three. 
     currentOption.add("1 group of "+items+" items"); 
     options.add(currentOption); 
    } 
    else{ 
     //I can make groups of 3,4,5,6 and 7 items. 
     for(int i = 3;i<=7;i++){ 
      if(items%i == 0){ 
       // If the number of items is divisible per the current number, 
       // then a possible option could be items/i groups of i items. 
       // Example: Items = 9. A possible option is 3 groups of 3 items. 
       currentOption.add(items/i +" groups of "+ i+" items"); 
       options.add(currentOption); 
      } 
      else{ 
       // If the number of items - the current number is equal or greater than 
       // three, then a possible option could be a group of i items 
       // and then I'll have items-i items to separate in other groups. 
       if(items - i >=3){ 
        currentOption.add("1 group of "+i+" items"); 
        generateOptions(items-i,currentOption); 
       } 
      } 
     } 
    } 
} 

感謝您的幫助！

Answer 1

下面是一個算法（在C++表示），以解決該問題， 與可能出現在每一個加數任意上限和下限的一個更一般的版本分區：

#include <iostream> 
#include <vector> 

using namespace std; 

typedef vector<int> Partition; 
typedef vector<Partition> Partition_list; 

// Count and return all partitions of an integer N using only 
// addends between min and max inclusive. 

int p(int min, int max, int n, Partition_list &v) 
{ 
    if (min > max) return 0; 
    if (min > n) return 0;  
    if (min == n) { 
     Partition vtemp(1,min); 
     v.push_back(vtemp); 
     return 1; 
    } 
    else { 
    Partition_list part1,part2; 
    int p1 = p(min+1,max,n,part1); 
    int p2 = p(min,max,n-min,part2); 
    v.insert(v.end(),part1.begin(),part1.end()); 
    for(int i=0; i < p2; i++) 
    { 
     part2[i].push_back(min); 
    } 
    v.insert(v.end(),part2.begin(),part2.end()); 
    return p1+p2; 
    } 
} 

void print_partition(Partition &p) 
{ 
    for(int i=0; i < p.size(); i++) { 
     cout << p[i] << ' '; 
    } 
    cout << "\n"; 
} 

void print_partition_list(Partition_list &pl) 
{ 
    for(int i = 0; i < pl.size(); i++) { 
     print_partition(pl[i]); 
    } 
} 

int main(int argc, char **argv) 
{ 
    Partition_list v_master; 

    int n = atoi(argv[1]); 
    int min = atoi(argv[2]); 
    int max = atoi(argv[3]); 
    int count = p(min,max,n,v_master); 
    cout << count << " partitions of " << n << " with min " << min ; 
    cout << " and max " << max << ":\n" ; 
    print_partition_list(v_master); 
} 

和一些輸出樣本：

$ ./partitions 12 3 7    
6 partitions of 12 with min 3 and max 7: 
6 6 
7 5 
4 4 4 
5 4 3 
6 3 3 
3 3 3 3 
$ ./partitions 50 10 20    
38 partitions of 50 with min 10 and max 20: 
17 17 16 
18 16 16 
18 17 15 
19 16 15 
20 15 15 
18 18 14 
19 17 14 
20 16 14 
19 18 13 
20 17 13 
19 19 12 
20 18 12 
13 13 12 12 
14 12 12 12 
20 19 11 
13 13 13 11 
14 13 12 11 
15 12 12 11 
14 14 11 11 
15 13 11 11 
16 12 11 11 
17 11 11 11 
20 20 10 
14 13 13 10 
14 14 12 10 
15 13 12 10 
16 12 12 10 
15 14 11 10 
16 13 11 10 
17 12 11 10 
18 11 11 10 
15 15 10 10 
16 14 10 10 
17 13 10 10 
18 12 10 10 
19 11 10 10 
20 10 10 10 
10 10 10 10 10 

Answer 2

這將是正的partitions包含從所述一組唯一的整數[3,7]

類似於常規分區的問題（其中，元件可以是任何正整數）的數量：

http://www.research.att.com/~njas/sequences/A000041

我看不到一個現有的數字序列完全匹配這個約束，但你可以像這樣（在python中）計數組。這可以取任意的範圍（在這種情況下爲[3,7]）並且計算所有a，b，c，d，e（3 * a + 4 * b + 5 * c + 6 * d + 7 * e）總和爲n的序列。

import sys 

# All partitions for a particular n: 

def groups(n, base, minBase, sum, sets, group = []): 
    c = 0; i = (n - sum)/base 
    while i >= 0: 
    s = sum + base * i 
    if s == n: 
     sets.append(group + [i]); 
     c = c + 1 
    elif s < n and base > minBase: 
     c = c + groups(n, base - 1, minBase, s, sets, (group + [i])) 
    i = i - 1 
    return c 

# Partitions for each n in [1,maxNum] 

def run(maxNum): 
    for i in xrange(1, maxNum + 1): 
    sets = []; maxBase = 7; minBase = 3 
    n = groups(i, maxBase, minBase, 0, sets) 
    print ' %d has %d groups:\n' % (i, n) 
    for g in sets: 
     x = len(g) - 1 
     sys.stdout.write('  ') 
     while x >= 0: 
     if g[x] > 0: 
      if x < len(g) - 1: sys.stdout.write(' + ') 
      sys.stdout.write('(%d * %d)' % (maxBase - x, g[x])) 
     x = x - 1 
     print '' 
    if len(sets): print '' 

run(40) 

你必須：

1 has 0 groups: 

2 has 0 groups: 

3 has 1 groups: 

    (3 * 1) 

4 has 1 groups: 

    (4 * 1) 

5 has 1 groups: 

    (5 * 1) 

6 has 2 groups: 

    (6 * 1) 
    (3 * 2) 

7 has 2 groups: 

    (7 * 1) 
    (3 * 1) + (4 * 1) 

8 has 2 groups: 

    (3 * 1) + (5 * 1) 
    (4 * 2) 

9 has 3 groups: 

    (3 * 1) + (6 * 1) 
    (4 * 1) + (5 * 1) 
    (3 * 3) 

10 has 4 groups: 

    (3 * 1) + (7 * 1) 
    (4 * 1) + (6 * 1) 
    (5 * 2) 
    (3 * 2) + (4 * 1) 

11 has 4 groups: 

    (4 * 1) + (7 * 1) 
    (5 * 1) + (6 * 1) 
    (3 * 2) + (5 * 1) 
    (3 * 1) + (4 * 2) 

12 has 6 groups: 

    (5 * 1) + (7 * 1) 
    (6 * 2) 
    (3 * 2) + (6 * 1) 
    (3 * 1) + (4 * 1) + (5 * 1) 
    (4 * 3) 
    (3 * 4) 

13 has 6 groups: 

    (6 * 1) + (7 * 1) 
    (3 * 2) + (7 * 1) 
    (3 * 1) + (4 * 1) + (6 * 1) 
    (3 * 1) + (5 * 2) 
    (4 * 2) + (5 * 1) 
    (3 * 3) + (4 * 1) 

14 has 7 groups: 

    (7 * 2) 
    (3 * 1) + (4 * 1) + (7 * 1) 
    (3 * 1) + (5 * 1) + (6 * 1) 
    (4 * 2) + (6 * 1) 
    (4 * 1) + (5 * 2) 
    (3 * 3) + (5 * 1) 
    (3 * 2) + (4 * 2) 

15 has 9 groups: 

    (3 * 1) + (5 * 1) + (7 * 1) 
    (4 * 2) + (7 * 1) 
    (3 * 1) + (6 * 2) 
    (4 * 1) + (5 * 1) + (6 * 1) 
    (3 * 3) + (6 * 1) 
    (5 * 3) 
    (3 * 2) + (4 * 1) + (5 * 1) 
    (3 * 1) + (4 * 3) 
    (3 * 5) 

或@克萊的優秀的解決方案

Answer 3

它可以使用遞歸來完成。你不會說如果你只是想要一些可能性或實際的可能性。

你想要做的一件事是避免重複意味着不計數4和3也作爲3和4.一種方法是創建非降序組大小的序列。

可能是對此最好的數據結構是樹：

root 
+- 12 
+- 9 
| +- 3 
+- 8 
| +- 4 
+- 7 
| +- 5 
+- 6 
| +- 6 
| +- 3 
|  +- 3 
+- 5 
| +- 4 
|  +- 3 
+- 4 
| +- 4 
|  +- 4 
+- 3 
    +- 3 
     +- 3 
     +- 3 

然後找到組合的號碼，你簡單地計算葉節點。要找到實際的組合，只需走樹。

算法建立這樣的樹是這樣的：

• 功能buildTree（INT大小，詮釋minSize屬性，樹根）
• 計數i從size降至minSize;
• 創建值爲i的當前節點的子節點;
• 對於每個j從minSize到i小於或等於i
  • 創建的值的新的子j
  • 呼叫`buildTree（J，minSize屬性，新節點）

或其他非常接近的東西。

Answer 4

樹是我認爲的最好的思考方式，但是您可以使用遞歸來構建一棵樹，而無需明確地製作一棵樹。你可以把根看作你的總數。使用3-7組的大小，你需要找到一些組合總和的總和。

可以使用0基團的7,1組7，2組的圖7，等。對於每個這些值，可以使用0基團的6個，1組6等的第一級的樹會表示使用了多少個7。第二個層次是使用了多少個6，等等。當你使用x 7時，你需要計算出6，5，4和3可以用來求和的總數（sum-x * 7） ，等等每個較低的級別（遞歸調用）。

你的樹總是有5個關卡。

使用遞歸構建樹，這裏是一個小的Python代碼示例（有沒有嘗試修剪樹，它會探索整個事情）。

MIN = 3 
MAX = 7 

def findComb(remaining, start, path): 
    times = remaining/start 

    if start == MIN: 
     if remaining % MIN == 0: 
      print "%s, %d %d's" % (path[1:], times, start) 
     return 

    for i in range(0, times+1): 
     findComb(remaining- (i*start), start-1, "%s, %d %d's" % (path, i, start)) 


findComb(12, MAX, "") 

此輸出：

0 7's, 0 6's, 0 5's, 0 4's, 4 3's 
0 7's, 0 6's, 0 5's, 3 4's, 0 3's 
0 7's, 0 6's, 1 5's, 1 4's, 1 3's 
0 7's, 1 6's, 0 5's, 0 4's, 2 3's 
0 7's, 2 6's, 0 5's, 0 4's, 0 3's 
1 7's, 0 6's, 1 5's, 0 4's, 0 3's 

Answer 5

僞代碼：

List<String> results; 

void YourAnswer(int n) { 
    GeneratePossiblities("", [3, 4, 5, 6, 7], n); 
} 

void GeneratePossibilities(String partialResult, List<int> buildingBlocks, int n) { 
    if (n == 0) { 
     // We have a solution 
     results.Add(partialResult); 
    } else if (buildingBlocks.IsEmpty()) { 
     // Dead-end: there is no solution that starts with the partial result we have and contains only the remaining building blocks 
     return; 
    } else { 
     int first = buildingBlocks.First(); 
     buildingBlocks.PopFirst(); 
     for (int i = 0, i < n/first; i++) { 
      GeneratePossibilities(partialResult + " " + i + "groups of " + first, 
           buildingBlocks, 
           n - i * first); 
     } 
    } 
} 

前兩種情況是非常直接的。第三個，你可以找出（例如）有多少個3的大小 - 可以是0到n/3之間的任何數字，然後遞歸地使用[4,5,6,7]等等。

Answer 6

你所描述的是partition function的不太一般的版本。

已經給出的算法是可笑的複雜，下面是一個簡單的一個（僞代碼，我會離開它給你翻譯成Java :)）

p(min, n): 
    if min > n: return 0 
    if min = n: return 1 
    return p(min+1, n) + p(min, n-min)