Come "scegliere" tra le permutazioni di n elementi
Buongiorno a tutti , non so se questa è la sezione giusta dove postare. Il problema è di calcolo combinatorio ed è il seguente.
Se ho ho un insieme di n elementi come posso sapere quante sono le permutazioni di questi elementi "abbastanza diverse"(abbastanza quanto voglio io, ovviamente ). Ovviamente il numero totale di permutazioni di n elementi è n !
Ma a me interessa "scremare" queste permutazioni come voglio io.
Cioè io ho un problema applicativo che riguarda un insieme di 6 elementi, {a,b,c,d,e,f} da riordinare nella maniera "più diversa possibile", in maniera che anche sottosequenze ordinate si mantengano il meno possibile( sempre a mio piacere). Quindi mantenendo l'esempio con 6 elementi, se una permutazione possibile è (a,b,c,d,e,f), non mi interessano permutazioni del tipo (b,c,d,e,f,a), (c,d,e,f,a,b), cioè ordinamenti che sono ciclicamente uguali al primo. Così per ogni permutazione "abbastanza "(abbastanza quanto voglio io) diversa. Cioè se ho (d,b,e,a,f,c) , non mi interessano le permutazioni (b,e,a,f,c,d) o (c,d,b,e,a,f). Così anche per le sotto permutazioni" più numerose" ( nel mio esempio potrebbero essere quelle di quattro elementi ) che "si muovano" nella permutazione più grande (di 6 elementi nell'esempio) . Prendendo l'esempio di prima se ho (b,e,a,f,c,d) la permutazione che scambia solo 2 elementi (d,e,a,f,c,b) voglio poterla escludere dal conto se lo decido.
Spero di non essere stato prolisso e mi scuso se non sono stato chiaro.
Grazie a tutti per l'aiuto
Se ho ho un insieme di n elementi come posso sapere quante sono le permutazioni di questi elementi "abbastanza diverse"(abbastanza quanto voglio io, ovviamente ). Ovviamente il numero totale di permutazioni di n elementi è n !
Ma a me interessa "scremare" queste permutazioni come voglio io.
Cioè io ho un problema applicativo che riguarda un insieme di 6 elementi, {a,b,c,d,e,f} da riordinare nella maniera "più diversa possibile", in maniera che anche sottosequenze ordinate si mantengano il meno possibile( sempre a mio piacere). Quindi mantenendo l'esempio con 6 elementi, se una permutazione possibile è (a,b,c,d,e,f), non mi interessano permutazioni del tipo (b,c,d,e,f,a), (c,d,e,f,a,b), cioè ordinamenti che sono ciclicamente uguali al primo. Così per ogni permutazione "abbastanza "(abbastanza quanto voglio io) diversa. Cioè se ho (d,b,e,a,f,c) , non mi interessano le permutazioni (b,e,a,f,c,d) o (c,d,b,e,a,f). Così anche per le sotto permutazioni" più numerose" ( nel mio esempio potrebbero essere quelle di quattro elementi ) che "si muovano" nella permutazione più grande (di 6 elementi nell'esempio) . Prendendo l'esempio di prima se ho (b,e,a,f,c,d) la permutazione che scambia solo 2 elementi (d,e,a,f,c,b) voglio poterla escludere dal conto se lo decido.
Spero di non essere stato prolisso e mi scuso se non sono stato chiaro.
Grazie a tutti per l'aiuto
Risposte
basta contare quanti sono i "cicli": sono $n$.
allora il numero di permutazioni "diverse", cioè escludendo i cicli, diventa $frac{n!}{n}=(n-1)!$
Se poi consideri "simili" anche quelle che hanno uno scambio di differenza, credo tu debba contare i possibli scambi. in $n$ elementi hai $frac{n!}{(n-2)!*2!}$ scambi. Quindi partendo dalle $n!$ di partenza te ne ritrovi (secondo me):
$frac{frac{n!}{frac{n!}{(n-2)!*2!}}}{n}$
allora il numero di permutazioni "diverse", cioè escludendo i cicli, diventa $frac{n!}{n}=(n-1)!$
Se poi consideri "simili" anche quelle che hanno uno scambio di differenza, credo tu debba contare i possibli scambi. in $n$ elementi hai $frac{n!}{(n-2)!*2!}$ scambi. Quindi partendo dalle $n!$ di partenza te ne ritrovi (secondo me):
$frac{frac{n!}{frac{n!}{(n-2)!*2!}}}{n}$
Cioè $frac{2*(n-2)!}{n}$
ok grazie ...ci devo pensare un attimo 
Secondo me però dovresti prima definire chiaramente cosa intendi per "abbastanza diversa" altrimenti qualsiasi proposta risolutiva rimarrebbe ambigua ...IMHO
Cordialmente, Alex
Cordialmente, Alex
sono quelle in cui anche gli ordinamenti all'interno di due permutazioni distinte si ripetono.Secondo questo criterio (a,c,d,b,e,f) (a,e,c,d,b,f) (a,e,f,c,d,b) sono troppo simili(ma posso decidere il livello di "somiglianza" di volta in volta) o non abbastanza diverse visto che si mantiene il ciclo (c,d,b).Onestamente non so se sono abbastanza rigoroso...
Non credo ... 
... prima di tutto può darsi che cambiando il "livello di somiglianza" possa cambiare il metodo risolutivo e poi sarebbe da capire cosa intendi per "ciclo" perché qualsiasi sequenza può esser un "ciclo", per esempio $f,a,c$ in $(d,e,f,a,c,b), (f,a,c,b,d,e), (e,d,b,f,a,c)$ ...
Dovresti prendere dei casi "precisi" di quello che ti interessa ...
... prima di tutto può darsi che cambiando il "livello di somiglianza" possa cambiare il metodo risolutivo e poi sarebbe da capire cosa intendi per "ciclo" perché qualsiasi sequenza può esser un "ciclo", per esempio $f,a,c$ in $(d,e,f,a,c,b), (f,a,c,b,d,e), (e,d,b,f,a,c)$ ...Dovresti prendere dei casi "precisi" di quello che ti interessa ...
hai ragione non sono cicli rigorosamente intesi che possono essere formati anche da elementi non contigui... io intendo sequenze ordinate uguali formate da elementi contigui all'interno si due permutaIoni distinte come hai esemplificato tu.
cioè lo scopo era capire come escludere le permutazioni troppo simili nel senso spiegato sopra o meglio prenderne un solo esemplare
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo