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

debugcn 发表于 Dev

艾伦

这是一个“最佳算法”问题。

我需要将混合值'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编写。

罗伯·贝利（Rob Baillie）

有两个技巧：

任何一系列检查相等性的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，但有可能使其中断。我将其留给读者作为练习...

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。