PHP Find All (somewhat) Unique Combinations of an Array
If you don't mind using a couple of global variables, you could do this in PHP (translated from a version in JavaScript):
<?PHP
$result = array();
$combination = array();
function combinations(array $myArray, $choose) {
global $result, $combination;
$n = count($myArray);
function inner ($start, $choose_, $arr, $n) {
global $result, $combination;
if ($choose_ == 0) array_push($result,$combination);
else for ($i = $start; $i <= $n - $choose_; ++$i) {
array_push($combination, $arr[$i]);
inner($i + 1, $choose_ - 1, $arr, $n);
array_pop($combination);
}
}
inner(0, $choose, $myArray, $n);
return $result;
}
print_r(combinations(array(20,20,22,24), 3));
?>
OUTPUT:
Array ( [0] => Array ( [0] => 20
[1] => 20
[2] => 22 )
[1] => Array ( [0] => 20
[1] => 20
[2] => 24 )
[2] => Array ( [0] => 20
[1] => 22
[2] => 24 )
[3] => Array ( [0] => 20
[1] => 22
[2] => 24 ) )
Finding all unique permutations of an array efficiently
So after much analysis and taking the code apart, I have come to the conclusion that the memory exhausted error will always occur, no matter how the function is coded. As you increase the number of array elements you exponentially increase the amount of possible combinations to the point of reaching the system memory limit.
I have therefore limited the input array to 15 which would produce 32,768 possible combinations. This should cover the most likely use case of this function.
Thanks @Anant_Singh for taking a look.
Find all possible unique combinations of elements of an array in PHP
Fast solution using recursion, probably not the best way to do it, but it gets the job done.
<?php
$arr = array(1,2,3);
$result = array();
function combinations($arr, $level, &$result, $curr=array()) {
for($i = 0; $i < count($arr); $i++) {
$new = array_merge($curr, array($arr[$i]));
if($level == 1) {
sort($new);
if (!in_array($new, $result)) {
$result[] = $new;
}
} else {
combinations($arr, $level - 1, $result, $new);
}
}
}
for ($i = 0; $i<count($arr); $i++) {
combinations($arr, $i+1, $result);
}
// TEST
foreach ($result as $arr) {
echo join(" ", $arr) . '<br>';
}
?>
PHP: How to get all possible combinations of 1D array?
I believe your professor will be happier with this solution:
<?php
$array = array('Alpha', 'Beta', 'Gamma', 'Sigma');
function depth_picker($arr, $temp_string, &$collect) {
if ($temp_string != "")
$collect []= $temp_string;
for ($i=0, $iMax = sizeof($arr); $i < $iMax; $i++) {
$arrcopy = $arr;
$elem = array_splice($arrcopy, $i, 1); // removes and returns the i'th element
if (sizeof($arrcopy) > 0) {
depth_picker($arrcopy, $temp_string ." " . $elem[0], $collect);
} else {
$collect []= $temp_string. " " . $elem[0];
}
}
}
$collect = array();
depth_picker($array, "", $collect);
print_r($collect);
?>
This solves it:
Array
(
[0] => Alpha
[1] => Alpha Beta
[2] => Alpha Beta Gamma
[3] => Alpha Beta Gamma Sigma
[4] => Alpha Beta Sigma
[5] => Alpha Beta Sigma Gamma
[6] => Alpha Gamma
[7] => Alpha Gamma Beta
[8] => Alpha Gamma Beta Sigma
[9] => Alpha Gamma Sigma
[10] => Alpha Gamma Sigma Beta
[11] => Alpha Sigma
[12] => Alpha Sigma Beta
[13] => Alpha Sigma Beta Gamma
[14] => Alpha Sigma Gamma
[15] => Alpha Sigma Gamma Beta
[16] => Beta
[17] => Beta Alpha
[18] => Beta Alpha Gamma
[19] => Beta Alpha Gamma Sigma
[20] => Beta Alpha Sigma
[21] => Beta Alpha Sigma Gamma
[22] => Beta Gamma
[23] => Beta Gamma Alpha
[24] => Beta Gamma Alpha Sigma
[25] => Beta Gamma Sigma
[26] => Beta Gamma Sigma Alpha
[27] => Beta Sigma
[28] => Beta Sigma Alpha
[29] => Beta Sigma Alpha Gamma
[30] => Beta Sigma Gamma
[31] => Beta Sigma Gamma Alpha
[32] => Gamma
[33] => Gamma Alpha
[34] => Gamma Alpha Beta
[35] => Gamma Alpha Beta Sigma
[36] => Gamma Alpha Sigma
[37] => Gamma Alpha Sigma Beta
[38] => Gamma Beta
[39] => Gamma Beta Alpha
[40] => Gamma Beta Alpha Sigma
[41] => Gamma Beta Sigma
[42] => Gamma Beta Sigma Alpha
[43] => Gamma Sigma
[44] => Gamma Sigma Alpha
[45] => Gamma Sigma Alpha Beta
[46] => Gamma Sigma Beta
[47] => Gamma Sigma Beta Alpha
[48] => Sigma
[49] => Sigma Alpha
[50] => Sigma Alpha Beta
[51] => Sigma Alpha Beta Gamma
[52] => Sigma Alpha Gamma
[53] => Sigma Alpha Gamma Beta
[54] => Sigma Beta
[55] => Sigma Beta Alpha
[56] => Sigma Beta Alpha Gamma
[57] => Sigma Beta Gamma
[58] => Sigma Beta Gamma Alpha
[59] => Sigma Gamma
[60] => Sigma Gamma Alpha
[61] => Sigma Gamma Alpha Beta
[62] => Sigma Gamma Beta
[63] => Sigma Gamma Beta Alpha
)
Find unique combinations of values from arrays filtering out any duplicate pairs
Since the structure is just obscuring the numbers which are available, you should first unfold the nested arrays. I'll be kind and do that for you:
$numbers = []
foreach ($arrar as $subarr) {
foreach ($subarr as $num) {
$numbers[] = $num;
}
}
I'm assuming there aren't any duplicate numbers in the input.
Next, you want to perform your algorithm for finding the unique combinations. With array this small, even a recursive solution will work. You don't have to try all the combinatorially-many combinations.
Get all unique combinations from array for a given number of elements
I finally found out a way to add recursive function to create unique combinations from given numbers:
$numbers = [1, 2, 3, 4, 5, 6, 7];
function subsetSumRecursive($numbers, $arraySize, $level = 1, $i = 0, $addThis = [])
{
// If this is the last layer, use a different method to pass the number.
if ($level == $arraySize) {
$result = [];
for (; $i < count($numbers); $i++) {
$result[] = array_merge($addThis, array($numbers[$i]));
}
return $result;
}
$result = [];
$nextLevel = $level + 1;
for (; $i < count($numbers); $i++) {
// Add the data given from upper level to current iterated number and pass
// the new data to a deeper level.
$newAdd = array_merge($addThis, array($numbers[$i]));
$temp = subsetSumRecursive($numbers, $arraySize, $nextLevel, $i, $newAdd);
$result = array_merge($result, $temp);
}
return $result;
}
echo "<pre>";
print_r(subsetSumRecursive($numbers, 7));
echo "</pre>";
Find all the possible combinations of array elements with two attributes where neither repeats
- Ok, so you need to first collect all possible pairs as you did.
- Now, we will try to place a pair at a location if no collision in the grid and check with other pairs.
- If the current placement fails, we try another location and so on and so forth.
(Scroll to the end to check with a working demo if you would like to see this in action first)
generateGrid:
<?php
function generateGrid($colors, $emotions, &$grid){
$combs = [];
foreach($colors as $color){
foreach($emotions as $emotion){
$combs[] = [$color, $emotion];
}
}
/* initialize grid */
for($i = 0; $i < count($colors); ++$i){
for($j = 0; $j < count($emotions); ++$j){
$grid[ $i ][ $j ] = [];
}
}
/* initializing grid ends */
if(makeGrid($combs, $grid, 0, count($colors) * count($emotions))){
return true;
}
$grid = [];// restore the grid to original state
return false;
}
makeGrid:
<?php
function makeGrid($combs, &$grid, $idx, $total){
if($idx == $total) return true;
for($i = 0; $i < count($grid); ++$i){
for($j = 0; $j < count($grid[ $i ]); ++$j){
if(count($grid[ $i ][ $j ]) == 0){
if(noCollision($combs[ $idx ], $i, $j, $grid)){
$grid[ $i ][ $j ] = $combs[ $idx ];
if(makeGrid($combs, $grid, $idx + 1, $total)){
return true;
}
$grid[ $i ][ $j ] = [];
}
}
}
}
return false;
}
noCollision check method:
<?php
function noCollision($element, $row, $col, $grid){
$rowSet = [];
for($i = 0; $i < count($grid[ $row ]); ++$i){
if(count( $grid[ $row ][ $i ]) > 0){
$rowSet[$grid[ $row ][ $i ][ 0 ]] = true;
$rowSet[$grid[ $row ][ $i ][ 1 ]] = true;
}
}
if(isset($rowSet[ $element[0] ]) || isset($rowSet[ $element[1] ])){
return false;
}
$colSet = [];
for($i = 0; $i < count($grid); ++$i){
if(count( $grid[ $i ][ $col ]) > 0){
$colSet[$grid[ $i ][ $col ][ 0 ]] = true;
$colSet[$grid[ $i ][ $col ][ 1 ]] = true;
}
}
return !(isset($colSet[ $element[0] ]) || isset($colSet[ $element[1] ]));
}
Driver code:
<?php
$grid = [];
if(generateGrid([ 'gold', 'silver', 'bronze', 'wood' ], [ 'happy', 'sad', 'wow', 'angry'], $grid)){
printGrid($grid);
}else{
throw new \Exception("No solution found!!");// or whatever you would like to have here
}
Online Demo
Code Demo to print all combinations
PHP array combinations
You can use the solution found here http://stereofrog.com/blok/on/070910.
Incase the link goes down here's the code....
class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
foreach(new Combinations("1234567", 5) as $substring)
echo $substring, ' ';
12345 12346 12347 12356 12357 12367 12456 12457 12467 12567 13456 13457 13467 13567 14567 23456 23457 23467 23567 24567 34567
Related Topics
Laravel 5.3 Withcount() Nested Relation
Unescape or HTML Decode in Twig (PHP Templating)
Setting Post Variable Without Using Form
Exclude Hidden Files from Scandir
How to Prefix a Positive Number with Plus Sign in PHP
Fatal Error: Call to a Member Function Query() on Null
Parsing JavaScript (Not JSON) in PHP
Get Total Time Difference Between Two Dates Using PHP
PHP Type-Hinting to Primitive Values
How to Easily Convert Dates from Utc via PHP
Rsa Encryption/Decryption Compatible with JavaScript and PHP