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

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

hakre , bazmegakapa - 大约 0.0005 秒
anemgyenge , Andrea , Dirk McQuickly - 大约 0.0010 s
Joe Nelson - 大约 0.0050 秒
Rob Hruska - 大约 0.0100 秒

用 4000 个数字测试：

hakre , bazmegakapa - 大约 0.13 秒
anemgyenge - 大约 1.4 秒
Dirk McQuickly , Andrea - 大约 1.8 秒
Rob Hruska - 大约 2.8 秒
Joe Nelson - 大约 15 秒（惊喜，又检查了几次）

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

score 26 · Accepted Answer

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

$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 手册}在这里做了大部分的魔法。

score 10 · Accepted Answer

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.

score 4 · Accepted Answer

有些人建议将罗马数字转换为整数、排序和映射回来。有一个更简单的方法。我们真正需要做的就是比较任意两个罗马数字，usort剩下的就交给我们吧。这是代码，我将在下面解释它的设计。

$base = array( 'I' => 0, 'V' => 1, 'X' => 2, 'L' => 3,
               'C' => 4, 'D' => 5, 'M' => 6 ); 
function single($a) { global $base; return $base[$a]; }

function compare($a, $b) {
    global $base;
    if(strlen($a) == 0) { return true; }
    if(strlen($b) == 0) { return false; }
    $maxa = max(array_map('single', str_split($a)));
    $maxb = max(array_map('single', str_split($b)));
    if($maxa != $maxb) {
        return $maxa < $maxb;
    }
    if($base[$a[0]] != $base[$b[0]]) {
        return $base[$a[0]] < $base[$b[0]];
    }
    return compare(substr($a, 1), substr($b, 1));
}

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

首先，我们创建一个查找数组来为一位罗马数字分配一个“大小”。请注意，这不是它们的十进制值，只是以更大的数字获得更大的值的方式分配的数字。然后我们创建single一些 PHP 函数使用的辅助函数来检索幅度。

好的，现在进入算法的核心。compare当需要打破平局时，有时必须递归调用自身的函数。出于这个原因，我们从一些测试开始，看看它是否在递归中达到了终端状态。暂时忽略这一点，看看第一个有趣的测试。它检查被比较的任一数字中是否有一个数字使另一个数字相形见绌。例如，如果其中一个X在其中，而另一个只有Iand V，则具有的那个X获胜。这依赖于某些罗马数字无效的约定，例如VVorVIIIII或IIIIIIIII。至少我从来没有见过它们是这样写的，所以我认为它们是无效的。

为了进行这项检查，我们将数字映射到幅度并比较最大值。好吧，这个测试可能无法决定问题。在这种情况下，比较每个数字的前几位是安全的，因为我们不必处理令人困惑的问题V < IX，例如前几位不代表真相。通过比较最大数字来处理这些令人困惑的情况。

最后，如果第一个数字相等，将它们去掉并重复。在某些时候，其中一个数字将减少为一个空字符串，而我们暂时忽略的那些初始测试将解决这个问题。

此方法已通过我对其进行的所有测试，但如果您发现错误或优化，请告诉我。

score 2 · Accepted Answer

似乎有三种方法，即：

转换数字，使用标准整数排序进行排序，然后转换回来。（或者用罗马数字保留转换后的版本并对结构进行排序，以避免双重转换。）
编写一个接受字符串的排序函数，此时调用转换函数并进行适当的比较。
编写一个排序函数，可以直接比较罗马数字，而无需进行完全转换。由于罗马数字首先具有较高的组件，（Ms 然后 D/Cs。然后 L/Xs，然后 I/Vs）这样的功能可能会提前短路。

第一个显然会涉及额外的存储开销。第二个将涉及额外的转换开销（因为相同的数字可能会被转换多次）。第三种可能涉及一些不必要的转换开销（同样，相同的数字可能会转换多次），但可以节省一些短路工作。如果存储开销不是问题，那么第一个可能是最好的。

score 2 · Accepted Answer

我对@borrible 的第一种方法很感兴趣，所以我决定试一试：

function sortRomanArray($array) {
     $combined=array_combine($array, array_map('roman2int', $array));
     asort($combined);
     return array_keys($combined);
}

array_map()这基本上使用调用的函数roman2int()（可以是任何实现）将数组中的所有罗马数字转换为整数。然后它创建一个数组，其中键是罗马数字，值是整数。然后这个数组被排序asort()，保留键关联，键作为数组返回。该数组将包含已排序的罗马数字。

我喜欢这种方法，因为它运行转换函数的次数仅与数组大小一样多（我的示例数组为 6），并且不需要转换回来。

如果我们把它放在比较函数中（每次比较两次），转换肯定会运行得更多。

score 1 · Accepted Answer

我认为您必须：

将字符串包装到具有排序方法的 RomanNumeral 类中或
编写一个方法来计算数组中每个元素的值，并对其进行排序
看看是否有人已经编写了执行此操作的 RomanNumeral 类/库 -类似这样

无论哪种方式，您都需要自定义排序代码来计算某处的值。由于罗马数字中的前缀字符有时可能意味着“减去这个值”而不是“添加这个值”。这很好，因为正如您所指出的，您真正在做的是按数值排序，因此您必须告诉计算机如何解释该值。

score 1 · Accepted Answer

使用此将数字转换为小数

比较小数

function roman2dec($roman) {
    // see link above
}

function compare($a, $b) {
    return roman2dec($a) < $roman2dec($b) ? -1 : 1;
}

score 0 · Accepted Answer

假设您制作了这个“字母表”：I、IV、V、IX、X、XL、L、XC、C、CD、D、CM、M。然后您可以根据这个“字母表”对罗马数字进行排序。

也许这会给某人带来新的灵感。

编辑：有一个工作示例。不是很快，在 1.3 秒内对 1000 个罗马数字进行排序

编辑 2：添加了一个检查以避免“通知”，还稍微优化了代码，运行速度更快，并且比转换为整数和排序快大约两倍（使用 PEAR Number_Roman 包）

function sortromans($a, $b){
    $alphabet = array('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I');
    $pos = 0;
    if ($a == $b) {
        return 0;
    }

    //compare the strings, position by position, as long as they are equal
    while(isset($a[$pos]) && isset($b[$pos]) && $a[$pos] === $b[$pos]){
        $pos++;
    }

    //if string is shorter than $pos, return value
    if(!isset($a[$pos])){
        return -1;
    } else if(!isset($b[$pos])){
        return 1;
    } else {

      //check the ´character´ at position $pos, and pass the array index to a variable
      foreach($alphabet as $i=>$ch){
            if(isset($a_index) && isset($b_index)){
         break;
        }
        $length = strlen($ch);
        if(!isset($a_index) && substr($a, $pos, $length) === $ch){
            $a_index = $i;
        }
        if(!isset($b_index) && substr($b, $pos, $length) === $ch){
            $b_index = $i;
        }
      }

    }

    return ($a_index > $b_index) ? -1 : 1;
}

$romans = array('III', 'IX', 'I', 'CM', 'LXII','IV');

usort($romans, "sortromans");

echo "<pre>";
print_r($romans);
echo "</pre>";

score 0 · Accepted Answer

最简单的解决方案可能是先将每个数字转换为常规整数（在新数组中），然后根据整数数组对两个数组进行排序。不过，不确定 PHP 是否包含一个函数。或者，您可以定义一个比较函数，将两个罗马数字转换为整数并进行比较。编写一个直接比较两个罗马数字而不先将它们转换为整数的函数可能会很麻烦。

score 0 · Accepted Answer

我认为最好的（见我的评论）第一个解决方案是在特殊的罗马比较函数的帮助下使用标准的 usort PHP 函数。

下面的roman_compare函数非常直观，不使用任何类型的转换。为了简单起见，它使用尾递归。

function roman_start( $a )
{
    static $romans = array(
        'I'  => 1,    'V'  => 5,
        'X'  => 10,   'L'  => 50,
        'C'  => 100,  'D'  => 500,
        'M'  => 1000,
    );
    return $a[0] . ($romans[$a[0]] < $romans[$a[1]] ? $a[1] : '');
}

function roman_compare( $a, $b )
{
    static $romans = array(
        'I'  => 1,    'IV' => 4,   'V'  => 5,   'IX' => 9,
        'X'  => 10,   'XL' => 40,  'L'  => 50,  'XC' => 90,
        'C'  => 100,  'CD' => 400, 'D'  => 500, 'CM' => 900,
        'M'  => 1000,
    );
    $blockA = roman_start($a);
    $blockB = roman_start($b);
    if ($blockA != $blockB)
    {
        return $romans[$blockA] - $romans[$blockB];    
    }
    $compared = strlen($blockA);
    if (strlen($a) == $compared) //string ended
    {
        return 0;
    }
    return roman_compare(substr($a, $compared), substr($b, $compared));
}

使用上面的函数，我们可以写

function array_equal( $a, $b )
{
    return count(array_diff_assoc($a, $b)) == 0 && count(array_diff_assoc($b, $a)) == 0;
}

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

var_dump(array_equal($sorted_a, $a));
usort($a, 'roman_compare');
var_dump(array_equal($sorted_a, $a));

运行上面我们得到的所有代码

bool(false)
bool(true)

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

10 回答 10

Related

Reference