Слияние массива в рекурсивной функции с использованием php? - PullRequest
Новая
       36

Слияние массива в рекурсивной функции с использованием php?

2 голосов
/ 18 марта 2012

Через неделю поиск и преобразование многих алгоритмов с другого языка в php для создания массива, содержащего «комбинацию k из n».Я застрял.Помогите мне, пожалуйста.

Это мой код (с использованием 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);

Рекурсивный алгоритм выше действительно смущает меня.Приведенный выше код успешно сформировал комбинацию, но я не могу объединить их в один массив из-за его рекурсивных характеристик.Я просто хочу сделать массив, содержащий результат комбинации 2 из 4 элементов.Вот так (см. Ниже) 

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

Я знаю, что все еще далек от ответа.Но, пожалуйста, ведите меня, чтобы достичь этого ответа.Возможно, вы знаете другую технику, это не имеет значения.Если ваш код работает, я буду его использовать.Неважно, какую технику вы использовали.Любые идеи будут с благодарностью, спасибо ..!

Ответы [ 6 ]

3 голосов
/ 18 марта 2012

(я думаю) более простая рекурсивная реализация: 

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


?>

, которая возвращает 

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
        )

)

и будет работать для любого массива размера и любого $k.

Вы ищете искомое (лексикографическое) перечисление k-подмножеств , где $k в данном конкретном случае равно 2.

Объяснение

Идея очень проста.Предположим, у нас есть (например) набор {A,B,C,D}.Мы хотим начать со всех наборов с A in, и поэтому мы рассматриваем подмножества размера 1 меньше, начиная с {B,C,D}, и добавляем к ним A, получая 

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

, а затем мы рассматриваем все подмножества размера 2без A в 

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

, а затем мы просто объединяем два.Надеюсь, легко увидеть, как в общем случае это дает хорошую рекурсивную стратегию для построения k-подмножеств множества (вместо просто k = 2).

Ссылка

Фантастическая ссылка на подобные вещи - Том 4, Фасилика 3 Кнута «Искусство компьютерного программирования» .

1 голос
/ 18 марта 2012

Не совсем уверен в необходимости запуска, n и k, но это должно дать вам ожидаемый результат.Если вы предоставите более подробную информацию о том, зачем нужны эти счетчики, мы можем дать вам более подробный ответ. 

<code>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 '
';}
1 голос
/ 18 марта 2012 
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);

даст вам: 

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
    )

)

1 голос
/ 18 марта 2012

Это должно помочь достичь массива, который вы описали выше: 

<?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));
?>
0 голосов
/ 18 марта 2012

Если вы хотите чисто чистый рекурсивный способ, используйте это: 

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);
0 голосов
/ 18 марта 2012

Почему вы делаете 

echo "ar"

вместо 

echo $ar

Также вы ищете перестановку или комбинацию?Вот сайт с очень хорошими алгоритмами для обоих.Реализация в Java, но это очень ясно.поэтому преобразование в php не составит труда: http://geekviewpoint.com/Numbers_functions_in_java/

...