php - naturales - diagrama de flujo para convertir numeros arabigos a romanos
¿Cómo ordenar una matriz de números romanos? (10)
Tengo una matriz que contiene números romanos (como cadenas, por supuesto). Me gusta esto:
$a = array(''XIX'', ''LII'', ''V'', ''MCCXCIV'', ''III'', ''XIII'');
Me gustaría ordenarlos de acuerdo con los valores numéricos de estos números, por lo que los resultados deberían ser algo así como:
$sorted_a = array(''III'', ''V'', ''XIII'', ''XIX'', ''LII'', ''MCCXCIV'');
Entonces mi pregunta es: ¿cuál es la mejor manera de ordenar una matriz de números romanos? Sé cómo usar las funciones de ordenamiento de matrices de PHP, estoy interesado en la lógica que ocurre dentro de la función de comparación.
EDITAR : Para simplificar, solo busco una forma que trate cadenas construidas con los números básicos de una manera estándar (sin CCCC por ejemplo):
I, V, X, L, C, D, M
RESULTADOS DE LA PRUEBA
Me tomé el tiempo para probar exhaustivamente todos los ejemplos de código que se publicaron. Se tomaron dos pruebas, una con una matriz aleatoria de 20 números romanos, y una segunda con una matriz que contiene 4000 de esos. La misma máquina, muchas iteraciones, un tiempo promedio tomado y todo esto se repite varias veces. Por supuesto, esto no es nada oficial, solo mis propias pruebas.
PRUEBA CON 20 NUMERALES:
- hakre , bazmegakapa - alrededor de 0.0005 s
- anemgyenge , Andrea , Dirk McQuickly - alrededor de 0.0010 s
- Joe Nelson - alrededor de 0.0050 s
- Rob Hruska - alrededor de 0.0100 s
PRUEBA CON 4000 NUMERALES:
- hakre , bazmegakapa - alrededor de 0.13 s
- anemgyenge - alrededor de 1.4 s
- Dirk McQuickly , Andrea - alrededor de 1.8 s
- Rob Hruska - alrededor de 2.8 s
- Joe Nelson - alrededor de 15 s (sorpresa, comprobado varias veces más)
Tengo dificultades para otorgar la recompensa. Hakre y yo hicimos las versiones más rápidas, siguiendo la misma ruta, pero hizo una variación de la mía, que anteriormente estaba basada en la idea de borrible. Entonces, aceptaré la solución de hakre, porque es la más rápida y mejor que la mía (IMO). Pero otorgaré la recompensa a un enemigo, porque amo su versión y parece que se han puesto muchos esfuerzos en ello.
- Convierte el número en un decimal usando esto
Compara los decimales
function roman2dec($roman) { // see link above } function compare($a, $b) { return roman2dec($a) < $roman2dec($b) ? -1 : 1; }
Algunas personas han sugerido convertir números romanos en números enteros, ordenando y mapeando. Hay una manera más fácil. Todo lo que realmente necesitamos hacer es comparar dos números romanos arbitrarios y dejar el resto. Aquí está el código, y explicaré su diseño a continuación.
$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);
Primero creamos una matriz de búsqueda para asignar una "magnitud" a números romanos de un solo dígito. Observe que este no es su valor decimal, solo números asignados de tal manera que los números más grandes obtienen valores más grandes. Luego creamos un single función auxiliar utilizado por algunas funciones PHP para recuperar las magnitudes.
OK, ahora a la carne del algoritmo. Es la función de compare que a veces tiene que llamarse recursivamente cuando necesita romper un empate. Por esta razón, comenzamos con algunas pruebas para ver si ha llegado a estados terminales en la recursión. Ignore eso por ahora y mire la primera prueba interesante. Comprueba si alguno de los números que se comparan tiene un dígito que empequeñece los dígitos del otro. Por ejemplo, si uno de ellos tiene X en él y el otro solo tiene I y V , entonces el que tiene X gana. Esto se basa en la convención de que ciertos números romanos no son válidos, como VV o VIIIII o IIIIIIIII . Al menos, nunca los había visto escritos de esa manera, así que los considero inválidos.
Para hacer esta comprobación, asignamos los dígitos a las magnitudes y comparamos los máximos. Bueno, esta prueba puede no decidir el problema. En ese caso, es seguro comparar los primeros dígitos de cada número, ya que no tendremos que lidiar con problemas confusos como V < IX donde los primeros dígitos no sugieren la verdad. Estas situaciones confusas fueron resueltas al comparar los dígitos más grandes.
Finalmente, si los primeros dígitos son iguales, quítelos y repita. En algún momento, uno de los números se reducirá a una cadena vacía, y esas pruebas iniciales que estábamos ignorando temporalmente se encargarán de eso.
Este método ha pasado todas las pruebas que arrojé, pero avíseme si encuentra un error u optimizaciones.
Creo que la mejor solución (ver mi comentario) es usar la función estándar de usort PHP con la ayuda de una función especial de comparación romana.
La siguiente función roman_compare es muy intuitiva y no utiliza ningún tipo de conversión. Para hacerlo simple, usa recursividad de cola.
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));
}
Usando las funciones anteriores, podemos escribir
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));
Ejecutando todo el código anterior obtenemos
bool(false)
bool(true)
Creo que tendrás que:
- Envuelva las cadenas en una clase RomanNumeral, que tiene un método de clasificación O
- Escribe un método para calcular el valor de cada elemento en la matriz y ordena el
- Vea si alguien ya ha escrito una clase / biblioteca RomanNumeral que hace esto, algo como esto
De cualquier manera, necesitarás un código de clasificación personalizado que calcule el valor en alguna parte. Como el prefijo de los caracteres en números romanos a veces puede significar "restar este valor" en lugar de "agregar este valor". Esto está bien, porque como has señalado, lo que realmente estás haciendo es ordenar por valor numérico, por lo que tendrás que decirle a la computadora cómo interpretar el valor.
Digamos que usted hace este "alfabeto": I, IV, V, IX, X, XL, L, XC, C, CD, D, CM, M. Luego puede ordenar los números romanos de acuerdo con este ''alfabeto''.
Tal vez esto le dará a alguien una nueva inspiración.
EDITAR: tengo un ejemplo de trabajo. No muy rápido, ordena 1000 números romanos en 1.3 segundos
EDIT 2: se agregó una marca para evitar los ''avisos'', también se optimizó un poco el código, se ejecutó un poco más rápido, y aproximadamente el doble de rápido que con una conversión a entero y luego se ordenó (paquete PEAR Number_Roman usado)
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>";
Escogiendo su clase para convertir números romanos en enteros , una devolución de llamada de ordenación definida por el usuario puede manejar esto para ordenar la matriz:
$a = array(''XIX'', ''LII'', ''V'', ''MCCXCIV'', ''III'', ''XIII'');
$bool = usort($a, function($a, $b) {
return RomanNumber::Roman2Int($a) - RomanNumber::Roman2Int($b);
});
var_dump($a);
Así que aquí encontrará la lógica dentro de la función de comparación: si ambos valores tienen el mismo peso, devuelva 0 . Si el primero es menor que el segundo, devuelve < 0 (por ejemplo, -1 ); de lo contrario, el segundo es más grande que el primero, así que regresa > 0 (por ejemplo, 1 ).
Naturalmente, cualquier otro tipo de función que devuelva el valor decimal para un número romano funcionaría también.
Editar:
Como ha comentado, no desea ejecutar la conversión para cada par. Está bien, con la ayuda de una matriz adicional que contiene todos los valores convertidos, puede ejecutar la ordenación en los valores decimales y usar esa ordenación en los números romanos también ( 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 hace la mayor parte de la magia aquí.
La solución más simple es, probablemente, primero convertir cada número en un entero regular (en una nueva matriz), y luego ordenar ambas matrices en función de la matriz de enteros. Sin embargo, no estoy seguro si PHP contiene una función para eso. Alternativamente, puede definir una función de comparación que convierta dos números romanos en enteros y los compare. Escribir una función que compare directamente dos números romanos sin convertirlos primero en enteros probablemente sea engorroso.
Me interesó bastante el primer enfoque de @borrible , así que decidí probarlo:
function sortRomanArray($array) {
$combined=array_combine($array, array_map(''roman2int'', $array));
asort($combined);
return array_keys($combined);
}
Esto básicamente convierte todos los números romanos en la matriz en enteros usando array_map() y una función llamada roman2int() (que puede ser cualquier implementación). Luego crea una matriz donde las claves son los números romanos y los valores son los enteros. A continuación, esta matriz se ordena con asort() que conserva las asociaciones de teclas y las claves se devuelven como una matriz. Esta matriz contendrá los números romanos clasificados.
Me gusta este método porque ejecuta la función de conversión solo tantas veces como el tamaño de la matriz (6 con mi matriz de ejemplo) y no hay necesidad de convertir de nuevo.
La conversión correría ciertamente mucho más si lo ponemos en la función de comparación (2 veces para cada comparación).
Parece que hay tres enfoques, a saber:
- Convierta los números, ordene usando una clasificación entera estándar y convierta de nuevo. (O mantenga las versiones convertidas con los números romanos y clasifique las estructuras para evitar la doble conversión).
- Escriba una función de ordenamiento que tome las cadenas, en ese punto llama a una función de conversión y hace la comparación apropiada.
- Escribe una función de clasificación que pueda comparar números romanos directamente, sin que sea necesario realizar una conversión completa. Como los números romanos tienen sus componentes más altos primero, (Ms luego D / Cs. Luego L / Xs, luego I / Vs) tal función podría ser capaz de cortocircuitar temprano.
El primero obviamente implicará gastos adicionales para el almacenamiento. El segundo implicará una sobrecarga de conversión adicional (ya que el mismo número se puede convertir muchas veces). El tercero puede implicar una sobrecarga de conversión innecesaria (de nuevo, el mismo número puede convertirse varias veces) pero ahorra algo de trabajo en el cortocircuito. Si los gastos generales de almacenamiento no son un problema, es probable que el primero sea el mejor.
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;
}
Dado dos números (cadenas romanas), $ a y $ b. Si no hay sustracciones en los números (IV, IX, XC, etc.), entonces la solución sería trivial:
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
Como puede haber estas partes especiales, el cálculo es más complejo. Pero la solución es encontrar los patrones:
a: IX | XC | CM
b: V | L | D
Estos son los únicos patrones que pueden arruinar la solución trivial. Si encuentra alguno de estos, entonces $ a será mayor que $ b.
Tenga en cuenta que los números romanos no incluyen ceros, como los arábigos. Por lo tanto, ahora los usaremos (y básicamente pondremos ceros donde falten).
Entonces aquí viene la función:
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.