确定可能的项目组的算法

Question

我正试图这样做,它正在吞噬我.我知道这不复杂.我有很多项目,这个数字可以等于或大于3.然后我需要确定完成总计的项目组的可能组合.唯一的限制是团体应该有三件或更多件,不超过(但包括)七件.

例如:

如果我有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组五项.
• ...

我考虑了递归并开始实现算法.这显然不起作用.我吮吸递归.很多.

//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