Je pense qu'on peut adapter l'algorithme de comparaison de chaines bruitées.

Soient deux chaines A et B.

On associe des pénalités:

D(A[i]) = poids de disparition d'un élément A[i]
P(B[j]) = poids d'apparition d'un élément B[j]
S(a,b) = poids de substitution de a par b

donc la distance entre deux chaines sera:
(X et Y sont des séquences de caractere, a et b sont des caracteres, e le caractere vide)

d(aX,bY) = min (S(a,b) + d(X,Y),       // c'est soit la substitution de a et b
                D(a) + d(X,bY),       // .. soit disparition de a dans X
                P(b) + d(aX,Y))       // .. soit l'apparition de b dans Y

d(aX,e) = D(a) + d(X,e)
d(e,bY) = P(b) + d(e,Y)
d(e,e) = 0

ce qui donne en une sorte de Ada:

distance(A[1..n], B[1..m],i,j){
    if (j==m+1){
        if(i==n+1){
            return 0;
        }
        return D(A[i]) + distance (A,B,i+1,j);
    } else {
        if (i==n+1){
            return P(B[j]) + distance (A,B,i,j+1);
        }
        return min (S(A[i],B[j]) + distance(A,B,i+1,j+1),
                    D(A[i]) + distance(A,B,i+1,j),
                    P(B[j]) + distance(A,B,i,j+1));
    }
}

avec la programmation dynamique tu peux arriver à quelque chose de polynomial.

Ca c'est l'algo de base.
Maintenant, tu veux qu'il soit possible de trouver une permutation des lettres dans la chaine.
Donc à mon avis, il faut associer une distance du genre
d(aX,Ya) = ...
mais il va sans doute interferer avec d(aX,bY)..
donc il faudra prendre le min des deux. dis = min( d(aX,Ya) , d(aX,bY) )

Je ne garantis pas que ca marche, mais c'est la premiere idée qui me vient à l'esprit.
Je pense que si ca marche, tu tombera toujours sur un truc polynomial.