current community

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite
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';
        }
    } 
}
share|improve this question
 
Is each element of the haystack a single character? –  Jack Jun 5 '13 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 –  Pudge601 Jun 5 '13 at 15:20
1  
ah, a beautiful example of a finite state automata. –  STT LCU Jun 5 '13 at 15:22
 
@Pudge601 - I'll update for you. –  theclueless1 Jun 5 '13 at 15:30
 
@Jack - No, it may range from single chars to 20 chars ... thus you could see "a bbbbbbbbb ccccc dddddddddddddddddddd" –  theclueless1 Jun 5 '13 at 15:34
show 2 more comments

2 Answers

up vote 2 down vote accepted

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
        )

)
share|improve this answer
 
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!) –  theclueless1 Jun 5 '13 at 15:53
 
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. –  Pudge601 Jun 5 '13 at 15:56
 
Well - I'm not 100% sure, but I think Jacks is ever so slightly faster ... but both are great - thank you both Pudge601 & Jack –  theclueless1 Jun 5 '13 at 16:34
 
Selected as answer due to flexibility –  theclueless1 Jun 10 '13 at 11:59
add comment
up vote 3 down vote

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);
share|improve this answer
 
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. –  STT LCU Jun 5 '13 at 15:30
 
@STTLCU You're not OP though :) –  Jack Jun 5 '13 at 15:32
 
@Jack - I see that works ... I will test it with some other values (as it may contain more than singles) :: Thank you :D –  theclueless1 Jun 5 '13 at 15:37
 
@theclueless1 I've updated my answer to include more than one character. –  Jack Jun 5 '13 at 15:39
1  
@theclueless1 Answer is updated. –  Jack Jun 5 '13 at 16:02
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.