If you're good with arrays and lists, this one's for you

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
Hi,

I'm using PHP 4.4.4.  Let's say I have two scalars, \$list1 and \$list2.
Both are comma separated lists of ordered, unsigned, unique integers.
An example would be

\$list1 = "2,26,345";
\$list2 = "3,4,26,35,525";

I am wondering if there is a short way of determining if all the
numbers in \$list1 occur in \$list2.

Grateful for any advice.  Thanks, - Dave

Re: If you're good with arrays and lists, this one's for you

If, as in your example, the two lists are sorted, it can be done in
O(n+m) time by doing  stepped compare. If they are unsorted, it can also
be done in O(n+m) time (with a much bigger constant factor) by making
the second list into the subscripts of an array, then checking for the
existence of the first list's elements in the new array.

Sample code (untested):

\$i1 = 0;
\$i2 = 0;
while(\$i1<count(\$list1) && \$i2<count(\$list2)) {
if(\$list2[\$i2]==\$list1[\$i1]) {
\$i1++;
\$i2++;
}
elseif(\$list2[\$i2]<\$list1[\$i1]) {
\$i2++;
}
else { /* this the failure case */ }
\$fail = TRUE;
break;
}
}

for(\$i2==0; \$i2<count(\$list2); \$i2++) {
\$test[\$list2[\$i2]] = TRUE;
}
for(\$i1==0; \$i1<count(\$list1); \$i1++) {
if(!array_key_exists(\$list1[\$i1],\$test) {
\$fail = TRUE;
break;
}
}

We use these techniques rather than the much easier to code in_array()
because the time for this technique in O(m*n) since \$list2 must be
searched completely for each element of \$list1.

Re: If you're good with arrays and lists, this one's for you

Or you could use array_diff:

<?php

\$list1 = "2,26,345";
\$list2 = "3,4,26,35,525";

\$alist1 = split(',', \$list1);
\$alist2 = split(',', \$list2);

if(count(array_diff(\$alist1, \$alist2)) == 0) {

echo "Yep. They're all in there.\n";

} else {

echo "Nope. Yer missing some.\n";
}

?>

Bob Stearns wrote:

Re: If you're good with arrays and lists, this one's for you

That is a shorter code, but we don't know what search logic is used. It
may devolve to the O(m*n) case, especially since it accommodates more
than one compare list.

Michael Cooney wrote:

Re: If you're good with arrays and lists, this one's for you

Fast or easy?

Easy:

\$arr1 = explode(',', \$list1);
\$arr2 = explode(',', \$list2);
\$allin = TRUE;
foreach (\$arr1 as \$n)
{
if (!in_array(\$n, \$arr2))
{
\$allin = FALSE;
break 1;
}
}
// \$allin is now TRUE iff every number in \$list1 is in \$list2.

Fast:

/***************************************************************
* We exploit the fact that \$list1 and \$list2 are sorted lists.
* This will speed things up, but will only be noticeable when
* dealing with lists of many hundreds of numbers.
***************************************************************/
\$arr1 = explode(',', \$list1);
\$arr2 = explode(',', \$list2);
\$allin = TRUE;
while (isset(\$arr1[0]))
{
\$n = (int)array_shift(\$arr1);
while ((int)\$arr2[0] < \$n)
array_shift(\$arr2);
if ((int)\$arr2[0]>\$n)
{
\$allin = FALSE;
break 1;
}
}
// \$allin is now TRUE iff every number in \$list1 is in \$list2.

--
Toby A Inkster BSc (Hons) ARCS
Contact Me  ~ http://tobyinkster.co.uk/contact

Re: If you're good with arrays and lists, this one's for you

Toby Inkster wrote:

Well, and now ths short code version (not more efficient (only if you
needed the difference)):

\$difference = array_diff(explode(',',\$list1),explode(',',\$list2));
if(count(\$difference)==0){
echo 'Every item in \$list1 is in \$list2.';
} else {
echo 'The following numbers are not present in \$list2: '.implode(',
',\$difference);
}
--
Rik Wasmus