arrays - 根据一组对数组有效的元素将列表拆分为数组的算法

这是一个“最优算法”问题。
我需要将一个混合值“a”、“b”和“c”的数组a分解成一个新的二维数组b，其中包含相同的值，但根据下面的规则在整个二维中拆分。
B记录以：

a: [a] || [a, a] || [a, b] || [a, b, b]
b: [b] || [b, b] || [b, a] || [b, b, a] || [b, b, b] || [b, b, b, b]
c: [c]

维持秩序
a中的每个值只能在b中使用一次
例如，我有一个数组a：

['a', 'c', 'b', 'b', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b']

我需要把它分成二维数组B：

[
 ['a'],
 ['c'],
 ['b', 'b', 'a'],
 ['a', 'a'],
 ['c'],
 ['b', 'b', 'b', 'b']
]

我编写的代码是很多嵌套的if/else语句。仅在while循环中包装“a”的代码：

while(i<arrA.length) {
 if(arrA[i] == a) {
  if(arrA[i+1] == a) {
   arrB[] = [arrA[i], arrA[i+1]]; //creates arrB[n]['a', 'a']
   i = i+2;
   continue;
  } elseif (arrA[i+1] == b) {
   if(arrA[i+2] == b) {
    arrB[] = [arrA[i], arrA[i+1], arrA[i+2]]; //creates arrB[n]['a', 'b', 'b']
    i = i+3;
    continue;
   } elseif (arrA[i+2] != b) {
    arrB[] = [arrA[i], arrA[i+1]]; //creates arrB[n]['a', 'b']
    i = i+2;
    continue;
   }
  } elseif (arrA[i+1] == c) {
   arrB[] = [arrA[i]]; //creates arrB[n]['a']
   i++;
   continue;
  }
 } elseif (...)
 i++;
}

“c”的代码较短，而“b”的代码较长。
在这种情况下，有没有更简洁的算法？如果这很重要，我用PHP编写。

最佳答案

有两个窍门：
检查相等性的任何一系列if语句都可以简化为对数组的检查。
你可以在每个循环中循环一个记住“上一个”的东西，并用它来行动。
即：
可以创建一个数组，其中包含所有可能的有效组合
然后，您可以循环遍历序列数组，并在每个步骤检查您所拥有的是否与可能性列表中的组合匹配。
如果你发现了不匹配的东西，你就假设你以前的样子匹配了，然后把它放到匹配的组合列表中。
它可能不是绝对最优的——但它肯定比您目前拥有的更具可扩展性。

<?php

    $aPossibleCombinations = array( 'a', 'aa', 'ab', 'abb', 'b', 'bb', 'ba', 'bba', 'bbb', 'bbbb', 'c' );

    $aThingsToMatch = array( 'a', 'c', 'b', 'b', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b' );

    $aMatchedThings = array();

    $sPreviousThing = '';
    $sCurrentThing  = '';

    foreach( $aThingsToMatch as $sSingleThing ) {

        $sCurrentThing .= $sSingleThing;

        if ( !in_array( $sCurrentThing, $aPossibleCombinations ) ) {
            $aMatchedThings[] = $sPreviousThing;
            $sCurrentThing = $sSingleThing;
        }

        $sPreviousThing = $sCurrentThing;
    }

    if ( in_array(  $sCurrentThing, $aPossibleCombinations ) ) {
        $aMatchedThings[] = $sPreviousThing;
        $sCurrentThing = '';
    }

    echo( "Matched Things: \r\n" );
    var_dump( $aMatchedThings );

    echo( "Remaining Things: \r\n" );
    var_dump( $sCurrentThing );

?>

我应该说我留下了一个虫子给你找它可以在当前的aThingsToMatch设置下工作，但也可以让它断开我把它留给读者作为练习。。。

关于arrays - 根据一组对数组有效的元素将列表拆分为数组的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20632216/