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

[laredotornado@zipmail.com]

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]

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

laredotornado@z ipmail.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($list 2)) {
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($list 2); $i2++) {
$test[$list2[$i2]] = TRUE;
}
for($i1==0; $i1<count($list 1); $i1++) {
if(!array_key_e xists($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]

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:

laredotornado@z ipmail.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($list 2)) {
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($list 2); $i2++) {
$test[$list2[$i2]] = TRUE;
}
for($i1==0; $i1<count($list 1); $i1++) {
if(!array_key_e xists($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]

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:

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

>>laredotornado @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<cou nt($list1) && $i2<count($list 2)) {
> 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($list 2); $i2++) {
> $test[$list2[$i2]] = TRUE;
>>}
>>for($i1==0; $i1<count($list 1); $i1++) {
> if(!array_key_e xists($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]

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

laredotornado@z ipmail.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_shif t($arr1);
while ((int)$arr2[0] < $n)
array_shift($ar r2);
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]

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

Toby Inkster wrote:

laredotornado@z ipmail.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_shif t($arr1);
while ((int)$arr2[0] < $n)
array_shift($ar r2);
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(expl ode(',',$list1) ,explode(',',$l ist2));
if(count($diffe rence)==0){
echo 'Every item in $list1 is in $list2.';
} else {
echo 'The following numbers are not present in $list2: '.implode(',
',$difference);
}
--
Rik Wasmus