PHP algorithm which calculates all possible combinations of dividing one set between another set

Question

I'm looking for a kind of 2-dimensional combination algorithm.. if that's the correct wording. I'm pretty experienced with PHP, but not with algorithms and advanced math so bear with me please.

I have a set of elements that I want to combine with another set of elements and calculate all possible combinations so that I can analyze it afterwards. The number of elements in the sets never changes, both sets always have five elements:

$set1= array('A', 'B', 'C', 'D', 'E');
$set2= array('One', 'Two', 'Three', 'Four', 'Five');

Don't know if this is the correct phrasing but I'd like to see all the combinations of Set 1 items, divided between the items of Set 2. All elements from both sets should only be used once per possibility and the Set 1 elements can be grouped together within a Set 2 element, so that I get a resulting array that looks like this (some random values as examples):

$possibilities= array(
  0 => array(
    'One' => array('A'),
    'Two' => array('B'),
    'Three' => array('C'),
    'Four' => array('D'),
    'Five' => array('E'),
  ),
  1 => array(
    'One' => array('A', 'B', 'C'),
    'Two' => array('D'),
    'Three' => array('E'),
    'Four' => array(),
    'Five' => array(),
  ),
  2 => array(
    'One' => array('C'),
    'Two' => array(),
    'Three' => array('A'),
    'Four' => array('B'),
    'Five' => array('D', 'E'),
  ),
  3 => array(
    'One' => array(),
    'Two' => array(),
    'Three' => array('A', 'B', 'C', 'D', 'E'),
    'Four' => array(),
    'Five' => array(),
  ),
);

Etc.. those kind of values. Any kind of feedback on this is welcome, particularly:

• How to code something like this in PHP? Through a recursive function? Do I use a Cartesian Product algorithm?
• How many combinations are possible? 5^10 ?
• Depending on the previous point: Is it feasible to work with this data in real time within a web app? If I have 10 million combinations than I suppose I'll probably need to do the calculations beforehand, save the resulting analysis and work with that during the live app execution?
• There are some restrictions (eg: Set 2 items 'One', 'Two' and 'Three' should always have at least one item from Set 1) but useless combinations will be dropped during analysis afterwards so no need to include that in the the combination algorithm, unless it can reduce the calculation time by building these in at that point?

My question may not be very clear so just ask if I need to provide some more or better information.

Thanks in advance

---

Update 28-02-2012

I have tried PHP implementations of Power Set & Cartesian Product functions I found on the internet (This kind of stuff is a bit beyond me to try and code myself). So when I execute this code:

$powerset= powerSet(array('A', 'B', 'C'));
$cartesian = cartesian(array(
    'Set1' => $powerset,
    'Set2' => array('One', 'Two', 'Three')
));

This is what the powerSet function puts in $powerset:

Array (
      [0] => Array ()
      [1] => Array (
        [0] => A
      )
      [2] => Array (
        [0] => B
      )
      [3] => Array (
        [0] => B
        [1] => A
      )
      ...

And this is what the cartesian function returns:

Array (
      [0] => Array (
        [Set1] => Array ()
        [Set2] => One
      )
      [1] => Array (
        [Set1] => Array (
          [0] => A
        )
        [Set2] => One
      )
      [2] => Array (
        [Set1] => Array (
          [0] => B
        )
        [Set2] => One
      )
      [3] => Array (
        [Set1] => Array (
          [0] => B
          [1] => A
        )
        [Set2] => One
      )
      ...

So it kind of does what I wanted, but not the hardest part. It considers the combinations "individually" and doesn't distribute Set1 within Set2, making sure all Set1 items are used per all three Set2 items.

• Am I misinterpreting the use of these two functions? I presume it's something I'm not correctly understanding about how to combine Power Set & Cartesian Product to achieve my result. Should I maybe call the powerSet() function within the cartesian() function?
• Maybe those specific PHP functions don't exactly serve my purpose? I found them here:
  • Power set: http://bohuco.net/blog/2008/11/php-arrays-power-set-and-all-permutations/
  • Cartesian product: Finding cartesian product with PHP associative arrays

---

Another update: Restating the problem without programming reference

This problem is related to an analysis tool I'm creating for a strategic game. Each time the tool gets used, players can select 5 different units from a large collection of units. These units can be combined with other (static) entities (let's call these "pools") in a variety of ways. The units have characteristics that may or may not improve the player's strategy if they are combined with certain pools. For example:

• Unit A loves to be in pool 1 but hates to be in pool 2
• Unit B hates to be in pool 1 unless if Unit A is there as well
• etc..

The tool's purpose is to find the best combinations of which units go in which pool. These are the rules:

• There are always 5 different units selected out of a collection of about 50. All these units have different characteristics.
• There are always the same 5 pools. They have different characteristics but the pools are not selected out of a larger collection, they're always the same.
• Each pool can contain multiple units, from 0 to 5.
• Each unit can only be in one pool.

The input is:

• A list of 5 variable units: A, B, C, D, E
• A list of 5 static pools: Pool1, Pool2, Pool3, Pool4, Pool5

The output should be, all possible combinations between these two lists, based on the aforementioned rules. Some examples:

Combination 1

• Pool 1: A
• Pool 2: B
• Pool 3: C
• Pool 4: D
• Pool 5: E

Combination 2

• Pool 1: A, B, C
• Pool 2: D
• Pool 3: E
• Pool 4:
• Pool 5:

Combination 3

• Pool 1: C
• Pool 2:
• Pool 3: A
• Pool 4: B
• Pool 5: D, E

Combination 4

• Pool 1:
• Pool 2:
• Pool 3: A, B, C, D, E
• Pool 4:
• Pool 5:

etc...

So what I would like to do is:

1. Take all possible combinations of units and pools there exist.
2. Go through them and assign the combination a "strategy value" based on the synergy between the units and the pools.
3. Take the top 10 combinations that have the highest "strategy value"

Step 2 and 3 are no problem. The issue I'm having is generating all possible combinations of the units in the pools.

Hopefully this is a more clear description of the problem

Answer 1

OK, so now I think I've figured out what you want to do. The collections of units are not elements of the power set of the set of units, they are (nearly) elements of the partitions of the set of units. I write 'nearly' because, strictly speaking, the empty set is not a member of the set of partitions of a set. Now I think your problem is to compute all the partitions of a set of 5 units; that partition will have at most 5 elements (each containing one of the units). For your problem any partition of the set of units which itself does not have 5 members should be padded with occurrences of the empty set.

Now you have to map those partitions to an ordering of pools. Your first combination maps the pools to elements of the partition of the set of units thus: {1->{A}, 2->{B}, 3->{C}, 4->{D}, 5->{E}}. If you also want the other combinations which map pools to the same partition of the set of units (such as {2->{A}, 3->{B}, 4->{C}, 5->{D}, 1->{E}} then you'll have to compute all the permutations of the pools and map each to the same partition of the set of units.

Repeat until finished.

Answer 2

You can use a kd-tree or a treemap algorithm. This kind of algorithm is good to find the nearest neighbor, closest-pair of point or addressing the space, tiling the space.