PHP - Comment trouver des groupes de valeurs dupliqués dans un tableau

Les tableaux de caractères ne sont que des chaînes. Regex est le roi de la correspondance des motifs de ficelles. Ajouter la récursion et la solution est assez élégante, même avec la conversion de va-et-vient des tableaux de caractères:

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('/^(.+)+(.*?)$/',$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)));
}

Vous pouvez tester ici : https://eval.in/507818 et https://eval.in/507815

Si c et d peuvent être regroupés, c'est mon code:

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

le résultat Final est:

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)

le code suivant retournera le résultat attendu, en trouvant les portions les plus longues avec des valeurs répétées:

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;
}

Ce sera en adéquation avec vos exemples:

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

ou {['x'], ['x']}, ["y"], {['x', 'b'], ['x', 'b']}, ['a']

la partie difficile est plus sur des exemples comme:

{['un', 'un', 'deux'], ['un', 'une', 'deux']}

Ou le plus difficile choix à faire:

un, deux, un, deux, un, deux, un, deux

parce que nous pouvons le regrouper sous la forme:

[,], [,], [,], [,]

[un, deux, un, deux], [un, deux, un, deux]

où il n'est pas "évident". Mon algorithme ci-dessus considérera toujours la correspondance la plus longue, car c'est la plus facile la mise en œuvre doit tenir compte de toute combinaison.

EDIT: vous devriez aussi considérer les cas où la correspondance la plus longue est après une correspondance plus courte:

Exemple:

'un', 'deux', 'un', 'deux', 'trois', 'quatre', 'un', 'deux', 'trois', 'quatre'

si vous commencez de gauche à droite, vous pourriez vouloir grouper comme :

{['un', 'deux'], ['un', 'deux'],} 'trois', 'quatre', 'un', 'deux', 'trois', 'quatre'

quand vous pourriez grouper comme:

'un', 'deux', {['un', 'deux', 'trois', 'quatre'], ['un', 'deux', 'trois', 'quatre']}

Cette situation doit être résolue avec des appels récursifs pour obtenir la meilleure solution, mais ce ne sera plus temps d'exécution:

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

Définitions:

Modèle de base: séquence d'éléments qui se répètent à l'intérieur d'un motif. (IE. Pour [a,b,a,b,c], [a,b] est le modèle de base et [a,b,a,b] est le modèle.

nous voulons commencer à chercher la plus longue base de motif, suivie de la plus longue, et ainsi de suite. Il est important de comprendre que si nous trouvons un motif, nous n'avons pas besoin de vérifier pour le début d'un autre modèle avec une base de la même longueur.

Voici la preuve.

supposons que A est une base de modèle, et que nous avons rencontré le modèle AA. Supposons que B soit une autre base de motif, de même longueur, qui forme un motif commençant par A. soit Y les éléments qui se chevauchent. Si A=XY, alors AA=XYXY. Puisque B est de la même longueur, il doit être le cas que B=YX parce que pour compléter B Nous devons utiliser les éléments restants dans A. de plus, puisque B forme un modèle nous devons avoir BB, qui est YXYX. Depuis A commence avant B, Nous avons XYXYX=AAX = XBB. Si B se répète à nouveau, nous aurons XBBB=XYXYXYX=AAAX. Par conséquent, B ne peut pas répéter un temps supplémentaire sans répéter un temps supplémentaire. Par conséquent, nous n'avons pas besoin de vérifier les patrons plus longs à l'intérieur de ceux générés par A.

le schéma le plus long possible se compose de la moitié des éléments dans la liste entière parce que le schéma le plus simple peut se produire exactement deux fois. Ainsi, nous pouvons commencer à vérifier des modèles de la moitié de la longueur et de travailler notre chemin vers le bas à motifs de taille 2.

en supposant que nous recherchons le tableau de gauche à droite, si un motif est trouvé, nous n'avons qu'à chercher de chaque côté des motifs supplémentaires. A gauche, il n'y a pas de motifs avec des bases de la même longueur, ou ils auraient été découverts à l'avance. Ainsi, nous cherchons le côté gauche pour les motifs en utilisant la plus petite taille de base suivante. Les éléments à droite du modèle n'ont pas été recherchés donc nous continuons à chercher des modèles en utilisant une base de même taille.

La fonction pour ce faire est la suivante:

function get_patterns($arr, $len = null) {
    // The smallest pattern base length for which a pattern can be found
    $minlen = 2;

    // No pattern base length was specified
    if ($len === null) {
        // Use the longest pattern base length possible
        $maxlen = floor(count($arr) / 2);
        return get_patterns($arr, $maxlen);

    // Base length is too small to find any patterns
    } else if ($len < $minlen) {
        // Compile elements into lists consisting of one element

        $results = array();

        $num = 1;
        $elem = $arr[0];

        for ($i=1; $i < count($arr); $i++) {
            if ($elem === $arr[$i]) {
                $num++;
            } else {
                array_push($results, array(
                    'number' => $num,
                    'values' => array( $elem )
                ));

                $num = 1;
                $elem = $arr[$i];
            }
        }

        array_push($results, array(
            'number' => $num,
            'values' => array( $elem )
        ));

        return $results;
    }

    // Cycle through elements until there aren't enough elements to fit
    //  another repition.
    for ($i=0; $i < count($arr) - $len * 2 + 1; $i++) {
        // Number of times pattern base occurred
        $num_read = 1; // One means there is no pattern yet

        // Current pattern base we are attempting to match against
        $base = array_slice($arr, $i, $len);

        // Check for matches using segments of the same length for the elements
        //  following the current pattern base
        for ($j = $i + $len; $j < count($arr) - $len + 1; $j += $len) {
            // Elements being compared to pattern base
            $potential_match = array_slice($arr, $j, $len);

            // Match found
            if (has_same_elements($base, $potential_match)) {
                $num_read++;

            // NO match found
            } else {
                // Do not check again using currently selected elements
                break;
            }
        }

        // Patterns were encountered
        if ($num_read > 1) {
            // The total number of elements that make up the pattern
            $pattern_len = $num_read * $len;

            // The elements before the pattern
            $before = array_slice($arr, 0, $i);

            // The elements after the pattern
            $after = array_slice(
                $arr, $i + $pattern_len, count($arr) - $pattern_len - $i
            );

            $results = array_merge(
                // Patterns of a SMALLER length may exist beforehand
                count($before) > 0 ? get_patterns($before, $len-1) : array(),

                // Patterns that were found
                array(
                    array(
                        'number' => $num_read,
                        'values' => $base
                    )
                ),

                // Patterns of the SAME length may exist afterward
                count($after) > 0 ? get_patterns($after, $len) : array()
            );

            return $results;
        }
    }

    // No matches were encountered

    // Search for SMALLER patterns
    return get_patterns($arr, $len-1);
}

La fonction has_same_elements, qui a été utilisé pour vérifier si les tableaux de primitives touches sont identiques, est comme suit:

// Returns true if two arrays have the same elements.
//
// Precondition: Elements must be primitive data types (ie. int, string, etc)
function has_same_elements($a1, $a2) {
    // There are a different number of elements
    if (count($a1) != count($a2)) {
        return false;
    }

    for ($i=0; $i < count($a1); $i++) {
        if ($a1[$i] !== $a2[$i]) {
            return false;
        }
    }

    return true;
}

afin d'accélérer le code, il ya quelques choses que vous pourriez faire. Au lieu de trancher le tableau, vous pouvez fournir à la fonction les index de la position de début et de fin qui doivent être examinés, ainsi que le tableau. En outre, l'utilisation de Chaînes peut être lente de sorte que vous pouvez créez un tableau qui fait correspondre les chaînes de caractères aux nombres et vice versa. Ensuite, vous pouvez convertir le tableau de chaînes en tableau de nombres et l'utiliser à la place. Après avoir obtenu le résultat, vous pouvez convertir les tableaux de nombres en chaînes.

j'ai testé la fonction en utilisant le code suivant:

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

echo '<pre>';
foreach ($tests as $test) {
    echo '<div>';
    $arr = explode(',',$test);
    echo "$test<br /><br />";
    pretty_print(get_patterns($arr));
    echo '</div><br />';
}
echo '</pre>';

La fonction que j'ai utilisé pour imprimer la sortie, pretty_print comme suit:

function pretty_print($results) {
    foreach ($results as $result) {
        $a = "array('" . implode("','", $result['values']) . "')";
        echo "array('number' => ${result['number']}, 'values' => $a)<br />";
    }
}

La sortie de l'épreuve de code est comme suit:

a,b,c,d

array('number' => 1, 'values' => array('a'))
array('number' => 1, 'values' => array('b'))
array('number' => 1, 'values' => array('c'))
array('number' => 1, 'values' => array('d'))

a

array('number' => 1, 'values' => array('a'))

a,a,a,a

array('number' => 2, 'values' => array('a','a'))

a,a,a,a,a

array('number' => 2, 'values' => array('a','a'))
array('number' => 1, 'values' => array('a'))

a,a,a,a,a,a

array('number' => 2, 'values' => array('a','a','a'))

b,a,a,a,a,c

array('number' => 1, 'values' => array('b'))
array('number' => 2, 'values' => array('a','a'))
array('number' => 1, 'values' => array('c'))

b,b,a,a,a,a,c,c

array('number' => 2, 'values' => array('b'))
array('number' => 2, 'values' => array('a','a'))
array('number' => 2, 'values' => array('c'))

b,b,a,a,d,a,a,c,c

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

a,b,c,d,a,b,c,d,c,d

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

x,x,y,x,b,x,b,a

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

OK, voici mon point de vue, le code ci-dessous divise le tableau original en plus longs morceaux adjacents qui ne se chevauchent pas.

donc dans cette situation

'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'd' 
[                 ] [                 ] [ ]  [  ]  <-- use 2 long groups
[      ] [        ] [      ]  [       ] [ ]  [  ]  <-- and not 4 short

il préférera 2 groupes de 4 courts groupes.

mise à jour: également testé avec des exemples d'une autre réponse, fonctionne pour ces cas aussi:

one, two, one, two, one, two, one, two
[one two one two], [one two one two]

'one' 'two' 'one' 'two' 'three' 'four' 'one' 'two' 'three' 'four'    
['one'] ['two'] ['one' 'two' 'three' 'four'] ['one' 'two' 'three' 'four']

voici le code et les tests:

<?php

/*
 * Splits an $array into chunks of $chunk_size.
 * Returns number of repeats, start index and chunk which has
 * max number of ajacent repeats.
 */
function getRepeatCount($array, $chunk_size) {
    $parts = array_chunk($array, $chunk_size);
    $maxRepeats = 1;
    $maxIdx = 0;
    $repeats = 1;
    $len = count($parts);
    for ($i = 0; $i < $len-1; $i++) {
        if ($parts[$i] === $parts[$i+1]) {
            $repeats += 1;
            if ($repeats > $maxRepeats) {
                $maxRepeats = $repeats;
                $maxIdx = $i - ($repeats-2);
            }
        } else {
            $repeats = 1;
        }
    }
    return array($maxRepeats, $maxIdx*$chunk_size, $parts[$maxIdx]);
}

/*
 * Finds longest pattern in the $array.
 * Returns number of repeats, start index and pattern itself.
 */
function findLongestPattern($array) {
    $len = count($array);
    for ($window = floor($len/2); $window >= 1; $window--) {
      $num_chunks = ceil($len/$window);
      for ($i = 0; $i < $num_chunks; $i++) {
        list($repeats, $idx, $pattern) = getRepeatCount(
          array_slice($array, $i), $window
        );
        if ($repeats > 1) {
            return array($repeats, $idx+$i, $pattern);
        }
      }
    }
    return array(1, 0, [$array[0]]);
}

/*
 * Splits $array into longest adjacent non-overlapping parts.
 */
function splitToPatterns($array) {
    if (count($array) < 1) {
        return $array;
    }
    list($repeats, $start, $pattern) = findLongestPattern($array);
    $end = $start + count($pattern) * $repeats;
    return array_merge(
            splitToPatterns(array_slice($array, 0, $start)),
            array(
                array('number'=>$repeats, 'values' => $pattern)
            ),
            splitToPatterns(array_slice($array, $end))
    );
}

Tests:

function isEquals($expected, $actual) {
    $exp_str = json_encode($expected);
    $act_str = json_encode($actual);
    $equals = $exp_str === $act_str;
    if (!$equals) {
        echo 'Equals check failed'.PHP_EOL;
        echo 'expected: '.$exp_str.PHP_EOL;
        echo 'actual  : '.$act_str.PHP_EOL;
    }
    return $equals;
}

assert(isEquals(
    array(1, 0, ['a']), getRepeatCount(['a','b','c'], 1)
));
assert(isEquals(
    array(1, 0, ['a']), getRepeatCount(['a','b','a','b','c'], 1)
));
assert(isEquals(
    array(2, 0, ['a','b']), getRepeatCount(['a','b','a','b','c'], 2)
));
assert(isEquals(
    array(1, 0, ['a','b','a']), getRepeatCount(['a','b','a','b','c'], 3)
));
assert(isEquals(
    array(3, 0, ['a','b']), getRepeatCount(['a','b','a','b','a','b','a'], 2)
));
assert(isEquals(
    array(2, 2, ['a','c']), getRepeatCount(['x','c','a','c','a','c'], 2)
));
assert(isEquals(
    array(1, 0, ['x','c','a']), getRepeatCount(['x','c','a','c','a','c'], 3)
));
assert(isEquals(
    array(2, 0, ['a','b','c','d']),
    getRepeatCount(['a','b','c','d','a','b','c','d','c','d'],4)
));

assert(isEquals(
    array(2, 2, ['a','c']), findLongestPattern(['x','c','a','c','a','c'])
));
assert(isEquals(
    array(1, 0, ['a']), findLongestPattern(['a','b','c'])
));
assert(isEquals(
    array(2, 2, ['c','a']),
    findLongestPattern(['a','b','c','a','c','a'])
));
assert(isEquals(
    array(2, 0, ['a','b','c','d']),
    findLongestPattern(['a','b','c','d','a','b','c','d','c','d'])
));


// Find longest adjacent non-overlapping patterns
assert(isEquals(
    array(
        array('number'=>1, 'values'=>array('a')),
        array('number'=>1, 'values'=>array('b')),
        array('number'=>1, 'values'=>array('c')),
    ),
    splitToPatterns(['a','b','c'])
));
assert(isEquals(
    array(
        array('number'=>1, 'values'=>array('a')),
        array('number'=>1, 'values'=>array('b')),
        array('number'=>2, 'values'=>array('c','a')),
    ),
    splitToPatterns(['a','b','c','a','c','a'])
));
assert(isEquals(
    array(
        array('number'=>2, 'values'=>array('a','b','c','d')),
        array('number'=>1, 'values'=>array('c')),
        array('number'=>1, 'values'=>array('d')),
    ),
    splitToPatterns(['a','b','c','d','a','b','c','d','c','d'])
));
/*     'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'd', */
/*     [                 ] [                 ] [ ]  [  ] */
/* NOT [      ] [        ] [      ]  [       ] [ ]  [  ] */
assert(isEquals(
    array(
        array('number'=>2, 'values'=>array('a','b','a','b')),
        array('number'=>1, 'values'=>array('c')),
        array('number'=>1, 'values'=>array('d')),
    ),
    splitToPatterns(['a','b','a','b','a','b','a','b','c','d'])
));

/*     'x', 'x', 'y', 'x', 'b', 'x', 'b', 'a' */
/* //  [  ] [  ] [ ]  [       ] [      ]  [ ] */
assert(isEquals(
    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')),
    ),
    splitToPatterns(['x','x','y','x','b','x','b','a'])
));
// one, two, one, two, one, two, one, two
// [                ] [                 ]
assert(isEquals(
    array(
        array('number'=>2, 'values'=>array('one', 'two', 'one', 'two')),
    ),
    splitToPatterns(['one', 'two', 'one', 'two', 'one', 'two', 'one', 'two'])
));
// 'one', 'two', 'one', 'two', 'three', 'four', 'one', 'two', 'three', 'four'
// [   ]  [   ]  [                           ]  [                           ]
assert(isEquals(
    array(
        array('number'=>1, 'values'=>array('one')),
        array('number'=>1, 'values'=>array('two')),
        array('number'=>2, 'values'=>array('one','two','three','four')),
    ),
    splitToPatterns(['one', 'two', 'one', 'two', 'three', 'four', 'one', 'two', 'three','four'])
));

/*     'a', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', */
/*     [  ] [                 ] [                 ] [ ]  */
assert(isEquals(
    array(
        array('number'=>1, 'values'=>array('a')),
        array('number'=>2, 'values'=>array('a','b','a','b')),
        array('number'=>1, 'values'=>array('c')),
    ),
    splitToPatterns(['a','a','b','a','b','a','b','a','b','c'])
));

/* 'a', 'b', 'a', 'b', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b' */
// [      ]  [      ]  [ ]  [ ]  [      ] [       ]  [      ]
assert(isEquals(
    array(
        array('number'=>2, 'values'=>array('a', 'b')),
        array('number'=>1, 'values'=>array('c')),
        array('number'=>1, 'values'=>array('d')),
        array('number'=>3, 'values'=>array('a','b')),
    ),
    splitToPatterns(['a', 'b', 'a', 'b', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b'])
));
/* 'a', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', */
/* [  ] [  ] [  ] [                 ] [                 ] [ ]  */
assert(isEquals(
    array(
        array('number'=>1, 'values'=>array('a')),
        array('number'=>2, 'values'=>array('a','b','a','b')),
        array('number'=>1, 'values'=>array('c')),
    ),
    splitToPatterns(['a','a','b','a','b','a','b','a','b','c'])
));

j'ai commencé avec cela maintenant mais à la fin mon cerveau brûle et je ne sais pas où commencer à comparer les tableaux... Profitez-en!

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

$arrayCount = count($array);

$res = array();
for($i = 0; $i < $arrayCount; $i++) {
    for($j = 1; $j < $arrayCount; $j++) {
        $res[$i][] = array_slice($array, $i, $j);
    }
}

//echo '<pre>';
//var_dump($res);
//echo '</pre>';
//
//die;


$resCount = count($res);
$oneResCount = count($res[0]);

tout d'abord créer une fonction qui trouvera les correspondances de groupe possibles dans le tableau pour un tableau de groupe donné, à partir d'un index spécifique dans le tableau et retournera le nombre de correspondances trouvées.

function findGroupMatch($group, $array, $startFrom) {
    $match = 0;
    while($group == array_slice($array, $startFrom, count($group))) {
        $match++;
        $startFrom += count($group);
    }
    return $match;
}

maintenant, nous devons itérer chaque item pour trouver des groupes possibles et ensuite l'Envoyer à findGroupMatch() fonction pour vérifier si un match pour le groupe existe dans les prochains articles. L'astuce pour trouver un possible groupe est de trouver un élément qui correspond à l'un des éléments précédents. Si oui, nous trouvons un groupe possible prenant tous les articles précédents à partir de l'article apparié. Sinon, nous venons d'augmenter la liste des inégalée éléments et à la fin nous entrons tous inégalée éléments comme unique élément de groupes. (Dans l'exemple donné, nous avons a, b, c, d, a.... Lorsque nous découvrirons des 2e a dans le tableau, il correspond à la précédente a, Donc, nous considérons a, b, c, d groupe possible et l'envoyer à la fonction findGroupMatch(), pour vérifier combien de groupes nous pouvons trouver dans les articles suivants.)

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

$unMatchedItems = array();
$totalCount = count($array);
$groupsArray = array();

for($i=0; $i < $totalCount; $i++) {
    $item = $array[$i];

    if(in_array($item, $unMatchedItems)) {
        $matched_keys = array_keys($unMatchedItems, $item);
        foreach($matched_keys as $key) {
            $possibleGroup = array_slice($unMatchedItems, $key);

            $matches = findGroupMatch($possibleGroup, $array, $i);

            if ($matches) {
                //Insert the items before group as single item group
                if ($key > 0) {
                    for ($j = 0; $j < $key; $j++) {
                        $groupsArray[] = array('number' => 1, 'values' => array($unMatchedItems[$j]));
                    }
                }
                //Insert the group array
                $groupsArray[] = array('number' => $matches + 1, 'values' => $possibleGroup); //number includes initial group also so $matches + 1
                $i += (count($possibleGroup) * $matches) - 1; //skip the matched items from next iteration
                //Empty the unmatched array to start with a new group search
                $unMatchedItems = array();
                break;
            }
        }
        //If there was no matches, add the item to the unMatched group
        if(!$matches) $unMatchedItems[] = $item;
    } else {
        $unMatchedItems[] = $item;
    }

}

//Insert the remaining items as single item group
for($k=0; $k<count($unMatchedItems); $k++) {
    $groupsArray[] = array('number' => 1, 'values' => array($unMatchedItems[$k]));
}

print_r($groupsArray);

le Le résultat sera comme ceci: (à Vérifier PHP Fiddle pour les tests et aussi https://eval.in/507333 pour ton autre test d'entrée.)

Array
(
    [0] => Array
    (
        [number] => 2
        [values] => Array
        (
            [0] => a
            [1] => b
            [2] => c
            [3] => d
        )

    )

    [1] => Array
    (
        [number] => 1
        [values] => Array
        (
            [0] => c
        )

    )

    [2] => Array
    (
        [number] => 1
        [values] => Array
        (
            [0] => d
        )

    )

)

premier l'exemple est super facile avec la récursion. deuxième exemple... pas si facile.

l'exemple ci-dessous ne fonctionne que pour le premier exemple en supposant qu'aucun modèle ne devrait jamais contenir deux du même élément. Cela permettra également de gérer tous les motifs d'éléments individuels à la fin du tableau original et de garder l'ordre du motif (de la première occurrence de motif).

function find_pattern($input, &$result) {
    $values = []; // currently processed elements
    $pattern = ''; // the current element pattern
    $dupe_found = false; // did we find a duplicate element?

    // search the values for the first that matches a previous value
    while ($next = array_shift($input)) {
        // check if the element was already found
        if (in_array($next, $values)) {
            // re-add the value back into the input, since the next call needs it
            array_unshift($input, $next);

            // add the resulting pattern
            add_pattern($pattern, $values, $result);

            // find the next pattern with a recursive call
            find_pattern($input, $result);

            // a duplicate element was found!
            $dupe_found = true;

            // the rest of the values are handled by recursion, break the while loop
            break;
        } else {
            // not already found, so store the element and keep going
            $values[] = $next;

            // use the element to produce a key for the result set
            $pattern .= $next;
        }
    }

    // if no duplicate was found, then each value should be an individual pattern
    if (!$dupe_found) {
        foreach ($values as $value) {
            add_pattern($value, [$value], $result);
        }
    }
}

function add_pattern($pattern, $values, &$result) {
    // increment the pattern count
    $result[$pattern]['number'] = isset($result[$pattern]['number']) ?
        result[$pattern]['number']+1 : 1;

    // add the current pattern to the result, if not already done
    if (!isset($result[$pattern]['values'])) {
        $result[$pattern]['values'] = $values;
    }
}

Et un exemple d'utilisation:

$input = [
    'a', 'b', 'c', 'd',
    'a', 'b', 'c', 'd',
    'c', 'd'
];

$result = [];
find_pattern($input, $result);

echo "<pre>";
print_r($result);
echo "</pre>";

L'exemple sortie:

Array
(
    [abcd] => Array
    (
        [number] => 2
        [values] => Array
        (
            [0] => a
            [1] => b
            [2] => c
            [3] => d
        )
    )

    [c] => Array
    (
        [number] => 1
        [values] => Array
        (
            [0] => c
        )
    )

    [d] => Array
    (
        [number] => 1
        [values] => Array
        (
            [0] => d
        )
    )
)

Vous pourriez faire quelque chose comme ceci:

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

// Call this function to get your patterns
function patternMatching(array $array) {
    $patterns = array();
    $belongsToPattern = array_fill(0, count($array), false);

    // Find biggest patterns first
    for ($size = (int) (count($array) / 2); $size > 0; $size--) {

        // for each pattern: start at every possible point in the array
        for($start=0; $start <= count($array) - $size; $start++) {

            $p = findPattern($array, $start, $size);

            if($p != null) {

                /* Before we can save the pattern we need to check, if we've found a
                 * pattern that does not collide with patterns we've already found */
                $hasConflict = false;
                foreach($p["positions"] as $idx => $pos) {
                    $PatternConflicts = array_slice($belongsToPattern, $pos, $p["size"]);
                    $hasConflict = $hasConflict || in_array(true, $PatternConflicts);
                }

                if(!$hasConflict) {

                    /* Since we have found a pattern, we don't want to find more 
                     * patterns for these positions */
                    foreach($p["positions"] as $idx => $pos) {
                        $replace = array_fill($pos, $p["size"], true);
                        $belongsToPattern = array_replace($belongsToPattern, $replace);
                    }

                    $patterns[] = $p;
                    // or only return number and values:
                    // $patterns[] = [ "number" => $p["number"], "values" => $p["values"]];
                }
            }
        }
    }

    return $patterns;
}


function findPattern(array $haystack, $patternStart, $patternSize ) {

    $size = count($haystack);
    $patternCandidate = array_slice($haystack, $patternStart, $patternSize);

    $patternCount = 1;
    $patternPositions = [$patternStart];

    for($i = $patternStart + $patternSize; $i <= $size - $patternSize; $i++) {

        $patternCheck = array_slice($haystack, $i, $patternSize);

        $diff = array_diff($patternCandidate, $patternCheck);

        if(empty($diff)) {
            $patternCount++;
            $patternPositions[] = $i;
        }

    }

    if($patternCount > 1 || $patternSize <= 1) {

        return [
            "number"    => $patternCount,
            "values"    => $patternCandidate,

            // Additional information needed for filtering, sorting, etc.
            "positions" => $patternPositions,
            "size"      => $patternSize
        ];
    } else {
        return null;
    }

}

$patterns = patternMatching($array);

print "<pre>";
print_r($patterns);
print "</pre>";

?>

Le code peut être loin d'être optimale de la vitesse mais elle devrait faire ce que vous voulez faire pour n'importe quelle séquence de chaînes dans un tableau. patternMatching() renvoie les motifs ordonnés descendant dans la taille du motif et Ascendant Par première occurrence (vous pouvez utiliser ['positions'][0] comme critère de tri pour obtenir un ordre différent).

Cela devrait le faire:

<?php

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


// convert the array to a string
$string = '';
foreach ($array as $a) {
  $l = strlen($a)-1;
  $string .= ($l) ? str_replace('::',':',$a[0] . ':' . substr($a,1,$l-1) . ':' . $a[$l]) . '-' : $a . '-';
}

// find patterns
preg_match_all('/(?=((.+)(?:.*?)+))/s', $string, $matches, PREG_SET_ORDER);
foreach ($matches as $m) {
  $temp = str_replace('--','-',$m[2].'-');
  $patterns[] = ($temp[0]==='-') ? substr($temp,1) : $temp;
}

// remove empty values and duplicates
$patterns = array_keys(array_flip(array_filter($patterns)));

// sort patterns
foreach ($patterns as $p) {
  $sorted[$p] = strlen($p);
}
arsort($sorted);

// find double or more occurences
$stringClone = $string;
foreach ($sorted as $s=>$n) {
  $nA = substr_count($stringClone,':'.$s);
  $nZ = substr_count($stringClone,$s.':');
  $number = substr_count($stringClone,$s);
  $sub = explode('-',substr($stringClone,strpos($stringClone,$s),$n-1));
  $values = $sub;
  if($nA>0 || $nZ>0){
    $numberAdjusted = $number - $nA - $nZ;
    if($numberAdjusted > 1) {
      $temp = '';
      while($n--){
        $temp .= '#';
      }
      $position = strpos(str_replace(':'.$s,':'.$temp,str_replace($s.':',$temp.':',$string)),$s);
      $stringClone = str_replace(':'.$s,':'.$temp,$stringClone);
      $stringClone = str_replace($s.':',$temp.':',$stringClone);
      $result['p'.sprintf('%09d', $position)] = array('number'=>$numberAdjusted,'values'=>$values);
      $stringClone = str_replace($s,'',$stringClone);
      $stringClone = str_replace($temp,$s,$stringClone);
    }
  } else if($number>1){
    $position = strpos($string,$s);
    $result['p'.sprintf('%09d', $position)] = array('number'=>$number,'values'=>$values);
    $stringClone = str_replace($s,'',$stringClone);
  }
}

// add the remaining items
$remaining = array_flip(explode('-',substr($stringClone,0,-1)));
foreach ($remaining as $r=>$n) {
    $position = strpos($string,$r);
    $result['p'.sprintf('%09d', $position)] = array('number'=>1,'values'=>str_replace(':','',$r));
}

// sort results
ksort($result);
$result = array_values($result);

print_r($result);
?>

exemple de travail ici.