verifica anagramma e permutazione casuale

[WarDuck]

Originariamente inviato da !fazz

per la questione della tabella ascii, a parte che una sottomano serve sempre

comunque basta ricordarsi che
A è 65
a è 97
e il 32 non è altro che la differenza


per la laboriosità mi sembra molto più laborioso il tuo metodo tra ordinamenti e confronti vari oltre che computazionalmente parlando senza senso: consumi una cifra di tempo di calcolo tra (inutili )ordinamenti ecc ecc dimenticantoti della definizione di anagramma

una stringa è un anagramma di un altra se e solo contiene ogni carattere ripetuto lo stesso numero di volte

se non ti è chiaro fatto con i numeri avresti potuto farlo con un case switch sul carattere ma sicuramente è più giusto che fare il casino che stai facendo
tra ordinamenti e permutazioni varie il tuo algoritmo ha complessità troppo elevata

ricorda sempre una delle regole principe della programmazione: il KISS



riguardo alle permutazioni: devi rifare tutta la funzione visto che di casuale non hai nulla devi usare il random

Non sono d'accordo, il ragazzo deve risolvere il problema prima di tutto, ed ha perfettamente senso ordinare le due stringhe per verificare se sono anagrammi, dal momento che in un'anagramma è proprio la posizione a fare la differenza.

ordinato -> adinoort
tanordio -> adinoort

Quindi le due parole sono anagrammi.

In realtà se ci pensi bene quello che proponi tu non è nient'altro che un ordinamento Integer Sort O(n) applicato ai caratteri (che sono sempre interi dal nostro punto di vista) .

Notare anche che per piccoli numeri un ordinamento O(n^2) si comporta meglio di altri e che comunque su piccoli set di dati la differenza è trascurabile.

Ogni algoritmo va applicato in base anche al contesto e non solo perché sulla carta è più efficiente...

[mistergks]

Originariamente inviato da __ZERO_UNO__

Per la permutazione potresti usare questo algoritmo:
ammesso che v sia l'array di caratteri o una stringa

// sono suff. length(v) - 1 scambi. Il primo elem. di v ha indice 1
for k = length(v) downto 2 do 
  // numero casuale in [0,1] o (0,1), è lo stesso.
  u = rand(); 
  // indice casuale in {1,...,k}.
  // Attenzione, Int sta per parte intera, non arrotondamento.
  i = Int(u*k) + 1; 
  // scambia l'elem in posizione i con quello in pos k
  swap(v[i], v[k]); 
end

non ho ben capito...potresti mostrarmi codice c++?o magari c..

[__ZERO_UNO__]

Ti ho scritto lo pseudo-codice per non darti la pappa pronta e imparare a farlo da solo.Non capisco come del codice in c++ possa essere più chiaro dello pseudo-codice.Se non hai capito qualcosa in particolare chiedilo.
Comunque... Abbiamo n posizione nell'array. Parto dal fondo, cioè da n, e scelgo in modo casuale quale lettera mettere in n. Ogni lettera della parola ha uguale probabilità di occupare quella posizione. Dopo devo scegliere una lettera, fra quelle che sono rimaste, da mettere nella posizione n-1. Fatto questo devo scegliere una lettera, fra quelle rimaste, da mettere nella posizione n-2. Si prosegue cosi fino all'esaurimento delle lettere.
k è la posizione corrente in cui devo mettere la lettera e, l'insieme {1, 2, ..., k} di indici, le posizioni delle lettere possibili da scegliere.




u = rand();
i = Int(u*k) + 1;

è un modo per generare una variabile aleatoria con distribuzione discreta uniforme su k elementi.