1

How to code up a [find-array-in-array] function?

Psuedo-code

Haystack: 

array(0=a, 1=b, 2=a, 3=b, 4=c, 5=c, 6=a, 7=b, 8=d, 9=c, 10=a, 11=b, 12=a, 13=b, 14=c);

Needle: 

array(a, b, c);

Return:

array ( array (2, 3, 4), array(12, 13, 14) )

Desired: The Keys from Haystack that match Needle. The above should give 2 matches:

  1. match = Haystack 2-4
  2. match = Haystack 12-14

It should not find "a b", "a b d" nor "c a b" etc., only instances of each value in Needle - in the specified order.

I'd like to make it a function so I can run it repeatedly (I have lots of these patterns).

I've tried doing this with nested foreachs, and driven myself nuts with counters etc. I get to a certain point, and am unable to separate matches from non-matches. (Surprised there isn't a built in function? in_array and array_intersect seem to be for individual values only, not collections?)

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

$CountH = count($haystack); echo $CountH."<br/>";
$CountN = count($needle); echo $CountN."<br/>";
$matches ='';
foreach ($haystack as $key1=>$haystackval){
    foreach ($needle as $key2=>$needleval) {
        $fail = '0';
        //if (in_array($needleval, $haystack)) {
        if ($key2[$needleval] === $haystackval && $fail === '0') {
            echo "Got needleval - ".$needleval ."<br/>";
        } 
        else { $fail='1';
        }
    } 
}
Improve this question
7
  • Is each element of the haystack a single character? Commented Jun 5, 2013 at 15:17
  • This is a little too specific to be a built in function. Can you show us some code you've tried to write yourself? Otherwise this is just a case of you asking for code, which isn't really what SO is for Commented Jun 5, 2013 at 15:20
  • 1
    ah, a beautiful example of a finite state automata. Commented Jun 5, 2013 at 15:22
  • @Pudge601 - I'll update for you. Commented Jun 5, 2013 at 15:30
  • @Jack - No, it may range from single chars to 20 chars ... thus you could see "a bbbbbbbbb ccccc dddddddddddddddddddd" Commented Jun 5, 2013 at 15:34

2 Answers 2

Reset to default
3

My attempt at creating this function;

function find_array_in_array($needle, $haystack) {
    $keys = array_keys($haystack, $needle[0]);
    $out = array();
    foreach ($keys as $key) {
        $add = true;
        $result = array();
        foreach ($needle as $i => $value) {
            if (!(isset($haystack[$key + $i]) && $haystack[$key + $i] == $value)) {
                $add = false;
                break;
            }
            $result[] = $key + $i;
        }
        if ($add == true) { 
            $out[] = $result;
        }
    }
    return $out;
}

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

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

print_r(find_array_in_array($needle, $haystack));

Outputs;

Array
(
    [0] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 4
        )

    [1] => Array
        (
            [0] => 12
            [1] => 13
            [2] => 14
        )

)
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thank you - that appears to work ... and I think I can follow the logic# (The code looks simple - yet for the life of me, I couldn't figure breaks etc. - again, thank you!)
No problem =] Jack's answer is, admittedly, quite satisfyingly concise compared to mine, but the advantage of this one is that the array values can be of any type, such as an object etc.
Well - I'm not 100% sure, but I think Jacks is ever so slightly faster ... but both are great - thank you both Pudge601 & Jack
Selected as answer due to flexibility
@Pudge601 you are genius!
3

If the haystack consists of letters, you can do this in the string domain:

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

preg_match_all('/abc/', $haystack, $matches, PREG_OFFSET_CAPTURE);

print_r(array_map(function($item) {
  return range($item[1], $item[1] + strlen($item[0]) - 1);
}, $matches[0]));

Output:

Array
(
    [0] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 4
        )

    [1] => Array
        (
            [0] => 12
            [1] => 13
            [2] => 14
        )

)

With potentially multiple characters inside the haystack, you need to resort to this:

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

// cache array sizes
$haystack_len = count($haystack);
$needle_len = count($needle);

// shortlist the possible starting keys
$possible_keys = array_keys($haystack, $needle[0], true);

$results = array();

foreach ($possible_keys as $index) {
    // start searching
    $i = $index; $j = 0;
    while ($i < $haystack_len && $j < $needle_len) {
        if ($haystack[$i] !== $needle[$j]) {
            continue 2; // no match
        }
        ++$i; ++$j;
    }
    // match
    $results[] = range($index, $index + $needle_len - 1);
}

print_r($results);
Improve this answer

7 Comments

this works, but i really hope for a more flexible solution, one where the haystack isn't made of single letters but possibly strings of letters.
@STTLCU You're not OP though :)
@Jack - I see that works ... I will test it with some other values (as it may contain more than singles) :: Thank you :D
@theclueless1 I've updated my answer to include more than one character.
@Jack - Thank you again! I'm printing out the resurlts of match - Array ( [0] => Array ( [0] => Array ( [0] => a b c [1] => 4 ) [1] => Array ( [0] => a b c [1] => 24 ) ) ) ... I like seeing the searched for string (nice touch), but the numbers appear doubled?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.