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

Выбирая свой класс для преобразования римских чисел в целые числа , пользовательский метод обратного вызова может обрабатывать это для сортировки массива:

 $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 ), в противном случае второе будет больше первого, поэтому return > 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 Manual} делает большую часть магии здесь.

 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. 

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

 $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); 

Сначала мы создаем массив поиска, чтобы присвоить «величину» однозначным римским цифрам. Обратите внимание, что это не их десятичное значение, а просто числа, назначенные таким образом, что большие цифры получают большие значения. Затем мы создаем вспомогательную функцию, используемую некоторыми функциями PHP, чтобы получить величины.

Хорошо, теперь к мясу алгоритма. Это функция compare которую иногда приходится называть рекурсивно, когда нужно сломать галстук. По этой причине мы начинаем с некоторых тестов, чтобы проверить, достигли ли они конечных состояний в рекурсии. Не обращайте внимания на это сейчас и посмотрите на первый интересный тест. Он проверяет, не сравнивается ли какая-либо цифра с цифрой, которая затмевает любые цифры другого. Например, если один из них имеет в нем X , а другой имеет только I и V , то выигрывает тот, у которого есть X Это зависит от того, что некоторые римские цифры недействительны, например, VV или VIIIII или IIIIIIIII . По крайней мере, я никогда их не видел так, поэтому считаю их недействительными.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, вы сделали этот «алфавит»: 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>"; 

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