Newsgroup: it.comp.www.php
Titolo: Problema: permutazioni con ripetizione... come fare ?

Devo scrivere una funzione in PHP che mi trovi
tutte le possibili permutazioni di un insieme di elementi dei quali alcuni
sono uguali tra loro.
Esempio, trovare tutti gli anagrammi della parola "ARARE".
Se le lettere fossero tutte diverse gli anagrammi sarebbero 5! ma ci sono 2
A e 2 R e in questo
caso sono molti meno.
Diciamo che gli elementi da permutare si trovano in un vettore elementi(n).
Ringrazio tutti quelli che mi aiuteranno.
Ciao

A e 2 R e in questo caso sono molti meno.
Direi che ti serve, per prima cosa, un algoritmo.
Un algoritmo ricorsivo non sarebbe male. Per assicurarti di non prendere
due volte lo stesso anagramma dovresti trovare il modo di assicurare una
metrica globale (per esempio: ALFA viene prima di FALA, come FALA verra'
prima di LAFA). Poi basta che ogni anagramma sia "minore" del successivo
in modo stretto.
Per assicurarti di non saltare anagrammi dovresti trovare il "mutamento"
che determina la minima variazione del valore metrico dei risultati. Per
esempio, LAAF -> LAFA cambia poco, LAAF -> LFAA cambia tanto.
Leonardo

 Leonardo
Quello che dici è sostanzialmente giusto.
Io però vorrei evitare di trovare tutte le permutazioni e poi sopprimere
quelle che non mi interessano perchè in questo modo perdo del prezioso tempo
macchina che per un certo numero di elementi diventa esagerato.
Desidererei invece trovare un algoritmo che generi SOLO i valori che mi
interessano cioè solo quelli distinti.
Io non sono un matematico e forse quello che chiedo non è realizzabile in
pratica...
Grazie comunque per l'interessamento :-)

interessano cioč solo quelli distinti.
Allora togli i duplicati, segnandoti quanti sono, e reintroducili ad
ogni permutazione. Questo costa meno ma rischi lo stesso dei doppi.
	ALFA si comprime in ALF
	ALF -> AALF, ALAF, ALFA
	AFL -> AAFL, AFAL, AFLA
	FAL -> AFAL, FAAL, FALA  (AFAL e' doppio)
	FLA -> AFLA, FALA, FLAA  (AFLA, FALA sono doppi)
	LAF -> ALAF, LAAF, LAFA  (ALAF e' doppio)
	LFA -> ALFA, LAFA, LFAA  (ALFA, LAFA sono doppi)
Per fare prima, questo e' un programma che effettua permutazioni.
===[ cut here ]===
h1HX-`#-@#P[h0PX-00PY-`]-`!-@!PZ=
h*BX-o@P^C0/07C07C07C0/C0/C07CCCC0/CCCC0/C07C07CC0/C0/C=
07C07C0/C0/C07C07C07C07C07CC0/C0/CC07C07C0/CC07CC=
V+~9> ,<Mt%<Zu3C-%//@d$*D*bt-=-*ta8 LM!=
MLH@LE@@@@ANH@LNKKKA@KHNOIKFB@@CODJF@HFAMA@KLNAG@NKANA@OK@@A@
MF@GEIK@@HOCODJKLNKEEA@FEKHFMIK@B@@DKM@LJJCDL@NKOKBBONDKHNLKH
MIMNECEAE@HKOB@GGK@KHD@HNDB@@HNAB@@KNLA@IKHKLNOKLHNGNOOAEKHKL
MJHDBJHDDA@HHD@FDBNHOHHDBKHBOIEBNINIEKECL@EDKI@MLABHEFH@NIHD@
MCLM@J@ADBDCDEDM@J@DBM@J@------------------------------------
Z
===[ cut here ]===
Nell'ultima riga, quella sequenza "ADBDCDED" sono i caratteri che il
programma permuta scritti in lingua farfallina ;-), ciascuno seguito
da una D. Si possono aggiungere fino ad altri 8 caratteri - poi solo
Dio sa cosa succede allo stack.
Leonardo miniatore

macchina che per un certo numero di elementi diventa esagerato.
Beh, l'idea potrebbe essere questa (ieri sera non avevo voglia di
uscire e non c'era niente in tv :-) :
genereremo un albero. La radice è l'insieme delle lettere da
permutare.
Esempio: {a,b,c,a}
Ora, per ogni elemento distinto dell'insieme (il che vorra' dire
considerare a,b e c) generiamo tali foglie:
a{b,c,a}              b{a,c,a}               c{a,b,a)
cioe', ogni foglia contiene l'elemento considerato e l'insieme che
rimane togliendo l'elemento considerato dall'insieme di partenza.
Ogni foglia, a questo punto, diventerà un nodo che avrà delle altre
foglie generate in maniera identica a quanto fatto.
Per es, la foglia b{a,c,a} generera', a sua volta, due foglie:
a{c,a}       c{a,a}
Ad un certo punto, si arriverà alla fine della costruzione
dell'albero, e tale albero avrà tante foglie quante sono le
permutazioni da trovare. Tali permutazioni si ricaveranno
ripercorrendo l'albero dalle foglie alla radice.
Ti consiglio di prenderti un foglio e cercare di costruire l'albero.
Trasformare, poi, il tutto in algoritmo, e' un altro discorso, che
affronterò la prossima serata destinata a diventare noiosa :-)
hint: l'albero potrebbe essere rappresentato da una matrice.
hola
Buttha

 ha scritto nel messaggio
news:3c60dffa...@news.seta.it...

Quello che dici è molto interessante ma non credo di essere in grado di
scrivere l'algoritmo :-( che probabilmente dovrà essere ricorsivo.
Ringrazio tutti quelli che mi hanno aiutato.

scrivere l'algoritmo :-( che probabilmente dovrà essere ricorsivo.
Cmq, sicuramente ne troverai di algoritmi in rete:
ce ne sono almeno 40 di algoritmi per risolvere questa classe di
problemi e, sicuramente, con google o qualche altro motore di ricerca,
e con un po' di pazienza, ne dovresti trovare.
hola
Buttha