Le barème est donné à titre indicatif et est sus­cep­tible d'être adapté. Lisez at­ten­ti­ve­ment les explications. Commentez vos fonctions.

L'objectif est d'écrire un programme en langage C qui détermine si deux mots u et v (des chaînes de caractères) passés en paramètres de la ligne de commande sont des anagrammes l'un de l'autre, c'est-à-dire si en permutant les lettres de l'un d'entre eux, on obtient l'autre :

1. Il existe n ∈ ℕ tel que |u| = |v| = n.
2. Il existe σ ∈ S_n tel que pour tout i ∈ [1, n]  v_σ(i) = u_i.

Dans cette définition, la permutation σ indique où déplacer les lettres de u. La i-ème lettre de u va en position σ(i) dans v, ce que l'on résumera par v = σ(u). Attention aux positions des opérandes dans les expressions. Dans ce qui va suivre u correspond au premier mot sur la ligne de commande et v au second.

Après avoir complété les fonctions du programme anagramme.c à télécharger, et une fois celui-ci compilé par la commande

$ gcc -o anagramme anagramme.c -g -Wall

L'appel

$ ./anagramme NIVELEURS UNIVERSEL

$ σ(NIVELEURS) = UNIVERSEL où σ = [2, 3, 4, 5, 9, 8, 1, 6, 7]

 et l'appel

$ ./anagramme STABILISE LIBANAISE

$ STABILISE et LIBANAISE ne sont pas des anagrammes

Une permutation σ ∈ S_n est codée par un tableau d'entiers non-signés de longueur n + 1 (le type tperm dans le fichier source) de manière à ce que la notation soit conforme à l'écriture mathématique puisqu'il s'agit d'une bijection de l'intervalle [1, n] dans lui-même. La première cellule d'indice 0 du tableau sert alors à ranger la taille n de la permutation. Ainsi la permutation

est codée par le tableau [9₀, 2₁, 3₂, 4₃, 5₄, 9₅, 8₆, 1₇, 6₈, 7₉].

Pour trouver cette permutation rapidement si deux mots sont des anagrammes l'un de l'autre, on trie les lettres de chacun des deux mots (avec la fonction TriAlpha) dans l'ordre alphabétique. Si les deux mots triés sont identiques, les mots sont des anagrammes. Par exemple, le tri des mots NIVELEURS et UNIVERSEL donnent le même mot EEILNRSUV, prouvant que ce sont des anagrammes.

Pour l'exemple, σ₁(NIVELEURS) = EEILNRSUV pour la permutation σ₁ = [5, 3, 9, 2, 4, 1, 8, 6, 7] et σ₂(UNIVERSEL) = EEILNRSUV pour la permutation σ₂ = [8, 5, 3, 9, 2, 6, 7, 1, 4]. On a donc

UNIVERSEL = σ(NIVELEURS)

pour la permutation σ := (σ₂)^-1 o σ₁ = [2, 3, 4, 5, 9, 8, 1, 6, 7]

Il faut noter qu'il n'y a pas unicité de la permutation σ dès qu'un mot contient plusieurs fois une même lettre.

Une adaptation du tri par répartition permet de calculer la permutation inverse σ ^-1 d'une permutation σ telle que σ(mot) = mot_trié. Pour ce faire, on crée un tableau Casiers de 26 listes chaînées, une pour chaque lettre de l'alphabet, dont les cellules contiennent un entier non-signé et le pointeur vers la cellule suivante. La fonction d'adressage est le rang de la lettre dans l'alphabet considéré, i.e. adresse(A) = 0, …, adresse(Z) = 25. Au lieu de ranger chaque lettre du mot dans le casier adressé par le rang de la lettre, on y range la position de la lettre dans le mot.

Par exemple, pour le mot ESSAI, on empile 1 dans le casier n°4 (E), puis on empile successivement 2 et 3 dans le casier n°18 (S) puis 4 dans le casier n° 0 (A) et finalement 5 dans le casier n° 8 (I). En récupérant les entiers des casiers dans l'ordre alphabétique, i.e. en dépilant les valeurs de chaque liste, on obtient la permutation inverse σ^-1 = [4, 1, 5, 3, 2] de la permutation σ = [2, 5, 4, 1, 3] telle que

σ(E₁ S₂ S₃ A₄ I₅) = A₄ E₁ I₅ S₃ S₂

NB. Contrairement au tri par répartition, où les éléments doivent être rajoutés en fin de liste, nécessitant de parcourir toute la liste ou de conserver un pointeur vers la dernière cellule, ici les valeurs dans une même liste chaînée sont les positions d'une même lettre dans le mot, peu importe donc dans quel ordre elles apparaissent pour trier le mot.