如何对罗马数字数组进行排序？

Question

我有一个包含罗马数字的数组(当然是字符串).像这样:

 $a = array('XIX', 'LII', 'V', 'MCCXCIV', 'III', 'XIII');

我想根据这些数字的数值对它们进行排序,因此结果应该类似于:

 $sorted_a = array('III', 'V', 'XIII', 'XIX', 'LII', 'MCCXCIV');

所以我的问题是:对罗马数字数组进行排序的最佳方法是什么？我知道如何使用PHP的数组排序函数,我对比较函数内部的逻辑感兴趣.

编辑:为简单起见,我只是寻找一种方法来处理以标准方式构建的基本数字字符串(CCCC例如):

I, V, X, L, C, D, M

---

检测结果

我花时间广泛测试了发布的所有代码示例.进行了两次测试,一次是随机排列的20个罗马数字,第二次是一个包含4000个罗马数字的阵列.相同的机器,大量的迭代,平均花费的时间,以及所有这些运行几次.当然这不是官方的,只是我自己的测试.

测试20个数字:

1. hakre,bazmegakapa - 大约0.0005秒
2. anemgyenge,Andrea,Dirk McQuickly - 约0.0010秒
3. Joe Nelson - 大约0.0050秒
4. Rob Hruska - 大约0.0100秒

测试4000个数字:

1. hakre,bazmegakapa - 大约0.13秒
2. anemgyenge - 大约1.4秒
3. Dirk McQuickly,Andrea - 大约1.8秒
4. Rob Hruska - 大约2.8秒
5. 乔尼尔森 - 大约15秒(惊喜,多次检查)

我很难获得赏金.hakre和我制作了最快的版本,遵循相同的路线,但他做了我的变种,这是以前基于可怕的想法.所以我会接受hakre的解决方案,因为这比我的(IMO)最快,更好.但是我会把这个赏金奖励给amgyenge,因为我喜欢他的版本并且似乎付出了很多努力.

Answer 1

选择将罗马数转换为整数的类,用户定义的排序回调可以处理这个以对数组进行排序:

$a = array('XIX', 'LII', 'V', 'MCCXCIV', 'III', 'XIII');

$bool = usort($a, function($a, $b) {
    return RomanNumber::Roman2Int($a) - RomanNumber::Roman2Int($b);
});    
var_dump($a);

所以在这里你可以找到比较函数中的逻辑:如果两个值具有相同的权重,则返回0.如果第一个低于第二个,则返回< 0(例如-1),否则第二个大于第一个返回> 0(例如1).

当然,任何其他类型的函数都可以返回罗马数字的十进制值.

编辑:

正如您所评论的那样,您不希望为每对运行转换.没关系,在包含所有转换值的附加数组的帮助下,您可以对小数值运行排序并对罗马数字进行排序(演示):

$a = array('XIX', 'LII', 'V', 'MCCXCIV', 'III', 'XIII');
$b = array_map('RomanNumber::Roman2Int', $a);
array_multisort($b, $a);
var_dump($a);

array_multisort ^PHP手册在这里做了大部分的魔术.

Answer 2

function sortRomanNum($a, $b) {
    if($a == $b) return 0;

    $str = "0IVXLCDM";
    $len = 0;

    if(strlen($a) >= strlen($b)) {
        $len = strlen($a);
        $b .= str_repeat("0", $len - strlen($b));
    }
    else {
        $len = strlen($b);
        $a .= str_repeat("0", $len - strlen($a));
    }

    for($i = 0; $i < $len - 1; $i++) {
        $a1 = $a[$i]; $b1 = $b[$i]; $a2 = $a[$i+1]; $b2 = $b[$i+1];

        if( strpos($str, $a1.$b1.$a2) !== false ) return 1;
        if( strpos($str, $b1.$a1.$b2) !== false ) return -1;

        if($a1 != $b1) return strpos($str, $a1) > strpos($str, $b1) ? 1 : -1;
    }

    if($a[$i] != $b[$i]) return strpos($str, $a[$i]) > strpos($str, $b[$i]) ? 1 : -1;
}

给出两个数字(罗马字符串),$ a和$ b.如果数字中没有减法(IV,IX,XC等),那么解决方案将是微不足道的:

for all $i in $a and $b
    if $a[$i] > $b[$i] then return 1; //($a is greater then $b)
    if $a[$i] < $b[$i] then return 1; //($a is lower then $b)
return 0 //equality

由于可能存在这些特殊部件,因此计算更复杂.但解决方案是找到模式:

a: IX | XC | CM
b: V  | L  | D

这些是唯一可以搞乱这个简单解决方案的模式.如果你发现其中任何一个,那么$ a将大于$ b.

请注意,罗马数字不包括零,如阿拉伯数字.因此,现在我们将使用它们(并且基本上将零放在缺少的位置).

所以这里有功能:

if $a == $b then return 0; //equality
create a string for ordering the roman numerals (strpos will give the right index)
define the length of the loop (take the longer string), and add zeros to the end of the shorter number
run the loop, and check:
    1. if the patterns above are found, return the comparision accordingly (1 or -1)
    2. otherwise do the trivial check (compare each numeral)
check the last numerals too.