PHP - 如何在数组中找到重复的值分组

Question

我有一个字符串值数组,有时会形成重复值模式('a','b','c','d')

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

我想根据数组顺序找到重复的模式,并按相同的顺序对它们进行分组(以维护它).

$patterns = array(
    array('number' => 2, 'values' => array('a', 'b', 'c', 'd')),
    array('number' => 1, 'values' => array('c'))
    array('number' => 1, 'values' => array('d'))
);

请注意,[a,b],[b,c]和[c,d]本身不是模式,因为它们位于较大的[a,b,c,d]模式和最后的[c,d]集合中只出现一次因此它也不是一种模式 - 只是个别值'c'和'd'

另一个例子:

$array = array(
    'x', 'x', 'y', 'x', 'b', 'x', 'b', 'a'
  //[.......] [.] [[......]  [......]] [.]
);

哪个产生

$patterns = array(
    array('number' => 2, 'values' => array('x')),
    array('number' => 1, 'values' => array('y')),
    array('number' => 2, 'values' => array('x', 'b')),
    array('number' => 1, 'values' => array('a'))
);

我怎样才能做到这一点？

Answer 1

字符数组只是字符串.正则表达式是字符串模式匹配的王者.添加递归,解决方案非常优雅,即使在字符数组中来回转换:

function findPattern($str){
    $results = array();
    if(is_array($str)){
        $str = implode($str);
    }
    if(strlen($str) == 0){ //reached the end
        return $results;
    }
    if(preg_match_all('/^(.+)\1+(.*?)$/',$str,$matches)){ //pattern found
        $results[] = array('number' => (strlen($str) - strlen($matches[2][0])) / strlen($matches[1][0]), 'values' => str_split($matches[1][0]));
        return array_merge($results,findPattern($matches[2][0]));
    }
    //no pattern found
    $results[] = array('number' => 1, 'values' => array(substr($str, 0, 1)));
    return array_merge($results,findPattern(substr($str, 1)));
}

你可以在这里测试:https://eval.in/507818和https://eval.in/507815

Answer 2

如果c和d可以分组,这是我的代码:

<?php
$array = array(
    'a', 'b', 'c', 'd',
    'a', 'b', 'c', 'd',
    'c', 'd',
);

$res = array();

foreach ($array AS $value) {
    if (!isset($res[$value])) {
        $res[$value] = 0;
    }
    $res[$value]++;
}

foreach ($res AS $key => $value) {
    $fArray[$value][] = $key;
    for ($i = $value - 1; $i > 0; $i--) {
        $fArray[$i][] = $key;
    }
}

$res = array();
foreach($fArray AS $key => $value) {
    if (!isset($res[serialize($value)])) {
        $res[serialize($value)] = 0;
    }
    $res[serialize($value)]++;
}
$fArray = array();
foreach($res AS $key => $value) {
    $fArray[] = array('number' => $value, 'values' => unserialize($key));
}

echo '<pre>';
var_dump($fArray);
echo '</pre>';

最终结果是:

array (size=2)
  0 => 
    array (size=2)
      'number' => int 2
      'values' => 
        array (size=4)
          0 => string 'a' (length=1)
          1 => string 'b' (length=1)
          2 => string 'c' (length=1)
          3 => string 'd' (length=1)
  1 => 
    array (size=2)
      'number' => int 1
      'values' => 
        array (size=2)
          0 => string 'c' (length=1)
          1 => string 'd' (length=1)

Answer 3

以下代码将返回预期结果,找到具有重复值的最长部分:

function pepito($array) {
  $sz=count($array);
  $patterns=Array();
  for ($pos=0;$pos<$sz;$pos+=$len) {
    $nb=1;
    for ($len=floor($sz/2);$len>0;$len--) {
      while (array_slice($array, $pos, $len)==array_slice($array, $pos+$len, $len)) {
        $pos+=$len;
        $nb++;
      }
      if ($nb>1) break;
    }
    if (!$len) $len=1;
    $patterns[]=Array('number'=>$nb, 'values'=>array_slice($array, $pos, $len));
  }
  return $patterns;
}

这将与您的示例匹配:

{['a','b','c','d'],['a','b','c','d']},['c','d']

或{['x'],['x']},['y'],{['x','b'],['x','b']},['a']

困难的部分更多的是例如:

{['one','one','two'],['one','one','two']}

或者最困难的选择:

一,二,一,二,一,二,一,二

因为我们可以将这两种形式分组:

[一,二],[一,二],[一,二],[一,二]

[一,二,一,二],[一,二,一,二]

哪里没有"明显的"选择.我的上述算法将始终考虑最长匹配,因为这是考虑任何组合的最简单的实现.

编辑:您还应该考虑最长匹配在较短的匹配之后的情况:

例:

'一','二','一','二','三','四','一','二','三','四'

如果从左到右开始,您可能希望分组为:

{['one','two'],['one','two'],}'three','four','one','two','three','four'

当你可以分组时:

'one','two',{['one','two','three','four'],['one','two','three','four']}

这种情况必须通过递归调用来解决,以获得更好的解决方案,但这将导致更长的执行时间:

function pepito($array) {
  if (($sz=count($array))<1) return Array();
  $pos=0;
  $nb=1;
  for ($len=floor($sz/2);$len>0;$len--) {
    while (array_slice($array, $pos, $len)==array_slice($array, $pos+$len, $len)) {
      $pos+=$len;
      $nb++;
    }
    if ($nb>1) break;
  }

  if (!$len) $len=1;
  $rec1=pepito(array_slice($array, $pos+$len));
  $rec2=pepito(array_slice($array, 1));

  if (count($rec1)<count($rec2)+1) {
    return array_merge(Array(Array('number'=>$nb, 'values'=>array_slice($array, $pos, $len))), $rec1);
  }
  return array_merge(Array(Array('number'=>1, 'values'=>array_slice($array, 0, 1))), $rec2);
}