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

Ответ 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).

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

Edit:

Как вы прокомментировали, вы не хотите запускать преобразование для каждой пары. Это прекрасно, с помощью дополнительного массива, который содержит все преобразованные значения, вы можете запустить сортировку по десятичным значениям и использовать эту сортировку по римским номерам (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} делает большую часть магии здесь.

Ответ 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.

Ответ 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, где первые цифры не указывают на правду. Эти запутанные ситуации были учтены путем сравнения самых больших цифр.

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

• Оберните строки в класс RomanNumeral, который имеет метод сортировки OR
• Напишите способ вычисления значения каждого элемента в массиве и отсортируйте его по
• Посмотрите, кто-то уже написал класс/библиотеку RomanNumeral, который делает это - что-то как это

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

Ответ 7

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

• Сравнить десятичные знаки

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

Ответ 8

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

Ответ 9

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

Возможно, это даст кому-то новое вдохновение.

EDIT: появился рабочий пример. Не очень быстро, сортирует 1000 римских чисел за 1,3 секунды

EDIT 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>";

Ответ 10

Я думаю, что 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)