Tri avec exceptions

Version imprimable

24/01/2013, 22h48
boteha

Tri avec exceptions
Bonjour,

J'ai un tableau, par exemple :
Code:

1 2 $tab = array ('a', 'b', 'c', 'd' 'e');
Je veux le trier de façon naturelle, mais en gérant des exceptions, par exmple 'e' avant 'a' et 'd' avant 'c' de façon à obtenir le tri suivant :

e
a
b
d
c

Je suppose que c'est possible mais comment faire ?

Merci d'avance.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
function cmp($a, $b) {
$trie= array ('a'=>2, 'b'=>3, 'c'=>6, 'd'=>5, 'e'=>1, 'f'=>4, 'g'=>5);
$a_value = $trie[$a];
$b_value = $trie[$b];
if ($a_value == $b_value) {
        return 0;
    }
    return ($a_value < $b_value) ? -1 : 1;
}
 
$tab = array ('a', 'b', 'c', 'd', 'e');
usort($tab, "cmp");
var_dump($tab);

Il y a peut être plus élégant.

Une version avec des mots :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function cmp($a, $b) {
$tri = array ('a'=>2, 'b'=>3, 'c'=>6, 'd'=>5, 'e'=>1, 'f'=>4, 'g'=>5);
$max = strlen($a);
for ($i = 0; $i < $max; $i++) {
	if (!isset($b[$i])) {
		return 1;
	}
	if($tri[$a[$i]] > $tri[$b[$i]]) {
		return 1;
	}
	elseif ($tri[$a[$i]] < $tri[$b[$i]]) {
		return -1 ;
	}
}
 
return 0;
}
 
$tab = array ('aef', 'ae', 'cfa', 'd', 'e');
usort($tab, "cmp");
var_dump($tab);

25/01/2013, 23h41
boteha
Bonjour sabotage,

Merci de ta réponse (notification par mail non reçue...).

Néanmoins, ce qui me gêne est que tu enrichis le tableau d'origine avec des valeurs correspondantes au classement.

Dans ce cas, il me semble aussi simple de faire :
Code:

1 2 3 $tab = array_flip ($tab); ksort ($tab); $tab = array_flip ($tab);
J'aimerais pouvoir ne pas toucher au tableau d'origine et simplement signifier que 'e' avant 'a' et 'd' avant 'c'.

Dans la réalité j'ai beaucoup de tableaux avec beaucoup de valeurs et la maintenance devient trop tordue s'il faut donner un ordre, je veux juste gérer quelques exceptions au classement naturel.
26/01/2013, 10h54
sabotage

je ne touche pas au tableau d'origine ($tab), $tri est le tableau contenant l'ordre souhaité.
26/01/2013, 17h30
boteha

Bonjour sabotage,

D'accord.

Mais cela t'oblige quand même à recopier le tableau dans la fonction et numéroter l'ordre.

J'essaye de réfléchir à une solution plus simple ou tu aurais juste besoin d'indiquer :

$tab_exception = array ('e' =>'a', 'd' =>'c');
27/01/2013, 11h15
sabotage

Citation:

Mais cela t'oblige quand même à recopier le tableau dans la fonction et numéroter l'ordre.

non $tri est l'ordre souhaité pour l'alphabet, je me suis arrêté à g pour l'exemple.
27/01/2013, 20h49
boteha

Bonjour Sabotage,

Merci de ton intérêt.

Je pense avoiri trouvé une solution où je n'utilise que le tableau d'exceptions sans rien numéroter.

Pas le temps ce soir mais je l'écris demain.
28/01/2013, 14h40
Benjamin Delespierre

regarde du coté de usort

Bonsoir,

Je ne sais pas si on peut faire avec usort () mais je propose une solution qui devrait marcher.

$tab est créé à la volée, les clés sont sans importance et il est facile de faire que les clés soient paires et commencent par 2.
Numérotation automatique et aucune maintenance.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 $tab = array (2 => 'a', 4 => 'b', 6 => 'c', 8 => 'd', 10 => 'e'); $tab_exception = array ('e' =>'a', 'd' =>'c'); // placer e avant a et d avant c function Classe_Exceptions ($tab, $tab_exception) { while (list ($k, $v) = each ($tab_exception)) { $cle_k = array_keys ($tab, $k); $cle_v = array_keys ($tab, $v); $cle_k = $cle_k[0]; $cle_v = $cle_v[0]; // récupère 10 et 2 pour e et a $cle_v -= 1; $tab[$cle_v] = $tab[$cle_k]; // place e en 1 avant a unset ($tab[$cle_k]); // enlève e en 10 } ksort ($tab); return $tab; }
Je ne dis pas que c'est élégant mais cela devrait être très rapide.

28/01/2013, 21h04
sabotage

Citation:

Je ne dis pas que c'est élégant mais cela devrait être très rapide.

C'est vrai pourquoi utiliser des algorithmes spécialement étudiés pour faire du tri :P

Ton code ne prend pas en compte qu'un caractère n'est pas forcemment dans la liste des exceptions ou qu'un caractère est présent deux fois.
De plus il suppose que le tableau de départ est déjà trié.
29/01/2013, 13h30
boteha

Bonjour,

Le tableau est tr!é.
Il n'y a pas de doublon.

Citation:

Ton code ne prend pas en compte qu'un caractère n'est pas forcemment dans la liste des exceptions

Je ne comprends pas ce que tu veux dire.

Je veux n'avoir à maintenir qu'un tableau des exceptions.
Si c'est possible avec usort () je n'ai rien contre mais ta fonction oblige à maintenir un classement complet.

Les deux cas ci-dessous provoquent des erreurs :

Code:

1
2
$tab = array (2 => 'a', 4 => 'b', 6 => 'c', 8 => 'd', 10 => 'e');
$tab_exception = array ('e' =>'z', 'd' =>'c');

Code:

1
2
$tab = array (2 => 'z', 4 => 'b', 6 => 'c', 8 => 'd', 10 => 'e');
$tab_exception = array ('e' =>'a', 'd' =>'c');

Citation:

Le tableau est trié.

On n'est pas plus du tout dans ton besoin de départ qui était de trier selon un ordre spécifique.
Finalement tu veux juste intervertir des éléments deux par deux.

Code:

1
2
3
4
5
6
7
8
9
10
$tab = array ('a', 'b', 'c', 'd', 'e' , 'z');
$tab_exception = array ('e' =>'a', 'd' =>'c');
foreach($tab as $clef=>$letter) {
	if (isset($tab_exception[$letter])) {
		$nouvelle_clef = array_search($tab_exception[$letter], $tab);
		$tab[$nouvelle_clef] = $letter;
		$tab[$clef] = $tab_exception[$letter];
	}
}
print_r($tab);

29/01/2013, 21h18
boteha

Bonsoir,

Encore merci de ton intérêt.

Les deux cas que tu cites qui provoqueraient des erreurs sont impossibles dans la réalité de mon programme.

array_search () est effectivement plus simple que array_keys ().

À cette heure j'ai un peu de mal à comprendre ta fonction.

Tu places bien 'e' à la place de 'a' mais ce faisant tu écrases 'a' et je ne vois où tu le replaces avec $tab[$clef] = $tab_exception[$letter];

$clef = 'e';

Tu passes de 0 à 'e', non ?
Et je vois pas trop comment le classement est cohérent.
29/01/2013, 21h33
sabotage

$clef vaut 4; c'est $letter qui vaut 'e'

Citation:

Les deux cas que tu cites qui provoqueraient des erreurs sont impossibles dans la réalité de mon programme.

Si depuis le début tu nous avais dit la réalité de tes hypothèses aussi ...

Citation:

Et je vois pas trop comment le classement est cohérent.

comment ça cohérent ?
29/01/2013, 22h06
boteha

Bonsoir Sabotage,

Encore merci.

Citation:

Si depuis le début tu nous avais dit la réalité de tes hypothèses aussi ...

Mon premier post me semble clair, mais c'est vrai que le besoin est tordu.

Je me suis sans doute mal exprimé, mais il me semble que tu n'as pas compris que la question est de placer 'e' AVANT 'a', mais pas à la place de 'a".

$tab = array ('a', 'b', 'c', 'd', 'e');
$tab_exception = array ('e' =>'a');

Il faut obtenir :
$tab = array ('e', 'a', 'b', 'c', 'd');

Alors qu'il me semble que ta fonction va créer :
$tab = array ('e', 'b', 'c', 'd', 'a');

D'où mon idée toute simple de clés paires qui te permettent d'utiliser les clés impaires pour le replacement sans écraser la valeur devant laquelle tu replaces.

Citation:

Mon premier post me semble clair

Je pensais que c'était une vue simplifiée de ton besoin ; je n'imaginais pas que tu souhaitais réellement reclasser un alphabet.

Après on peut imaginer plein de choses et sur une source si réduite, la performance joue peu.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 <?php $tab = array ('a', 'b', 'c', 'd', 'e' , 'z'); $tab_exception = array ('e' =>'a', 'd' =>'c'); foreach($tab as $clef=>$letter) { if (isset($tab_exception[$letter])) { $nouvelle_clef = array_search($tab_exception[$letter], $new_tab); $new_tab = array_merge(array_slice($new_tab, 0, $nouvelle_clef), (array)$letter, array_slice($new_tab, $nouvelle_clef)); } else { $new_tab[] = $letter; } } print_r($new_tab);

30/01/2013, 00h03
boteha

Bonsoir,

Citation:

Je pensais que c'était une vue simplifiée de ton besoin ; je n'imaginais pas que tu souhaitais réellement reclasser un alphabet.

Les tableaux réels sont composés d'une vingtaine de chaînes de 3 caractères, cela revient au même.

Merci pour ta fonction.