algorithm - PHP Find All (somewhat) Unique Combinations of an Array

Question

I've been looking at PHP array permutation / combination questions all day.. and still can't figure it out :/

If I have an array like:

20 //key being 0    
20 //key being 1    
22 //key being 2    
24 //key being 3

I need combinations like:

20, 20, 22 //keys being 0 1 2    
20, 20, 24 //keys being 0 1 3    
20, 22, 24 //keys being 0 2 3
20, 22, 24 //keys being 1 2 3

The code I currently have gives me:

20, 22, 24

because it doesn't want to repeat 20... but that's what I need!

Here is the code I have. it is directly from Php recursion to get all possibilities of strings

function getCombinations($base,$n){

$baselen = count($base);
if($baselen == 0){
    return;
}
    if($n == 1){
        $return = array();
        foreach($base as $b){
            $return[] = array($b);
        }
        return $return;
    }else{
        //get one level lower combinations
        $oneLevelLower = getCombinations($base,$n-1);

        //for every one level lower combinations add one element to them that the last element of a combination is preceeded by the element which follows it in base array if there is none, does not add
        $newCombs = array();

        foreach($oneLevelLower as $oll){

            $lastEl = $oll[$n-2];
            $found = false;
            foreach($base as  $key => $b){
                if($b == $lastEl){
                    $found = true;
                    continue;
                    //last element found

                }
                if($found == true){
                        //add to combinations with last element
                        if($key < $baselen){

                            $tmp = $oll;
                            $newCombination = array_slice($tmp,0);
                            $newCombination[]=$b;
                            $newCombs[] = array_slice($newCombination,0);
                        }

                }
            }

        }

    }

    return $newCombs;


}

I've been playing around with the ($b == $lastEl) line, with no luck

===============

Questions I've already looked at, and are not the same OR that created an out of memory error!:

• How can I get all permutations in PHP without sequential duplicates?
• Permutations - all possible sets of numbers
• Combinations, Dispositions and Permutations in PHP
• PHP array combinations
• Get all permutations of a PHP array?
• PHP: How to get all possible combinations of 1D array?
• Select only unique array values from this array
• Get all permutations of a PHP array?
• PHP: How to get all possible combinations of 1D array?
• Select only unique array values from this array
• How can I get all permutations in PHP without sequential duplicates?
• Algorithm to return all combinations of k elements from n
• Find combination(s) sum of element(s) in array whose sum equal to a given number
• Combinations, Dispositions and Permutations in PHP
• PHP array combinations
• Php recursion to get all possibilities of strings
• How to return permutations of an array in PHP?
• Permutations - all possible sets of numbers
• Subset-sum problem in PHP with MySQL
• Find unique combinations of values from arrays filtering out any duplicate pairs
• Finding all the unique permutations of a string without generating duplicates
• Generate all unique permutations
• Subset sum for exactly k integers?

I've tried some of these algorithms with an array of 12 items, and end up running out of memory. However the algorithm that I'm currently using doesn't give me an out of memory error.... BUT.. I need those duplicates!

Answer 1

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