"Развернуть" строку

Question

У меня есть набор строк, каждая строка имеет переменное количество сегментов, разделенных трубами (|), например ::

$string = 'abc|b|ac';

Каждый сегмент с более чем одним символом должен быть расширен до всех возможных комбинаций с одним символом, для 3 сегментов прекрасно работает следующий «алгоритм»:

$result = array();
$string = explode('|', 'abc|b|ac');

foreach (str_split($string[0]) as $i)
{
    foreach (str_split($string[1]) as $j)
    {
        foreach (str_split($string[2]) as $k)
        {
            $result[] = implode('|', array($i, $j, $k)); // more...
        }
    }
}

print_r($result);

Выход:

$result = array('a|b|a', 'a|b|c', 'b|b|a', 'b|b|c', 'c|b|a', 'c|b|c');

Очевидно, что для более чем 3 сегментов код начинает очень запутываться, так как мне нужно добавлять (и проверять) все больше и больше внутренних циклов. Я попытался придумать динамическое решение, но я не могу понять, как создать правильную комбинацию для всех сегментов (индивидуально и в целом). Я также посмотрел на некоторый исходный код комбинаторики, но не могу объединить различные комбинации моих сегментов.

Я ценю, если кто-нибудь может указать мне правильное направление.

Answer 1

Рекурсия на помощь (может понадобиться немного подправить, чтобы охватить крайние случаи, но это работает):

function explodinator($str) {
    $segments = explode('|', $str);
    $pieces = array_map('str_split', $segments);

    return e_helper($pieces);
}

function e_helper($pieces) {

    if (count($pieces) == 1)
        return $pieces[0];

    $first = array_shift($pieces);
    $subs = e_helper($pieces);

    foreach($first as $char) {
        foreach ($subs as $sub) {
            $result[] = $char . '|' . $sub;
        }
    }

    return $result;
}

print_r(explodinator('abc|b|ac'));

Выходы:

Array
(
    [0] => a|b|a
    [1] => a|b|c
    [2] => b|b|a
    [3] => b|b|c
    [4] => c|b|a
    [5] => c|b|c
)

Как видно на ideone .

Answer 2

Это похоже на работу для рекурсивного программирования! :П Сначала я посмотрел на это и подумал, что это будет лайнер (и, вероятно, в Perl). Существуют и другие нерекурсивные способы (например, перечислить все комбинации индексов в сегменты, а затем перебрать циклы), но я думаю, что это более интересно и, вероятно, «лучше».

 $str = explode('|', 'abc|b|ac');
 $strlen = count( $str );
 $results = array();

 function splitAndForeach( $bchar , $oldindex, $tempthread) {
     global $strlen, $str, $results;
     $temp = $tempthread;
     $newindex = $oldindex + 1;

     if ( $bchar != '') { array_push($temp, $bchar ); }

     if ( $newindex <= $strlen ){
         print "starting foreach loop on string '".$str[$newindex-1]."' \n";

         foreach(str_split( $str[$newindex - 1] ) as $c) {
             print "Going into next depth ($newindex) of recursion on char $c \n";
             splitAndForeach( $c , $newindex, $temp);
         }

     } else {

        $found = implode('|', $temp);
        print "Array length (max recursion depth) reached, result: $found \n";

        array_push( $results, $found );
        $temp = $tempthread;
        $index = 0;
        print "***************** Reset index to 0 *****************\n\n";
     }
 }

 splitAndForeach('', 0, array() );
 print "your results: \n";
 print_r($results);

Answer 3

У вас может быть два массива: альтернативы и счетчик тока .

$alternatives = array(array('a', 'b', 'c'), array('b'), array('a', 'c'));
$counter = array(0, 0, 0);

Затем в цикле вы увеличиваете «последнюю цифру» счетчика, и еслиэто равно числу альтернатив для этой позиции, вы сбрасываете эту «цифру» в ноль и увеличиваете «цифру», оставленную ей.Это работает так же, как подсчет с десятичными числами.

Строка для каждого шага строится путем объединения $alternatives[$i][$counter[$i]] для каждой цифры.

Вы закончите, когда «первая цифра» станет слишком большойв качестве количества альтернатив для этой цифры.

Пример: для вышеуказанных переменных счетчик получит следующие значения в шагах:

0,0,0
0,0,1
1,0,0 (overflow in the last two digit)
1,0,1
2,0,0 (overflow in the last two digits)
2,0,1
3,0,0 (finished, since the first "digit" has only 3 alternatives)