StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFinding all non-conflicting combinations of values from multiple lists of values
text
Body
copied!<p>I have the following array which contains arrays of values:</p> <pre><code>$array = array( array('1', '2'), array('a', 'b', 'c'), array('x', 'y'), ); </code></pre> <p>There can be any number of arrays and an array can contain any number of values. I currently have a piece of code which will generate all combinations where one value is taken from each array. eg:</p> <pre><code>1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy </code></pre> <p>However what I actually want is only the combinations where only one value sits in each column, ie. 1ax is no good because all three values 1, a and x sit in the first column, 1by is no good because b and y sit in the second column. So from the above example only these combinations would be valid:</p> <pre><code>1cy, 2cx </code></pre> <p>I originally planned to just generate all combinations and then filter out the ones with conflicts, but that doesn't scale as this is an oversimplified example, in the real application there's going to be situations where there are potentially millions of combinations (including conflicting ones).</p> <p>Can anyone help with a better way to solve this? I'm working in PHP, but any code sample that clearly demonstrates the logic would be helpful.</p> <p>Thanks in advance.</p> <hr> <h2>Update:</h2> <p>I've tested the solutions that work against a bigger dataset, to get some benchmarks, these are the results so far:</p> <pre><code>$array = array( array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'), array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'), array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'), array('1', '2', '3', '1', '2', '3', '1', '2', '3'), array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'), array('x', 'y', 'z'), ); </code></pre> <p><strong>Josh Davis 2nd Solution:</strong></p> <pre><code>Combinations: 249480 Time: 0.3180251121521 secs Memory Usage: 22.012168884277 mb Peak Memory Usage: 22.03059387207 mb </code></pre> <p><strong>Josh Davis:</strong></p> <pre><code>Combinations: 249480 Time: 1.1172790527344 secs Memory Usage: 22.004837036133 mb Peak Memory Usage: 22.017387390137 mb </code></pre> <p><strong>Tom Haigh:</strong></p> <pre><code>Combinations: 249480 Time: 5.7098741531372 secs Memory Usage: 39.145843505859 mb Peak Memory Usage: 39.145843505859 mb </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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