Как отсортировать массив римских цифр?

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. хакре , базмегакапа - около 0,0005 с
2. анемгендж , Андреа , Дирк МакКвикли - около 0,0010 с
3. Джо Нельсон - около 0,0050 с
4. Роб Хруска - около 0,0100 с

ТЕСТ С 4000 ЦИФРАМИ:

1. хакре , базмегакапа - около 0,13 с
2. анемия: - около 1,4 с
3. Дирк МакКвикли , Андреа - около 1,8 с
4. Роб Хруска - около 2,8 с
5. Джо Нельсон - около 15 с (удивление, проверено еще несколько раз)

Мне трудно присудить награду. Хакре и я сделали самые быстрые версии, следуя одному и тому же маршруту, но он сделал мою вариацию, которая ранее была основана на идее Борнорда. Поэтому я приму решение Хакре, потому что оно самое быстрое и приятное, чем мое (ИМО). Но я буду награждать награду за анемгендж, потому что я люблю его версию, и, похоже, в нее вложено много усилий.

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).

Естественно, любой другой типфункции, которая возвращает десятичное значение для римского числа, также будет работать.

Редактировать:

Как вы прокомментировали, вы не хотите запускать преобразование для каждогопара.Это нормально, с помощью дополнительного массива, который содержит все преобразованные значения, вы можете запустить сортировку по десятичным значениям и использовать эту сортировку также по римским числам ( Demo ):

$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.

Answer 3

Некоторые люди предлагают преобразовать римские цифры в целые числа, сортировать и отображать обратно. Есть более простой способ. Все, что нам действительно нужно сделать, это сравнить любые две произвольные римские цифры и позволить 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, а у другого только I и V, то выигрывает тот, у кого X. Это основывается на соглашении о том, что некоторые римские цифры недопустимы, например, VV или VIIIII или IIIIIIIII. По крайней мере, я никогда не видел их написанными таким образом, поэтому считаю их недействительными.

Чтобы выполнить эту проверку, мы сопоставляем цифры с величинами и сравниваем максимумы. Ну, этот тест не может решить проблему. В этом случае безопасно сравнивать первые цифры каждого номера, поскольку нам не придется сталкиваться с такими запутанными проблемами, как V < IX, когда первые цифры не говорят правду. Эти запутанные ситуации были решены путем сравнения самых больших цифр.

Наконец, если первые цифры равны, удалите их и повторите. В какой-то момент одна из цифр будет уменьшена до пустой строки, и те начальные тесты, которые мы временно игнорировали, позаботятся об этом.

Этот метод прошел все тесты, которые я ему проводил, но сообщите мне, если найдете ошибку или оптимизацию.

Answer 4

Меня очень заинтересовал 1-й подход @ borrible , поэтому я решил попробовать:

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

Это в основном преобразует все римские цифры в массиве в целые числа, используя array_map() и функцию с именем roman2int() (которая может быть любой реализацией). Затем он создает массив, где ключи - это римские цифры, а значения - целые числа. Затем этот массив сортируется с asort(), который сохраняет ассоциации ключей, и ключи возвращаются в виде массива. Этот массив будет содержать отсортированные римские цифры.

Мне нравится этот метод, потому что он выполняет функцию преобразования только столько раз, сколько размер массива (6 для моего примера массива), и нет необходимости преобразовывать обратно.

Преобразование будет выполняться гораздо больше, если мы поместим его в функцию сравнения (2 раза для каждого сравнения).

Answer 5

Казалось бы, три подхода, а именно:

• Преобразование чисел, сортировка с использованием стандартной целочисленной сортировки и обратное преобразование. (Или сохраните преобразованные версии с римскими цифрами и сортируйте структуры, чтобы избежать двойного преобразования.)
• Напишите функцию сортировки, которая принимает строки, в этот момент вызывает функцию преобразования и выполняет соответствующее сравнение.
• Напишите функцию сортировки, которая может сравнивать римские цифры напрямую, без необходимости полного преобразования. Поскольку римские цифры имеют вначале свои более высокие компоненты (Ms, затем D / Cs, затем L / Xs, затем I / Vs), такая функция могла бы быть в состоянии короткого замыкания на раннем этапе.

Первое, очевидно, потребует дополнительных накладных расходов на хранение. Второй будет связан с дополнительными издержками преобразования (поскольку одно и то же число может быть преобразовано много раз). Третий может включать в себя некоторые ненужные издержки преобразования (опять же, одно и то же число может быть преобразовано несколько раз), но сэкономит некоторую работу по короткому замыканию. Если затраты на хранение не являются проблемой, первое, вероятно, будет лучшим.

Answer 6

1. Преобразуйте число в десятичное число, используя this

2. Сравните десятичные дроби

   function roman2dec($roman) {
       // see link above
   }
   
   function compare($a, $b) {
       return roman2dec($a) < $roman2dec($b) ? -1 : 1;
   }
   

Answer 7

Я думаю, вам придется либо:

1. Обернуть строки в класс RomanNumeral, у которого есть метод сортировки ИЛИ
2. Написать метод для вычисления значения каждогоэлемент в массиве, и сортируйте по этому
3. Посмотрите, если кто-то уже написал класс / библиотеку RomanNumeral, которая делает это - что-то как это

В любом случаеВам понадобится специальный код сортировки, который вычисляет значение где-то.Поскольку префикс символов в римских цифрах иногда может означать «вычесть это значение», а не «добавить это значение».Это нормально, потому что, как вы уже указали, вы действительно сортируете по числовому значению, поэтому вам придется указать компьютеру, как интерпретировать это значение.

Answer 8

Я думаю, что первое решение best (см. Мой комментарий) заключается в использовании стандартной функции 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)

Answer 9

Допустим, вы делаете этот «алфавит»: I, IV, V, IX, X, XL, L, XC, C, CD, D, CM, M. Затем вы можете отсортировать римские числа по этому «алфавиту».'.

Может быть, это даст кому-то новое вдохновение.

РЕДАКТИРОВАТЬ: получил рабочий пример.Не очень быстро, сортирует 1000 римских чисел за 1,3 с

РЕДАКТИРОВАТЬ 2: добавлена ​​проверка, чтобы избежать «уведомлений», также немного оптимизирован код, работает немного быстрее и примерно в два раза быстрее, чем спреобразование в целое число и затем сортировка (используется пакет PEAR Number_Roman)

<code>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 "

";

Answer 10

Самое простое решение - сначала преобразовать каждую цифру в обычное целое число (в новом массиве), а затем отсортировать оба массива на основе целочисленного массива.Не уверен, что в PHP есть функция для этого.Кроме того, вы можете определить функцию сравнения, которая преобразует две римские цифры в целые числа и сравнивает их.Написание функции, которая непосредственно сравнивает две римские цифры без предварительного преобразования их в целые числа, вероятно, будет громоздким.