seeking for the good pattern in preg_match

Hi,
Suppose I have one string $str = "ABCCD"

Here are some examples for which I want to return TRUE:
"ABCD"
"BACC"
"DCA"

and others for which I want to return FALSE:
"ABCDE"
"BACDD"
"ABB"

You see the pattern? You have to choose letters from the string only,
the order has no importance but you must not have more letters of one
kind than found in the string $str.

What would be the correct preg_match pattern for this problem?
Any hint appreciated,
Patrick

geantbrun wrote:

> What would be the correct preg_match pattern for this problem?

I don't think there would be one in general. You need to do something
like this:

$str = 'ABCCD';
$testing = 'DCA';
$pass = TRUE;
$cs = ''; // change to 'i' to make it case-insensitive
while (strlen($testing))
{
$char = substr($testing, 0, 1);
$testing = substr($testing, 1);

if (!preg_match("/$c/$cs", $str))
{
$pass = FALSE;
break;
}

$str = preg_replace("/([^$c]$)c/$cs", '\1', $str);
}
echo $pass ? 'passed' : 'failed';


--
Toby A Inkster BSc (Hons) ARCS
[Geek of HTML/SQL/Perl/PHP/Python/Apache/Linux]
[OS: Linux 2.6.17.14-mm-desktop-9mdvsmp, up 5 days, 9:40.]

Sharing Music with Apple iTunes
http://tobyinkster.co.uk/blog/2007/1...tunes-sharing/

Thank you for the answer Tony.
First did you mean $char instead of $c in your code? (3 occurences?)
I would like to better understand your algorithm because it does not
seem to work with $testing="DDCA" (it passed but it's supposed to
fail). I understand that you test first if each character is in $str
but what's the point of your preg_replace at the end?
Cheers,
Patrick

geantbrun wants to know when a test string is a subsequence of a permutation of another given string:

$str = "ABCCD";
$aTest = array("ABCD", "BACC", "DCA", "DDCA",
"ABCDE", "BACDD", "ABB");

print "For base string '$str':<br><br>\n";
foreach ($aTest as $test)
print (subPerm ($test, $str) ? "Passed" : "Failed")
. " on '$test'<br>\n";

function subPerm ($test, $str) {
/* returns true iff $sub is a subsequence of a permutation of $subject */
$aStr = count_chars($str, 1);
foreach (count_chars($test, 1) as $ord=>$count)
if (!array_key_exists($ord, $aStr) || $aStr[$ord] < $count)
return false;
return true; }


Csaba Gabor from Vienna

geantbrun wrote:

> First did you mean $char instead of $c in your code? (3 occurences?)

Yep -- this is what happens when you post code without testing it! ;-)

Or the other way around, I meant '$c' when I wrote '$char'. Either way,
they should both be the same!

> I would like to better understand your algorithm because it does not seem
> to work with $testing="DDCA" (it passed but it's supposed to fail). I
> understand that you test first if each character is in $str but what's
> the point of your preg_replace at the end?

The preg_replace at the end if broken. Should be:

$str = preg_replace("/([^$c])$c/$cs", '\1', $str);

(I had the ')$' as '$)' instead, which is wrong!)

What this does, is removes the first occurrence of $c from $str.

So basically, as a whole, the algorithm does this:

For each character in $testing:

Check to see if it exists in $str.
If not, then fails the test.
Otherwise, remove that character from $str and continue.

--
Toby A Inkster BSc (Hons) ARCS
[Geek of HTML/SQL/Perl/PHP/Python/Apache/Linux]
[OS: Linux 2.6.17.14-mm-desktop-9mdvsmp, up 5 days, 21:50.]

Sharing Music with Apple iTunes
http://tobyinkster.co.uk/blog/2007/1...tunes-sharing/

Thanks Tony,
If I understand well, the preg_replace line should be:
$str = preg_replace("/$c/$cs", '\1', $str, 1 );

I did 2 replacements:
1- I put a one for the count parameter (you must replace only one
letter from $str)
2- I removed the ([^$c]) from the pattern because the character can be
at first position.

At first glance, it seems to work. I did't have the time to look at
the code from Csaba right now.
Thank you again folks!
Patrick

On Dec 12, 10:31 pm, geantbrun <agin.patr...@gmail.com> wrote:
> Hi,
> Suppose I have one string $str = "ABCCD"
>
> Here are some examples for which I want to return TRUE:
> "ABCD"
> "BACC"
> "DCA"
>
> and others for which I want to return FALSE:
> "ABCDE"
> "BACDD"
> "ABB"
>
> You see the pattern? You have to choose letters from the string only,
> the order has no importance but you must not have more letters of one
> kind than found in the string $str.
>
> What would be the correct preg_match pattern for this problem?
> Any hint appreciated,
> Patrick

Hi

I'd suggest

function test($test, $pattern) {
$map = count_chars($pattern, 0);
foreach(count_chars($test, 1) as $chr => $cnt)
if($cnt > $map[$chr]) return false;
return true;
}

$pat = "ABCCD";
$test = "ABCCD BACC DCA ABCDE BACDD ABB XX" ;

foreach(preg_split("~\s+~", $test) as $t)
printf("%20s %d\n", $t, test($t, $pat));


--
gosha bine

[gui for google chart api http://www.tagarga.com/files/gcui]
[makrell http://www.tagarga.com/blok/makrell]