sorting roman numbers

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

•  Subject
• Author
• Posted on
Hi,
An array contains elements of the form [upper-roman number][optional one
lower-alpha char], for example IVa, XIXb, LIX and LXIVc. Does anyone have a
function which can sort this array in a way a human would expect it to, with
the roman letters treated as their numerical values? I don't think this is a
especially problematic thing to do, but I don't want to re-invent the wheel.
Thanks
Ivo

Re: sorting roman numbers

Ivo wrote:

There is a roman numerals package in PEAR (I haven't tried it myself):
http://pear.php.net/package/Numbers_Roman

You can use the usort family of functions to sort an array with a
comparison callback, which can use that to get the numerical values.
http://www.php.net/manual/en/function.usort.php

-- brion vibber (brion @ pobox.com)

Re: sorting roman numbers

"Brion Vibber" wrote

Thanks but I need a solution without PEAR.   Roman numbers!   Has nobody
done that in PHP? I was absolutely amazed how little I could find about it
on the web.
Here is what I have written sofar, looks best with a fixed width font:

function toroman(\$n=1){
\$s='';
for(\$k=0;\$k<\$n;\$k++){
\$s=str_replace(

array('VIIII','IIII','IVI','IXI','XXXX','XLX','LXL','XCX','CCCC','CDC','DCD'
,'CMC'),
array(   'IX',  'IV',  'V',  'X',  'XL',  'L', 'XC',  'C',  'CD',  'D',
'CM',  'M'), \$s.'I');
}
return \$s;
}
function fromroman(\$s=''){
\$s=str_replace(
array(   'CM', 'M',   'CD',    'D',   'XC', 'C',  'XL',    'L',   'IX',
'X',  'IV',    'V'),
array('DCCCC',
'DD','CCCC','CCCCC','LXXXX','LL','XXXX','XXXXX','VIIII','VV','IIII','IIIII')
, \$s);
return strlen(\$s);
}
function romansort(\$a,\$b){
\$av=preg_replace('/([^IVXLCDM]+)?\$/','',\$a);
\$bv=preg_replace('/([^IVXLCDM]+)?\$/','',\$b);
if(\$av===\$bv){ return ( \$a < \$b ) ? -1 : 1; }
return ( fromroman(\$av) < fromroman(\$bv) ) ? -1 : 1;
}

// example array
\$myarray=array('C','XCVII','XVII','LVIf','LIb','LIXa','LIVa','IXa','DXb','DX
a','IXb','IXc','XIV');
usort(\$myarray,'romansort');

?>
<? foreach(\$myarray as \$n) {
preg_match('/^([IVXLCDM]+)([a-z]+)?\$/',\$n,\$rom);
?><tr><td><?=\$n;?></td><td><?=fromroman(\$rom[1]);?></td></tr>
<?}?>
</table>
<?

Function toroman() is not needed for the described purpose.
The convertor function accepts numbers from 1-3999, but does not recognize
certain numbers such as IC and IM. If anyone can improve, I 'd be
grateful...
--
Ivo

Re: sorting roman numbers

Ivo wrote:

Try this

========
<?php
function roman2int(\$roman, &\$last) {
\$symbols = array('I'=>1, 'V'=>5, 'X'=>10, 'L'=>50, 'C'=>100, 'D'=>500,
'M'=>1000);
\$values = array();
\$last = '';
for (\$i = 0; \$i < strlen(\$roman); ++\$i) {
if (!isset(\$symbols[\$roman])) {
\$last = \$roman;
break;
}
\$values[] = \$symbols[\$roman];

/* I'm sure the following code can be improved */
/* This was just a quick way I found to 'negativate' previous symbols */
\$j = \$i-1;
if (\$j >= 0) {
while (\$symbols[\$roman] > \$symbols[\$roman[\$j]]) {
\$values[\$j] = -\$symbols[\$roman];
--\$j;
if (\$j < 0) break;
}
}
}
return array_sum(\$values);
}

function romansort(\$lhs, \$rhs) {
\$lhlast = \$rhlast = '';
\$lhv = roman2int(\$lhs, \$lhlast);
\$rhv = roman2int(\$rhs, \$rhlast);
if (\$lhv == \$rhv) {
if (\$lhlast == \$rhlast) return 0;
else return (\$lhlast < \$rhlast) ? (-1) : (1);
} else {
return (\$lhv < \$rhv) ? (-1) : (1);
}
}

\$myarray = array('C', 'XCVII', 'XVII', 'LVIf',
'LIb', 'LIXa', 'LIVa', 'IXa',
'DXb', 'DXa', 'IXb', 'IXc', 'XIV',
'IM', 'IC');
usort(\$myarray, 'romansort');
print_r(\$myarray);
?>

========
--
Mail sent to my "From:" address is publicly readable at http://www.dodgeit.com /
== ** ## !!                                                         !! ## ** ==
bypass the spam filter. I will answer all pertinent mails from a valid address.

Re: sorting roman numbers

Ivo wrote:

I'm curious to know why you can't use the preexisting PEAR package. Even
if you have trouble using the pear installer program you can just
download and drop in the file manually: it's a single, standalone .php
file and doesn't depend on other packages.

Perhaps you are thinking of PECL (which is a repository of C-based
extension modules for PHP)?

The PEAR package Numbers_Roman is written in PHP, and is designed to be
used by PHP programs. It's packaged and distributed by the 'PHP
Extension and Application Repository' so that people don't have to
reinvent the same wheel every time the need comes up.

-- brion vibber (brion @ pobox.com)

Re: sorting roman numbers

Ivo wrote:

I've worked with roman numerals... I have a demo at:

http://fxmahoney.com/demo/roman_numeral /

the source can be viewed at:

http://fxmahoney.com/demo/roman_numeral/rn_source.php

I was not aware that IC and IM were "legal" (more like shorthand in
"common usage"...maybe... but generally not used now) -- 99 should be
XCIX and 999 should be CMXCIX (and some sources say that, historically,
VIIII is more appropriate for 9, but my routines stick with IX), at
least according to the rules I researched. 1999 is generally represented
by MCMXCIX and not MIMIC (lol) [I've seen all different kinds of
variations, though -- i guess it just comes down to: find one system and
"stick with it."] At any rate, my routines, as written, will not support
them. (You can try adding them into the \$lookup array -- notice how the
[uncommented] values are prioritized...) [*if you use the num2roman
routine, it won't be a problem]

Secondly, I'm not familiar with the "optional extra lowercase character"
-- have no idea what that's about (mainly because, if the information I
was researching got to be too programmatically complicated, I would pass
on the rest.)

The approach I use is a little unorthodox... if you have any questions,
I'll try to answer them. Just a few notes:

1) I convert vertical bars to underscores to simplify regex [my romans
use vertical bars in place of the overscore to signify x1000 -- for
example, 10,000 is |X|, 5000 is |V|, etc...]

2) I use mostly lookup tables, very little math or if:thens

3) The code takes advantage of newer features of php [4.3 or better]

HTH...

Fox
************

Re: sorting roman numbers

Here is a quick and dirty port of my C implementation written long
time ago. It won't work for overscore characters.

<?php
function InRoman( \$n ) /* converts arabic to roman */
{
\$arabic_tbl = array (1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500,
900, 1000, 9999 );
\$roman_tbl = array ('I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC',
'C', 'CD', 'D', 'CM', 'M');
\$roman_str = ''; //to return
while ( \$n )
{
for( \$i=0 ; \$arabic_tbl[\$i]<=\$n ;++\$i ) //lookup of position
;
--\$i;
\$n -= \$arabic_tbl[\$i];
\$roman_str .= \$roman_tbl[\$i];
}
return \$roman_str;
} /*--InRoman( )----------*/

function InArabic( \$rstr ) /* roman to arabic */
{
\$arabic_tbl = array (1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500,
900, 1000, 9999 );
\$roman_tbl = array ('I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC',
'C', 'CD', 'D', 'CM', 'M');
\$n = 0; //to return
while ( \$rstr )
{
for( \$i=count(\$roman_tbl)-1 ; strncmp(\$rstr, \$roman_tbl[\$i],
strlen(\$roman_tbl[\$i]))!=0 ;--\$i )
;
\$rstr = substr(\$rstr, strlen(\$roman_tbl[\$i])); //remove scanned
chars from left
\$n += \$arabic_tbl[\$i];
}
return \$n;
} /*--InArabic( )------*/

function roman_cmp(\$a, \$b)
{
if (\$a == \$b)
return 0;
return InArabic(\$a) < InArabic(\$b) ? -1 : 1;
}

for(\$i=1; \$i<=50; ++\$i)
{
\$r = InRoman(\$i);
\$a = InArabic(\$r);
echo \$i.'--'.\$r.'--'.\$a."\n";
}

\$test_arr = array('X', 'X', 'I', 'I', 'C', 'IX', 'CD');

usort(\$test_arr, 'roman_cmp');
print_r(\$test_arr);
?>

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com