java - 确定可能的项目组的算法

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