[java] fermare un ciclo infinito

[McLain]

ciao a tutti, e bentornati dalle ferie, se ne avete avute (beati voi)

ho un dubbio/problema in java:
con un programmino volevo estrarre tutte le possibili combinazioni di una parola, estraendone quante possibili, anche senza senso, insomma tutti gli anagrammi di una stringa.
ma come faccio a fermare il ciclo che mischia le lettere una volta che ha trovato tutte le combinazioni? cioè, come faccio a dirgli che le ha trovate?
io già controllo in un vettore temporaneo se la combinazione è già stata estratta, in tal caso prosegue per trovarne un'altra.. ma così credo andrebbe avanti all'infinito..

speriamo mi sappiate dare una mano, intanto buon weekend.
ciao.

[NøName_121]

per gli anagrammi di una parola se non ricordo male, la formula statistica è (con ripetizione):
lettereCheFormanoLaParola^lettereCheFormanoLaParol a

[McLain]

mm.. forse era quello che temevo..
cioè dovrei prima calcolare quante possibilità ci sono e poi far ripete il ciclo per tante volte??

[Alex'87]

Originariamente inviato da NøName_121
per gli anagrammi di una parola se non ricordo male, la formula statistica è (con ripetizione):
lettereCheFormanoLaParola^lettereCheFormanoLaParol a

Un anagramma non ha ripetizioni, la stessa lettera la si usa una volta sola :master:
Se ricordo bene, la formula di tutte le possibili combinazioni senza ripetizioni è n!, dove n è il numero di caratteri della stringa :master:

Originariamente inviato da McLain
cioè dovrei prima calcolare quante possibilità ci sono e poi far ripete il ciclo per tante volte??

Ehm.. cosa c'è che non va? I cicli for li hanno inventati per un motivo

[NøName_121]

Originariamente inviato da McLain
mm.. forse era quello che temevo..
cioè dovrei prima calcolare quante possibilità ci sono e poi far ripete il ciclo per tante volte??

esattamente..
quale altra via avresti voluto seguire? non credo ne esistano altre.. almeno non me ne vengono in mente :master:

[NøName_121]

Originariamente inviato da Alex'87
Un anagramma non ha ripetizioni, la stessa lettera la si usa una volta sola :master:
Se ricordo bene, la formula di tutte le possibili combinazioni senza ripetizioni è n!

hmm.. si vede che non apro il libro di statistica da un po' ^_^"
credo tu abbia ragione.. il fattoriale..

[McLain]

no no, per carità, nessun problema, credevo semplicemente ci fossero altri modi, ma in effetti questo è il più consono.
casomai la difficoltà aumenta se la parola contiene per due o tre volte la stessa lettera, ma per questo mi arrangio, leggerò qua e là..


un altra cosa: e se volessi estrapolare solo una parte di questa parola, ad esempio trovare tutti i possibili anagrammi di volta in volta ma solo per 4 lettere prese da una parola di 6.. vado sempre di calcolo fattoriale, ma come faccio a non estrapolare più volte le stesse 4 lettere..


si, so che starete pensando se non ho altro di meglio da fare il sabato pomeriggio, ma mi sto rimettendo sotto con java.. mi serve sta roba.. grazie mille intanto

[biagiopas]

forse quello che voleva dire Alex'87

Ehm.. cosa c'è che non va? I cicli for li hanno inventati per un motivo

è che non serve calcolare prima il numero delle permutazioni cioe n!
perchè il problema si risolve direttamente in almeno due modi :

a) con n semplicissimi cicli for annidati
es (in pseudicodice) hai l'array di caratteri

parola = [0]A  [1]B  [2]C  [3]D
n-> 4
for(x 0..3) for(y 1..3) for(j 2..3) for(k 3..3) 
anagramma = parola[x] + parola[y] + parola[j] + parola[k]

(ma non è molto elegante come soluzione specie se la il numero dei caratteri n è arbitrario :berto: :master: :ignore: .... VVoVe: )

b) con una procedura ricorsiva


per le lettere ripetute basta filtrare i risultati per eliminare i doppioni , è la soluzione piu semplice non so se ce ne sono altre

di sicuro cercando troverai il codice o anche nei manuali di programmazione

[R@ve M@ster]

Per quanto riguarda il numero di cicli da effettuare occorre distinguere se la parola ha lettere tutte diverse oppure se alcune compaiono più di una volta. Se non ci sono lettere ripetute allora va bene n!

Se ci sono lettere ripetute ci saranno sicuramente alcuni anagrammi che verrebbero conteggiati più di una volta. Ad esempio nella parola JAVA c'è un anagramma che si otterrebbe scambiando l'ultima A con la seconda...ottenendo ovviamente di nuovo la parola JAVA. Per evitare di conteggiare anche i duplicati la formula diventa:



____n!___
S1!S2!...Sk!


dove S1, S2,...,Sk rappresentano il numero di quante volte si ripetono determinate lettere. Ad esempio, con la parola PAPPAGALLO:

_10!__
3!3!2!

perchè ci sono tre A, tre P e due L

[biagiopas]

____n!___
S1!S2!...Sk!

è esatto , ma questa formula serve solo a sapere qul'è il numero degli anagrammi non a trovarli

per trovarli il metodo piu naturale (per quel poco che so) è quello sopra descritto che comporta l'esecuzione di n! cicli e il filtraggio dei risultati

se avete una procedura con
____n!___ cicli fatemi sapere
S1!S2!...Sk!