current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite

After one week searching and converting many algorithm from other language into php to make an array that contain "combination k from n". I'm stuck. please help me.

This is my code (using php):

function comb($item,$arr,$out, $start, $n, $k, $maxk) {
if ($k > $maxk) {
       foreach($arr as $ar){
           echo "$ar";
           echo "<br/>";
       }
   return;
}

for ($i=$start; $i<=$n; $i++) {
     $arr[$k] = $item[$i-1];
         comb($isi, $arr, $out, $i+1, $n, $k+1, $maxk);
}
}

$team = array("A","B","C","D");
$ar = array();
$o = array();
comb($team,$ar,$o,1,4,1,2);

Recursive algorithm above is really confuse me. The code above was successful to form the combination but I cannot merge them into one array because of its recursive characteristics. I just want to make an array that contain the result of combination of 2 from 4 items. Like this (see below)

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

   [1] => Array (
                  [1] => A
                  [2] => C
          )

   [2] => Array (
                  [1] => A
                  [2] => D
          )

   [3] => Array (
                  [1] => B
                  [2] => C
          )

   [4] => Array (
                  [1] => B
                  [2] => D
          )

   [5] => Array (
                  [1] => C
                  [2] => D
          )
)

I know I still far from the answer. But please guide me, to reach that answer. Perhaps you know the other technique, it doesn't matter. If your code works, I will use it. No matter what the technique you've used. Any ideas would be gratefully appreciated,Thank you..!

share|improve this question
    
This is very similar to all string combinations in a fixed length, based on a charset and you don't need recursion for it. The difference with that question is, it uses string offsets instead of array offsets, but sure you can do the same replacing the charset with an array. Additionally you don't want to have doubles like AA, but that's easy to check for and to drop. –  hakre Mar 18 '12 at 16:15
    
@hakre that question is different in that it considers all strings of length 2, whereas this (essentially) considers sets. For example, here "AB" and "BA" are considered the same and so we only have "AB" once, and "BA" never appears. –  MGwynne Mar 18 '12 at 16:46
    
@MGwynne: Yes, but the way of resolving it should be possible as well w/o recursion (which was merely the point I wanted to make). –  hakre Mar 18 '12 at 16:48

6 Answers 6

up vote 3 down vote accepted

An (I think) simpler recursive implementation is:

<?php

/* Given the array $A, returns the array of $k-subsets
   of $A in lexicographical order. */
function k_lex_subset($A,$k) {
  if (($k <= 0) or (count($A) < $k)) { return array(); }
  else if ($k <= 1) { return array_chunk($A,1); }
  else {
    $v = array_shift($A);
    $AwA = k_lex_subset($A,$k-1);
    foreach($AwA as &$vp) {
      array_unshift($vp,$v);
    }
    $AwoA = k_lex_subset($A,$k);
    $resultArrs = array_merge($AwA, $AwoA);
    return($resultArrs);
  }
}

$team = array("A","B","C","D");
print_r(k_lex_subset($team,2));


?>

which returns

Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
        )

    [1] => Array
        (
            [0] => A
            [1] => C
        )

    [2] => Array
        (
            [0] => A
            [1] => D
        )

    [3] => Array
        (
            [0] => B
            [1] => C
        )

    [4] => Array
        (
            [0] => B
            [1] => D
        )

    [5] => Array
        (
            [0] => C
            [1] => D
        )

)

and will work for any size array, and any $k.

The term you are looking for is (lexicographical) k-subset enumeration where $k is 2 in this specific case.

Explanation

The idea is very simple. Assume we have (for example) a set {A,B,C,D}. We want to start with all sets with A in, and so we consider subsets of size 1-less coming from {B,C,D} and append A to them yielding

{{A,B}, {A,C}, {A,D}}

and then we consider all subsets of size 2 without A in

{{B,C}, {B,D}, {C,D}}

and then we just merge the two. It is hopefully easy to see how, in general, this yields a nice recursive strategy for constructing the k-subsets of a set (instead of just k=2).

Reference

A fantastic reference on this sort of thing is Vol 4 Fasicle 3 of Knuth's The Art of Computing Programming.

share|improve this answer
    
Wow...thank you MGwyne..!!your code is working. That's quite similar with Sorin did. Using recursive way!!Honestly, I currently interested in recursive method in programming. But sometimes it was driving me crazy, I already have that reference, but it's really hard to understand!okay little by little I'll learn from it. Thank you MGwyne... –  thoriqgrady Mar 18 '12 at 16:17
up vote 1 down vote

This should do the trick to reach the array you've described above:

<?php
$array = array("A","B","C","D");

function transformArray( $array ) {

    $returnArray = array();

    for( $i=0; $i < count($array); $i++ ) {

        for( $j=$i+1; $j < count($array); $j++ ) {

            $returnArray[] = array( $array[$i], $array[$j] );

        }

    }

    return $returnArray;

}

print_r(transformArray($array));
?>
share|improve this answer
    
wow..that's working!!thank you hidde, sometimes I love sequential method rather than recursive!! thank you... –  thoriqgrady Mar 18 '12 at 15:49
1  
This method will work, but only if you want it to return the combinations of two elements. If you would like to return the combinations of 10 elements you would have to make 10 for cycles, which would be highly unrecommended. This is however the best answer for your request, but if you need a function that returns combinations take a look at my answer. Cheers! –  Sorin Buturugeanu Mar 18 '12 at 15:57
up vote 1 down vote

Not exactly sure on the necessity of start, n, and k, but this should get you the expected output. If you provide some more details on why those counters would be necessary, we can get you a more thorough answer.

function comb($itemArray, $start, $n, $k, $maxk) {

    //if ($k > $maxk) return;

   $outputArray = array();

    foreach($itemArray AS $index => $firstChar) {

        for($i = $index+1; $i<count($itemArray); $i++) {

            $secondChar = $itemArray[$i];

            $outputArray[] = array($firstChar, $secondChar);

        }

    }

    return $outputArray;

}

$teamArray = array("A","B","C","D");

$resultArray = comb($teamArray,1,4,1,2);

ppr($resultArray);

function ppr($variable) {

    echo '<pre>';

    print_r($variable);

    echo '</pre>';

}
share|improve this answer
up vote 1 down vote 
function comb($a, $len){
    if ($len > count($a))return array();
    $out = array();
    if ($len==1) {
        foreach ($a as $v) $out[] = array($v);
        return $out;
    }
    $len--;
    while (count($a) > $len) {
        $b = array_shift($a);
        $c = comb($a, $len);
        foreach ($c as $v){
            array_unshift($v, $b);
            $out[] = $v;
        }
    }
    return $out;
}

$test = array('a','b','c','d');
$a = comb($test,2);
print_r($a);

would give you:

Array(
[0] => Array
    (
        [0] => a
        [1] => b
    )

[1] => Array
    (
        [0] => a
        [1] => c
    )

[2] => Array
    (
        [0] => a
        [1] => d
    )

[3] => Array
    (
        [0] => b
        [1] => c
    )

[4] => Array
    (
        [0] => b
        [1] => d
    )

[5] => Array
    (
        [0] => c
        [1] => d
    )

)

share|improve this answer
    
Yeaah you are absolutely right Sorin!!Your code is really flexible,that is true combination!how expert you are...thank you!! –  thoriqgrady Mar 18 '12 at 16:05
    
Nice. I personally think it makes more sense to return array() when $len > count($a) as you are basically asking for the set of subsets of $a of size $len, which is simply the empty-set if $len > count($a). –  MGwynne Mar 18 '12 at 16:31
    
@MGwynne you're right. I made the modification. –  Sorin Buturugeanu Mar 18 '12 at 18:29
up vote 0 down vote

Why are you doing 

echo "ar"

instead of 

echo $ar

Also are you looking for permutation or combination? Here is a site with very nice algorithms for both. The implementation is in java but it's very clear. so converting to php won't be difficult: http://geekviewpoint.com/Numbers_functions_in_java/

share|improve this answer
up vote 0 down vote

If you want a pure clean recursive way use this:

function comb($item, $n) {
    return comb_rec($item, array(), $n);
}
function comb_rec($items, $c, $n) {
    if (count($c) == $n) {
        return array($c);
    }else{
        if (count($items) == 0) {
            return $items;
        }else{
            $list = $items;
            $head = array_shift($list);
            $tail = $list;
            $current = $c;
            array_push($current,$head);
            return array_merge(comb_rec($tail, $current, $n),comb_rec($tail, $c, $n));
        }
    }

}

$team = array("A","B","C","D");
$all = comb($team,2);
print_r($all);
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.