Salve, nel mio primo post voglio fare subito i complimenti a tutti...questo forum è di grande aiuto per quelle persone che come me, non sono proprio ferratissime in matematica.
Il mio problema è sapere se è possibile scrivere un programma che ,dopo aver ricevuto in ingresso 2 stringhe di n bit , rispettivamente l'input e l'output di una permutazione "random" , riesca a contare il numero di cicli necessari ad ottenere la stringa di uscita.Vorrei per prima cosa sapere se è possibile contare il numero di cicli, in quanto le mie basi di combinatoria non mi hanno aiutato su questa cosa.Ovviamente non chiedo nessun programma qui a voi, ma semplicemente qualche spiegazione teorica sul fatto che sia possibile o meno.
Grazie a tutti.
Aiuto su cicli e permutazioni
intendi date le stringhe "ABCDE" e "BCDEA" stabilire quanti swap tra due caratetri servono per passare da una all'altra? (in questo caso 4: "BACDE","BCADE","BCDAE","BCDEA")
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
In effetti mi hai fatto venire alcuni dubbi.....Partiamo da una cosa che forse per te è banale ma purtroppo voglio essere sicuro di tutto: che cosa si intende per dimensione di un generico ciclo?Se si intende il numero di elementi coinvolti nel ciclo allora qualcosa l'ho capita.Ma se è così, un K-ciclo (ciclo di dimensione k > 2) può sempre essere espresso come prodotto di trasposizioni (cicli con dimensione 2)???Inoltre, ho letto che, data una permutazione "random" , il numero di cicli che ci si aspetta di trovare in uscita è pari al numero di Stirling (senza segno).Se supponiamo quindi di avere una stringa di n bit , poichè il suddetto numero è approssimabile al LN(2^n), mi aspetto di avere nella stringa di uscita della funzione random proprio questo numero di cicli.Ma......i cicli che dimensione avranno????Non è possibile saperlo?Forse mi sto perdendo.....Infine, c'è differenza nella definizione di cicli dispari e permutazioni dispari?
Concludo (seriamente!!) dicendo che questo argomento mi appassiona davvero tanto.Se ho messo alla prova la vostra pazienza con tutte queste domande vi chiedo scusa e ricordo a tutti che apprezzerei tanto delle risposte a tutte queste domande, ma sopratutto apprezzerei un buon libro o qualche testo in rete dove io possa imparare tutto ciò.
Grazie per la disponibilità.
Concludo (seriamente!!) dicendo che questo argomento mi appassiona davvero tanto.Se ho messo alla prova la vostra pazienza con tutte queste domande vi chiedo scusa e ricordo a tutti che apprezzerei tanto delle risposte a tutte queste domande, ma sopratutto apprezzerei un buon libro o qualche testo in rete dove io possa imparare tutto ciò.
Grazie per la disponibilità.