Algorithm to determine possible groups of items

Question

I am scratching my head trying to do this and it's eating me up. I know it is not THAT complex. I have a number of items, this number can be equal or greater than three. Then I need to determine the possible combination of group of items that will complete the total. The only restriction it's that the groups should have three or more items, not exceeding (but including) seven items.

For example:

If I have 7 items, then I could have these possible groups:

• 1 group of 7 items.
• 1 group of 4 items and 1 group of 3 items.

If I have 12 items, I could have these possible groups:

• 4 groups of 3 items.
• 3 groups of 4 items.
• 2 groups of 6 items.
• 1 group of 7 items + 1 group of 5 items.
• 2 groups of 3 and 1 group of 6 items.
• 1 group of 3, 1 group of 4 and 1 group of five items.
• ...

I thought about recursion and started implementing the algorithm. It's obviously not working. I suck at recursion. A lot.

//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);
                }
            }
        }
    }
}

Thanks for your help!!!

Answer 1

Here's an algorithm (expressed in C++) to solve a more general version of the problem, with arbitrary upper and lower bounds on the addends that may appear in each partition:

#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);
}

And some sample output:

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

It can be done with recursion. You don't say if you just want the number of possibilities or the actual possibilities.

One thing you want to do is avoid repetition meaning don't count 4 and 3 also as 3 and 4. One way to do that is to create sequences of non-descending group sizes.

Probably the best data structure for this is a tree:

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

Then to find the number of combinations you simply count the leaf nodes. To find the actual combinations you just walk the tree.

The algorithm for building such a tree goes something like this:

• Function buildTree(int size, int minSize, Tree root)
• Count i from size down to minSize;
• Create a child of the current node with value i;
• For each j from minSize to i that is less than or equal to i
  • Create a new child of value j
  • Call `buildTree(j, minSize, new node)

or something very close to that.