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

php arrays sorting roman-numerals

2022-08-30 14:36:05

我有一个包含罗马数字的数组（当然是字符串）。喜欢这个：

 $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个数字测试：

哈克雷，巴兹梅加卡帕 - 约0.0005秒
anemgyenge， Andrea， Dirk McQuickly - 大约0.0010 s
乔·尼尔森 - 约0.0050 s
罗布赫鲁斯卡 - 约0.0100秒

使用 4000 个数字进行测试：

哈克雷，巴兹梅加卡帕 - 约0.13秒
阿尼姆金格 - 约1.4秒
德克·麦奎克利，安德里亚 - 约1.8秒
罗布赫鲁斯卡 - 约2.8秒
Joe Nelson - 大约15秒（惊喜，又检查了几次）

我很难颁发赏金。hakre和我按照相同的路线制作了最快的版本，但他制作了我的变体，这以前是基于borrible的想法。所以我会接受hakre的解决方案，因为这是比我（IMO）更快，更好的解决方案。但是我会把赏金颁发给anemgyenge，因为我喜欢他的版本，而且似乎投入了很多精力。

答案 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> 01

当然，任何其他类型的函数返回罗马数字的十进制值也可以工作。

编辑：

正如您所评论的，您不希望对每对运行转换。这很好，借助包含所有转换值的附加数组，您可以对十进制值运行排序，并对罗马数字也使用排序（演示）：

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

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

答案 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.