Ordre lexicographique

Aide à la résolution d'exercices ou de problèmes de niveau supérieur au baccalauréat.

Modérateur : gdm_sco

Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Sumbebkum
Utilisateur confirmé
Utilisateur confirmé
Messages : 26
Inscription : samedi 22 janvier 2011, 22:05
Statut actuel : Lycéen
Localisation : Berlin

Ordre lexicographique

Message par Sumbebkum »

Bonjour,
Je cherche la formule inverse de l'ordre lexicographique, j'ai un un ensemble de la forme $E\coloneqq\[1,N_1\] \times \[1,N_2\] \times \ldots \times \[1,N_d\] \cap \mathbb{N}^d,d \in \mathbb{N}, N_1,N_2,\ldots,N_d \in \mathbb{N}$ que je peux (et dois) ordonné avec l'ordre lexicographique défini comme suit pour $d=2$:
$(x,y)= (x-1)*N_2+y $ pour tout $(x.y) \in E$
et on procède par récurrence pour $d \geq 2$, le cas $d=1$ étant trivial. Il y a le code mathlab en dessous avec $I \in E$ et $B = (N_1,N_2,\ldots,N_d)$:

Code : Tout sélectionner

function [x] = Lex(I,B)

[d,c]=size(I);
    x = I(1,1);
if [d,c]==size(B)
    for i=1:(d-1)
        x = (x-1)*B(i+1,1)+I(i+1,1);
    end;
else
    x=pi;
end;
return

end; 
Cette fonction est méchamment bijective de $E$ dans $\{1,2,\ldots,(N_1\cdot N_2 \cdots N_d)\}$ du coup elle doit être sympathiquement inversible j'espère :), mais j'avoue que je peine à le trouver explicitement.

Sumbebkum
Utilisateur confirmé
Utilisateur confirmé
Messages : 26
Inscription : samedi 22 janvier 2011, 22:05
Statut actuel : Lycéen
Localisation : Berlin

Re: Ordre lexicographique

Message par Sumbebkum »

pardon je viens de voir que je me suis planté dans l'écriture de $E = [1,N_1]\times[1,N_2]\times\ldots\times[1,N_d]\cap\mathbb{N}^d, N_1,N_2,\ldots,N_d \in \mathbb{N}\backslash\{0\}$

Arthur Accroc
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 131
Inscription : lundi 17 octobre 2005, 20:33

Re: Ordre lexicographique

Message par Arthur Accroc »

Sumbebkum a écrit :pardon je viens de voir que je me suis planté dans l'écriture de $E = [1,N_1]\times[1,N_2]\times\ldots\times[1,N_d]\cap\mathbb{N}^d, N_1,N_2,\ldots,N_d \in \mathbb{N}\backslash\{0\}$
L'image de $(x_1,\dots,x_d)$ par ta fonction est, si je ne me trompe pas,
$$x_1+N_2(x_2-1)+N_2N_3(x_3-1)+\dots+N_2N_3..N_d(x_d-1)$$
qui doit pouvoir se calculer efficacement à l'aide du schéma de Hörner.

Pour la réciproque, il suffit alors de calculer les quotients et restes successifs de ton entier $M$ par les produits $N_2\dots N_i$ (c'est du pseudo-code, je ne connais pas Matlab) :

Code : Tout sélectionner

P=M
pour i de d jusqu'à 2
    x[i] = 1+P/(N[2]N[3]...N[i])
    P = P mod (N[2]N[3]...N[i])
fin_pour
x[1] = P
Ceci te convient-il ?
\bye

Arthur Accroc