Databases
StackOverflow2013
Postsdbo
POPHP algorithm which calculates all possible combinations of dividing one set between another set
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPHP algorithm which calculates all possible combinations of dividing one set between another set
    primarykey
    data
    text
    <p>I'm looking for a kind of <strong>2-dimensional combination algorithm</strong>.. if that's the correct wording. I'm pretty experienced with PHP, but not with algorithms and advanced math so bear with me please.</p> <p>I have a set of <strong>elements that I want to combine with another set of elements and calculate all possible combinations</strong> so that I can analyze it afterwards. The number of elements in the sets never changes, both sets always have five elements:</p> <pre><code>$set1= array('A', 'B', 'C', 'D', 'E'); $set2= array('One', 'Two', 'Three', 'Four', 'Five'); </code></pre> <p>Don't know if this is the correct phrasing but I'd like to see <strong>all the combinations of Set 1 items, divided between the items of Set 2</strong>. 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): </p> <pre><code>$possibilities= array( 0 =&gt; array( 'One' =&gt; array('A'), 'Two' =&gt; array('B'), 'Three' =&gt; array('C'), 'Four' =&gt; array('D'), 'Five' =&gt; array('E'), ), 1 =&gt; array( 'One' =&gt; array('A', 'B', 'C'), 'Two' =&gt; array('D'), 'Three' =&gt; array('E'), 'Four' =&gt; array(), 'Five' =&gt; array(), ), 2 =&gt; array( 'One' =&gt; array('C'), 'Two' =&gt; array(), 'Three' =&gt; array('A'), 'Four' =&gt; array('B'), 'Five' =&gt; array('D', 'E'), ), 3 =&gt; array( 'One' =&gt; array(), 'Two' =&gt; array(), 'Three' =&gt; array('A', 'B', 'C', 'D', 'E'), 'Four' =&gt; array(), 'Five' =&gt; array(), ), ); </code></pre> <p>Etc.. those kind of values. Any kind of feedback on this is welcome, particularly:</p> <ul> <li><strong>How to code something like this in PHP</strong>? Through a recursive function? Do I use a Cartesian Product algorithm?</li> <li>How many combinations are possible? 5^10 ?</li> <li>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?</li> <li>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?</li> </ul> <p>My question may not be very clear so just ask if I need to provide some more or better information.</p> <p>Thanks in advance</p> <hr> <p><strong>Update 28-02-2012</strong></p> <p>I have tried PHP implementations of Power Set &amp; 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: </p> <pre><code>$powerset= powerSet(array('A', 'B', 'C')); $cartesian = cartesian(array( 'Set1' =&gt; $powerset, 'Set2' =&gt; array('One', 'Two', 'Three') )); </code></pre> <p>This is what the powerSet function puts in $powerset:</p> <pre><code>Array ( [0] =&gt; Array () [1] =&gt; Array ( [0] =&gt; A ) [2] =&gt; Array ( [0] =&gt; B ) [3] =&gt; Array ( [0] =&gt; B [1] =&gt; A ) ... </code></pre> <p>And this is what the cartesian function returns:</p> <pre><code>Array ( [0] =&gt; Array ( [Set1] =&gt; Array () [Set2] =&gt; One ) [1] =&gt; Array ( [Set1] =&gt; Array ( [0] =&gt; A ) [Set2] =&gt; One ) [2] =&gt; Array ( [Set1] =&gt; Array ( [0] =&gt; B ) [Set2] =&gt; One ) [3] =&gt; Array ( [Set1] =&gt; Array ( [0] =&gt; B [1] =&gt; A ) [Set2] =&gt; One ) ... </code></pre> <p>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.</p> <ul> <li>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 &amp; Cartesian Product to achieve my result. Should I maybe call the powerSet() function within the cartesian() function?</li> <li>Maybe those specific PHP functions don't exactly serve my purpose? I found them here: <ul> <li>Power set: <a href="http://bohuco.net/blog/2008/11/php-arrays-power-set-and-all-permutations/" rel="nofollow noreferrer">http://bohuco.net/blog/2008/11/php-arrays-power-set-and-all-permutations/</a></li> <li>Cartesian product: <a href="https://stackoverflow.com/questions/6311779/finding-cartesian-product-with-php-associative-arrays">Finding cartesian product with PHP associative arrays</a></li> </ul></li> </ul> <hr> <p><strong>Another update: Restating the problem without programming reference</strong></p> <p>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:</p> <ul> <li>Unit A loves to be in pool 1 but hates to be in pool 2</li> <li>Unit B hates to be in pool 1 unless if Unit A is there as well</li> <li>etc..</li> </ul> <p><strong>The tool's purpose is to find the best combinations of which units go in which pool.</strong> These are the rules:</p> <ul> <li>There are always 5 different units selected out of a collection of about 50. All these units have different characteristics.</li> <li>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.</li> <li>Each pool can contain multiple units, from 0 to 5.</li> <li>Each unit can only be in one pool.</li> </ul> <p><strong>The input is:</strong></p> <ul> <li>A list of 5 variable units: A, B, C, D, E</li> <li>A list of 5 static pools: Pool1, Pool2, Pool3, Pool4, Pool5</li> </ul> <p><strong>The output should be, all possible combinations between these two lists</strong>, based on the aforementioned rules. Some examples:</p> <p>Combination 1</p> <ul> <li>Pool 1: A</li> <li>Pool 2: B</li> <li>Pool 3: C</li> <li>Pool 4: D</li> <li>Pool 5: E</li> </ul> <p>Combination 2</p> <ul> <li>Pool 1: A, B, C</li> <li>Pool 2: D</li> <li>Pool 3: E</li> <li>Pool 4: </li> <li>Pool 5: </li> </ul> <p>Combination 3</p> <ul> <li>Pool 1: C</li> <li>Pool 2: </li> <li>Pool 3: A</li> <li>Pool 4: B</li> <li>Pool 5: D, E</li> </ul> <p>Combination 4</p> <ul> <li>Pool 1: </li> <li>Pool 2: </li> <li>Pool 3: A, B, C, D, E</li> <li>Pool 4: </li> <li>Pool 5:</li> </ul> <p>etc...</p> <p>So <strong>what I would like to do</strong> is:</p> <ol> <li>Take all possible combinations of units and pools there exist.</li> <li>Go through them and assign the combination a "strategy value" based on the synergy between the units and the pools.</li> <li>Take the top 10 combinations that have the highest "strategy value"</li> </ol> <p>Step 2 and 3 are no problem. <strong>The issue I'm having is generating all possible combinations of the units in the pools.</strong></p> <p>Hopefully this is a more clear description of the problem</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USKiluminati
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POPHP algorithm which calculates all possible combinations of dividing one set between another set
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO"Set 2 items 'One', 'Two' and 'Three' should always have at least one item from Set 1", shouldn't this be reflected in your example then?
      singulars
      1. POPHP algorithm which calculates all possible combinations of dividing one set between another set
      1. USWard Muylaert
    2. COThis reminds me of a combinatorics problem that I read about a few years ago. I've a feeling there was a solution for 5 elements, but no known solution for 6... or something like that. You might need to expand about exactly want you want to achieve. perhaps you won't need to write prize-winning algorithms after all :)
      singulars
      1. POPHP algorithm which calculates all possible combinations of dividing one set between another set
      1. USPete
    3. CODoes the ordering matter in a divided array? e.g. is array('A','B','C') considered the same as array('B','C','A') for this problem?
      singulars
      1. POPHP algorithm which calculates all possible combinations of dividing one set between another set
      1. USBijou Trouvaille
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload