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

[laredotornado]

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

[Bob Stearns]

la***********@zipmail.com wrote:

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

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.

[Michael Cooney]

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:

la***********@zipmail.com wrote:

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

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.

[Bob Stearns]

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:

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:

>>la***********@zipmail.com wrote:

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

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.

[Toby Inkster]

la***********@zipmail.com wrote:

$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.

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

[Rik]

Toby Inkster wrote:

la***********@zipmail.com wrote:

>$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.

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

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