Spesso quando si lavora su algoritmi che hanno come dati di ingresso una lista di elementi si ha la necessità di testarne il comportamento su tutte le permutazioni possibili dell’insieme di ingresso.

L’algoritmo seguente è probabilmente il più semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi, l’algoritmo analizza semplicemente la permutazione attuale per ricavarne la prossima basandosi sul fatto che le permutazioni devono seguire un ordinamento lessicografico (nel caso numerico qui analizzato ogni permutazione deve essere la minima permutazione maggiore di quella corrente)


    public boolean prossima() {
        int i = len - 1;
        while (i>0 && (elementi[i - 1] >= elementi[i])) {
            i--;
        }
        if(i==0)return false;
        int j = len;
        // (i-1) è l'elemento trovato con il ciclo precedente
        while (elementi[j - 1] < = elementi[i - 1])j--;
        swap(i - 1, j - 1);
        i++;
        j = len;
        //inverto gli elementi tra i due elementi scambiati
        while (i < j) {
            swap(i - 1, j - 1);
            i++;
            j--;
        }
        return true;
    }

considerando la permutazione come un vettore di n elementi numerici l’algoritmo determina la permutazione successiva nel seguente modo:

  1. a partire dall’ultimo elemento scorre l’array cercando il primo elemento preceduto da un elemento minore
  2. se non esiste si è giunti all’ultima permutazione possibile e l’algoritmo deve terminare
  3. se esiste ricomincia a scorrere il vettore dalla fine cercando il primo elemento maggiore all’elemento trovato al punto1
  4. si invertono gli elementi trovati al punto1 e al punto3
  5. se lo scambio non è avvenuto tra elementi di livello minimo (l’ultimo e il penultimo) si ripristina l’ordinamento interno invertendo le posizioni degli elementi che si trovano tra l’elemento trovato al punto1 e quello trovato al punto3
  6. l’algoritmo è molto semplice e molto generico ma non è efficiente, infatti il fatto di dover analizzare a ogni iterazione la struttura attuale del vettore ne incrementa di molto la complessità.

    Un modo per rendere molto più efficiente l’algoritmo è quello di dotare l’algoritmo di un altro vettore che contiene dati sulla struttura attuale del vettore degli elementi in modo da poter determinare velocemente la prossima permutazione.

    Un altro miglioramento notevole si può ottenere evitando che a uno scambio debba seguire una ristrutturazione del vettore, entrambe queste ottimizazioni sono implementate nell algoritmo di Johnson–Trotter

    Continua a leggere…

Inserito da: thedarshan | Giugno 19, 2009

Facebook e l’era degli “asocial” network

Riporto per intero una discussione che ho fatto su facebook e che a un certo punto è stata troncata (spero per problemi di comunicazione), la riporto con tutti gli errori di battitura, mi limito a togliere i nomi degli utenti sostituendoli con le iniziali. mancano almeno due commenti che sono spariti (spero per problemi di comunicazione)

EDIT (15:29):  i commenti saltati sono almeno 3 e uno non è mio…quindi comincio a dubitare dei problemi di comunicazione…

VLS

facebook non è fatto per condividere…
non è un vero social network…
è un estensione digitale delle chiacchiere da bar. un gigantesco bar multimediale dove parli con gente che in realtà non conosci

IC alle 13.29 del 19 giugno

diciamo ke è anke un modo per fare ” curtigghiu “!!

VLS alle 13.58 del 19 giugno

dico che è ESCLUSIVAMENTE un modo per fare curtigghiu.
I gruppi sono inutilizzabili, perche uno finisce per averne troppi e non seguirne nessuno, anche perche non hanno notifiche ne rss.

E’ tutto basato sulla bacheca dove i commenti scivolano via spinti da altro curtigghiu, è impossibile farci una discussione seria e duratura (che duri il tempo necessario per svilupparsi).
Comincio a pensare che il prodotto qualità*quantità dei siti sia costante…lo diceva umberto eco molti anni fà prima che si cominciasse a parlare di web2.0

E una degenerazione: prima un sito lo aveva solo chi sapeva gestirlo, poi si sono diffusi i blog dove anche chi non saprebbe creare o gestire un sito piò averne uno e poi sono arrivati questi social network “asociali” dove anche chi è troppo lagnuso per avere un blog può scrivere e avere un feedback anche se scrive banalità.

MS alle 14.00 del 19 giugno

W il bar!

un ultima cosa, nel caso ci fosse qualche lettore non bilingue:

Curtìgghiu cortile, vicolo; 2. fig chiasso; 3. fig. pettegolezzo

Inserito da: thedarshan | Maggio 12, 2009

Michela Vittoria Brambilla è un ministro del Turismo competente

Di solito non parlo di politica in questo blog, ma questa è un occasione speciale

Il trenta aprile sul televideo rai si poteva leggere questo:

Il ministro della Difesa non fa nomi,ma il collega Calderoli precisa; “Romani, Urso e Castelli saranno viceministri”.
I nomi li avrebbe fatti Berlusconi al Consiglio dei ministri, dicendo che presto diventerebbe ministro Michela Vittoria Brambilla, ora sottosegretario al Turismo.
Il governo ha deciso che il referendum sulla legge elettorale per le politiche si terrà il 21 giugno.

Novità in vista per il governo.”E’ stato annunciato che ci sarà un nuovo ministro e tre viceministri”, dice La Russa,dopo il Consiglio dei ministri nel quale Saglia è stato nominato sottosegretario allo Sviluppo economico al posto di Martinat, morto a marzo.

mmm, Michela Vittoria Brambilla… dove l’ho già vista…ah si…in quel canale sul digitale terrestre…perche sono troppo giovane per aver visto questo programma

Inserito da: thedarshan | Aprile 3, 2009

Eseguire calcoli matematici con Octave online

Octave nasce come clone open source di Matlab, come il programma a cui è ispirato permette di eseguire calcoli numerici anche complessi e come il programma a cui è inspirato (e anche di più)  è goffo e inutile per il calcolo simbolico.

Ho trovato un sito molto utile che permette di eseguire degli script di Octave online, la cosa può rivelarsi molto utile quando capita di dover eseguire calcoli complessi da computer in cui non è installato alcun tipo di software del genere.

Il sito è questo: Online Math Calculator, nel caso non fosse diponibile esiste anche questo.

Inserito da: thedarshan | Aprile 1, 2009

il pesce d’Aprile di Youtube

Oggi youtube ha fatto un pesce d’aprile meraviglioso

pesce d'aprile

pesce d'aprile

si vede tutto al contrario

Inserito da: thedarshan | Marzo 8, 2009

Un semplice generatore di spam con le catene di Markov

Oggi pomeriggio ho fatto una cosa che non facevo da un pò di tempo: Dedicarmi alla Toy-programming ,scrivere un codice assolutamente inutile giusto per il gusto di farlo.

Il codice che ho scritto è un generatore di spam che permette di generare un testo apparentemente sensato a partire da un testo sensato preso come modello senza fare nessun tipo di analisi della sintassi.

Per fare questo ho scritto un algoritmo che sfrutta le catene di Markov.

Questo algoritmo agisce dividendo le singole frasi in due parti: un prefisso formato da un numero costante di parole e un suffisso formato da una singola parola.
L’algoritmo costruisce un testo associando a ogni prefisso un suffisso scelto in maniera casuale tra i suffissi che seguono quel prefisso nel testo originale. La probabilità di estrazione di un suffisso dipende dal numero di occorrenze di quella coppia prefisso-suffisso nel testo originale.

La profondità del prefisso influenza la casualità del testo: un numero basso genera molte possibilità di accoppiamento ma un numero alto genera frasi più verosimili, credo che per la lingua italiana la dimensione ideale del prefisso sia 3.

Malgrado sia molto semplice ,molto stupido e assolutamente incapace di analizzare la sintassi un generatore del genere riesce a costruire testi che sembrano sensati e che riescono a passare attraverso molti filtri antispam e addirittura a scalare le classifiche dei motori di ricerca (avvolte quando cerco qualcosa che effettivamente non esiste su google vado a finire in pagine generate in questo modo).

Per ottenere un risultato verosimile è importante scegliere come modello un testo abbastanza complesso e con parole complicate e ambigue quasi in ogni frase, avrei voluto usare il mio libro di testo di teoria dei segnali ma avrei dovuto passarlo a scanner…quindi ho ripiegato su qualcosa di più semplice: Kant

Dando in pasto all’algoritmo la pedagogia di Kant si ottengono risultati del genere:

Si deve dunque sottoporre i fanciulli si abbiano a trattare come schiavi.  In quanto al rospo, è questo un animale innocuo al pari di una foresta si mantiene diritto, per la distanza, vuoi per la società che si può in certo modo chiamare fisica, bisogna soprattutto curare lo svolgimento della umanità, e far si ch’ella diventi non solo più abile, ma ancora più morale, da ultimo, cosa molto strana che alcuni genitori, dopo aver giudicato con un’occhiata di potervi riuscire senza pericolo. Ma la disciplina consiste semplicemente nello spogliar l’uomo della sua libertà. Fa d’uopo avvezzarsi ai rifiuti, alla resistenza, e va dicendo. La massima tantum scimus quantum memoria tenemus (tanto sappiamo quanto riteniamo a memoria) ha certo la sua ragione l’attira dalla parte opposta. Egli dunque potrebbe divenire moralmente buono o cattivo secondo l’utile proprio. Le massime della. condotta umana vanno desunte dall’uomo stesso. Devesi cercare per tempo a diffidare di questo o di loro stessi.

Continua a leggere…

Visto che alcune persone arrivano a questo blog (in particolare a questo post) cercando la lista completa dei farmaci venduti in italia ho deciso di accontentarli,

La lista completa non si trova online, il database ufficiale (di farmaci e parafarmaci) è aquistabile da agenzie come federfarma, si trova invece la lista completa dei farmaci SOP (Farmaci di fascia C senza obbligo di ricetta medica) e OTC (Farmaci da banco o di automedicazione).

Lista in PDF dal sito dell AIFA (agenzia italiana del farmaco) [DOWNLOAD]

La sezione dedicata del sito paginesanitarie.com contiene un elenco molto dettagliato dei SOP e OTC e delle leggi e decreti che li riguardano  [LINK]

Inserito da: thedarshan | Febbraio 25, 2009

Una classe Java per effettuare il backup di un database Mysql

Quando si sviluppa un applicazione che permette di interagire e modificare un database (quelle che oggi fa tanto figo chiamare CRUD) può essere utile prevedere una funzione che permetta di effettuare velocemente e con un solo click il backup completo dell’intero database (dati, struttura, trigger e stored procedure).

Questa classe fa esattamente questo, e a differenza dei molti snippet che si trovano sul web è completa e autosufficente e documentata con javadoc, necessita soltanto della presenza nel sistema del comando “mysqldump” (presenza che viene verificata dalla classe stessa).

La classe avvia un istanza di mysqldump e permette di salvarne l’output in dei file di testo ,in un unico file zip o eventualmente in una stringa

Spero solo che questo codice non finisca schiaffato in qualche forum che non linka nemmeno il sito, fosse per me estenderei il 41bis ai succhiatori di codice

 Continua a leggere...
Inserito da: thedarshan | Febbraio 13, 2009

Come sono identificati i farmaci in italia

Inserito da: thedarshan | Dicembre 3, 2008

Rinominare le immagini usando la data di scatto come nome

Questo script permette di rinominare le immagini jpeg con metadati exif (quindi quasi tutte le immagini delle fotocamere digitali) in modo che il nome sia la data e l’ora di scatto.

I file vengono rinominati in modo che il nome sia $anno_$mese_$giorno_$ore$minuti_$contatore.jpg in questo modo l’ordinamento lessicografico e quello cronologico corrispondono.

Questo è molto utile per visualizzare le fotografie con player rudimentali che non supportano i metadati exif o l’orinamento per data (tipo la maggior parte dei lettori dvd-dvx).

Lo script usa la libreria exifr, scaricabile comodamente con rubygem (vedi il commento nel codice)

Lo script genera il file backtrack.bat che permette di annullare la rinominazione


#!/usr/bin/ruby
#28/10/2008
require 'rubygems'
require 'exifr' #gem install exifr
files = Dir.glob('*.{jpg,JPG}')

back=File.new("backtrack.bat","w+")
files.each{|nomefile|
    begin
        # l'ordine è invertito per far concidere l'ordinamento
        # alfabetico con quello cronologico
        datastr=EXIFR::JPEG.new(nomefile).date_time.strftime("%y_%m_%d_%H%M")
    rescue
        next
    end

    #controllo l'esistenza di duplicati
    if FileTest.exist?(datastr+".jpg")
        datastr=datastr+"_1"
        while FileTest.exist?(datastr+".jpg")
            datastr=datastr.next
        end
    end
    nuovonome=datastr+".jpg"
    puts "mv '#{nomefile}' '#{nuovonome}'"
    system("mv '#{nomefile}' '#{nuovonome}'")
    back.puts("mv '#{nuovonome}' '#{nomefile}'")
    }
back.close

Articoli precedenti »

Categorie