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

this would be the number of partitions of n which contain only integers from the set [3,7]

similar to the regular partition problem (where the elements can be any positive integer):

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

i don't see an existing number sequence that matches this constraint exactly, but you can count the groups like so (in python). this can take an arbitrary range ([3,7] in this case) and count all the a,b,c,d,e (3*a + 4*b + 5*c + 6*d + 7*e) sequences that sum to 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)

you'd have:

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)

or @Cletus's excellent solution

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.

Answer 3

A tree is the best way to think about it I think, but you can use recursion to build one without explicitly making a tree. You can think of the root as your total. Using groups of size 3-7, you need to find some combination of groups that sums up to your total.

You can use 0 groups of 7, 1 group of 7, 2 groups of 7, etc. For each of those values, you can use 0 groups of 6, 1 group of 6, etc. The first level of your tree will represent how many 7's were used. The second level is how many 6's were used, etc. When you use x 7's, then you need to figure out how many combinations of 6's, 5's, 4's, and 3's you can use to sum up to (sum-x*7), and so on for each lower level (recursive call).

Your tree will always have 5 levels.

Using recursion to build the tree, here is a small Python code sample (with no attempt to prune the tree, it will explore the entire thing).

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, "")

This outputs:

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 4

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 5

In pseudocode:

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

The first two cases are pretty straight-forward. The third one, you figure out (for example) how many groups of size 3 there are - that can be any number between 0 and n/3, and then recursively the function with [4, 5, 6, 7], etc.

Answer 6

What you are describing is a less general version of the partition function.

The algorithms already given are ridiculously complicated, here is a simpler one (in pseudo-code, I will leave it up to you to translate to Java :) )

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