Comment trier un tableau de chiffres romains ?

Question

J'ai un contenant Chiffres romains (sous forme de ficelles bien sûr). Comme ceci :

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

J'aimerais les trier selon les valeurs numériques de ces chiffres, donc les résultats devraient être quelque chose comme :

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

Donc ma question est : Quelle est la meilleure façon de trier un tableau de chiffres romains ? Je sais comment utiliser les fonctions de tri des tableaux de PHP, mais je suis intéressé par la logique de la fonction de comparaison.

EDIT : Pour des raisons de simplicité, je ne cherche qu'un moyen qui traite les chaînes construites à partir des chiffres de base de manière standard (pas de CCCC par exemple) :

I, V, X, L, C, D, M

---

RÉSULTATS DES TESTS

J'ai pris le temps de tester de manière approfondie tous les exemples de code qui ont été postés. Deux tests ont été effectués, un avec un tableau aléatoire de 20 chiffres romains, et un second avec un tableau contenant 4000 de ces chiffres. Même machine, beaucoup d'itérations, un temps moyen pris, et tout ceci exécuté plusieurs fois. Bien sûr, cela n'a rien d'officiel, ce sont juste mes propres tests.

TEST AVEC 20 CHIFFRES :

1. hakre , bazmegakapa - environ 0,0005 s
2. anemgyenge , Andrea , Dirk McQuickly - environ 0,0010 s
3. Joe Nelson - environ 0,0050 s
4. Rob Hruska - environ 0,0100 s

TEST AVEC 4000 CHIFFRES :

1. hakre , bazmegakapa - environ 0,13 s
2. anemgyenge - environ 1,4 s
3. Dirk McQuickly , Andrea - environ 1,8 s
4. Rob Hruska - environ 2,8 s
5. Joe Nelson - environ 15 s (surprise, vérifié plusieurs fois)

J'ai du mal à attribuer la prime. hakre et moi avons fait les versions les plus rapides, en suivant la même route, mais il a fait une variante de la mienne, qui était auparavant basée sur l'idée de borrible. Donc je vais accepter la solution de hakre, parce que c'est la plus rapide et plus belle que la mienne (IMO). Mais je vais attribuer la prime à anemgyenge, parce que j'aime sa version et que beaucoup d'efforts semblent avoir été faits.

Answer 1

Choisir votre classe pour convertir les nombres romains en nombres entiers un callback de tri défini par l'utilisateur peut s'en charger pour trier le tableau :

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

$bool = usort($a, function($a, $b) {
    return RomanNumber::Roman2Int($a) - RomanNumber::Roman2Int($b);
});    
var_dump($a);

On retrouve donc ici la logique de la fonction de comparaison : si les deux valeurs ont le même poids, on renvoie 0 . Si le premier est inférieur au second, on retourne < 0 (par exemple -1 ), sinon le second est plus grand que le premier, donc on retourne > 0 (par exemple 1 ).

Naturellement, tout autre type de fonction qui renvoie la valeur décimale d'un nombre romain fonctionnerait également.

Editar:

Comme vous l'avez commenté, vous ne voulez pas exécuter la conversion pour chaque paire. C'est bien, avec l'aide d'un tableau supplémentaire qui contient toutes les valeurs converties, vous pouvez exécuter le tri sur les valeurs décimales et utiliser ce tri sur les nombres romains également ( Démo ) :

$a = array('XIX', 'LII', 'V', 'MCCXCIV', 'III', 'XIII');
$b = array_map('RomanNumber::Roman2Int', $a);
array_multisort($b, $a);
var_dump($a);

array_multisort Manuel PHP fait la plupart de la magie ici.

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;
}

Étant donné deux nombres (chaînes romaines), $a et $b. S'il n'y a pas de soustractions dans les nombres (IV, IX, XC, etc.), la solution est triviale :

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

Comme il peut y avoir ces pièces spéciales, le calcul est plus complexe. Mais la solution consiste à trouver les modèles :

a: IX | XC | CM
b: V  | L  | D

Ce sont les seuls motifs qui peuvent perturber la solution triviale. Si vous trouvez l'un de ces motifs, alors $a sera supérieur à $b.

Notez que les chiffres romains ne comprennent pas de zéros, comme les chiffres arabes. Par conséquent, nous allons maintenant les utiliser (et mettre des zéros là où ils manquent).

Voici donc la fonction :

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

Certaines personnes ont suggéré de convertir les chiffres romains en nombres entiers, de les trier et de les remettre en correspondance. Il existe une méthode plus simple. Tout ce que nous devons faire est de comparer deux chiffres romains arbitraires et de laisser usort faire le reste. Voici le code, et je vais expliquer sa conception ci-dessous.

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

Tout d'abord, nous créons un tableau de consultation pour attribuer une "magnitude" aux chiffres romains à un seul chiffre. Notez qu'il ne s'agit pas de leur valeur décimale, mais simplement de chiffres attribués de telle sorte que les plus grands chiffres obtiennent de plus grandes valeurs. Ensuite, nous créons une fonction d'aide single utilisé par certaines fonctions PHP pour récupérer les magnitudes.

OK, passons maintenant à l'essentiel de l'algorithme. Il s'agit de la compare qui doit parfois s'appeler elle-même de manière récursive lorsqu'elle doit départager une égalité. Pour cette raison, nous commençons par quelques tests pour voir si elle a atteint des états terminaux dans la récursion. Ignorez cela pour l'instant et regardez le premier test intéressant. Il vérifie si l'un des deux numéraux comparés contient un chiffre qui éclipse tous les chiffres de l'autre. Par exemple, si l'un des deux a X en elle, et l'autre n'a que I y V puis celui avec X gagne. Cela repose sur la convention selon laquelle certains chiffres romains ne sont pas valables, comme par exemple VV o VIIIII o IIIIIIIII . En tout cas, je ne les ai jamais vus écrits de cette façon, donc je les considère comme non valables.

Pour faire cette vérification, nous faisons correspondre les chiffres à des magnitudes et comparons les maximums. Ce test ne permet pas forcément de trancher la question. Dans ce cas, il est plus sûr de comparer les premiers chiffres de chaque nombre, puisque nous n'aurons pas à traiter de questions déroutantes telles que V < IX où les premiers chiffres ne suggèrent pas la vérité. La comparaison des plus grands chiffres a permis de remédier à ces situations confuses.

Enfin, si les premiers chiffres sont égaux, on les enlève et on recommence. À un moment donné, l'un des chiffres sera réduit à une chaîne vide, et les tests initiaux que nous avons temporairement ignorés s'en chargeront.

Cette méthode a passé tous les tests que je lui ai fait subir, mais faites-moi savoir si vous trouvez un bogue ou des optimisations.

Answer 4

Il semblerait qu'il y ait trois approches, à savoir :

• Convertissez les nombres, triez-les à l'aide d'un tri standard d'entiers, et reconvertissez-les. (Ou gardez les versions converties avec les chiffres romains et triez les structures, pour éviter la double conversion).
• Écrivez une fonction de tri qui prend les chaînes de caractères, appelle à ce moment-là une fonction de conversion et effectue la comparaison appropriée.
• Écrivez une fonction de tri qui peut comparer des chiffres romains directement, sans avoir à effectuer une conversion complète. Puisque les chiffres romains ont leurs composantes supérieures en premier (Ms puis D/C. puis L/X, puis I/V), une telle fonction pourrait être capable de court-circuiter rapidement.

La première implique évidemment des frais généraux supplémentaires pour le stockage. La deuxième impliquera une surcharge de conversion supplémentaire (puisque le même nombre peut être converti plusieurs fois). La troisième peut impliquer des frais de conversion inutiles (là encore, le même nombre peut être converti plusieurs fois) mais permet d'économiser du travail sur le court-circuitage. Si les frais généraux de stockage ne sont pas un problème, la première solution est probablement la meilleure.

Answer 5

Je me suis intéressé à La 1ère approche du @borrible J'ai donc décidé d'essayer :

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

Cela convertit essentiellement tous les chiffres romains du tableau en nombres entiers en utilisant array_map() et une fonction appelée roman2int() (qui peut être n'importe quelle implémentation). Ensuite, il crée un tableau dont les clés sont les chiffres romains et les valeurs les entiers. Ensuite, ce tableau est trié avec asort() qui préserve les associations de clés, et les clés sont retournées sous forme de tableau. Ce tableau contiendra les chiffres romains triés.

J'aime cette méthode car elle n'exécute la fonction de conversion qu'autant de fois que la taille du tableau (6 avec mon exemple de tableau) et il n'y a pas besoin de reconvertir.

La conversion s'exécuterait certainement beaucoup plus si on la mettait dans la fonction de comparaison (2 fois pour chaque comparaison).