PHP: Find An Array Sequence In An Array

6th March 2021 - 3 minutes read time

I was looking for a function that searched an array for another array, and after not finding one I decided to write it. What I was looking for was a function that took a smaller array and searched for that exact sequence of items in a larger array. As it happens, PHP does have a number of array search functions, but they didn't produce the correct result.

The array_search() function does accept an array as the needle to be searched for, but this does a multi-dimensional search instead. I also saw some techniques using array_intersect() or array_diff(), and although these functions were able to find one array inside another I was interested in the sequence. 

The implementation of the function contains a two loops, one for going through the haystack array and one for the needle array. If the number of matches found equals the number of items in the needle array then the function returns true.

Here is the sequence_in_array() function.

/**
 * Determines if an array is part of another array.
 *
 * @param array $needle
 *   The array to search for.
 * @param array $haystack
 *   The array to search in.
 *
 * @return bool
 *   True if the needle array is completely found in the haystack array.
 */
function sequence_in_array(array $needle, array $haystack) {
  $haystackCount = count($haystack);
  $needleCount = count($needle);

  if ($needleCount > $haystack) {
    throw new InvalidArgumentException('$needle array must be smaller than $haystack array.');
  }

  for ($i = 0; $i <= $haystackCount - $needleCount; $i++) {
    $matchCount = 0;
    for ($j = 0; $j < $needleCount; $j++) {
      if ($needle[$j] == $haystack[$i + $j]) {
        $matchCount++;
        if ($matchCount == $needleCount) {
          return TRUE;
        }
      }
    }
  }
  return FALSE;
}

In order to test this I set up a phpunit test class and used a dataProvider to test a few different arrays. This just calls the function repeatedly with different arrays and makes sure that it works correctly.

  /**
   * @dataProvider arrayData
   */
  public function testSequenceInArray($needle, $haystack, $expectedResult)
  {
    $result = sequence_in_array($needle, $haystack);
    $this->assertEquals($expectedResult, $result);
  }

  public function arrayData() {
    return [
      [[], [], FALSE,],
      [[7,8,9], [1,2,3,4,5,6], FALSE,],
      [[1,3,4], [1,2,3,4,5,6], FALSE,],
      [[1,4,3], [1,2,3,4,5,6], FALSE,],
      [[1,2,3,9], [1,2,3,4,5,6], FALSE,],
      [[1], [1,2,3,4,5,6], TRUE,],
      [[1], [1], TRUE,],
      [[1,2,3], [1,2,3,4,5,6], TRUE,],
      [[3,4,5], [1,2,3,4,5,6], TRUE,],
      [[4,5,6], [1,2,3,4,5,6], TRUE,],
      [[1,2,3,4,5,6], [1,2,3,4,5,6], TRUE,],
      [[42,43,44,45,46,47], range(1, 100), TRUE,],
    ];
  }

As I wasn't able to find a function like this whilst searching I hope it comes in useful to someone.

Add new comment

The content of this field is kept private and will not be shown publicly.