Nome:

permutadismuta
Download: Codice sorgente (in C) Eseguibile (compilato per Linux su Pentium I) Eseguibile (compilato per Win 2000 su Pentium III)
Retroscena matematico: Tutti sanno cosa sono le permutazioni: se prendo una stringa (composta nel nostro caso da caratteri ASCII), le permutazioni sono i possibili modi in cui posso riordinare la stringa scambiando di posto gli elementi: in parole povere gli anagrammi. Si chiamano invece dismutazioni, in base a una convenzione decisamente molto meno diffusa, le permutazioni che cambiano di posto tutti gli elementi della stringa.

Ad esempio se la stringa iniziale è "ciao", "iaco" è una permutazione ma non una dismutazione, perché la lettera "o" è sempre al quarto posto.

Chiunque abbia mai studiato un briciolo di calcolo combinatorio impara presto (e la dimostrazione è semplicissima) che le permutazioni di n elementi sono n! (n fattoriale, non "incredibile, sono proprio n!"). Sono stato spinto alla scrittura di questo semplicissimo programmino dal fatto che ignoravo, e tutt'ora ignoro, una formula per conoscere le dismutazioni di n elementi. Per cui mi sono detto "io le faccio tutte, le conto e vediamo se salta fuori qualcosa". Non è saltato fuori niente, il numero di dismutazioni risultante da tentativi pratici non mi ha illuminato. E probabilmente la formula c'è già e io non la conosco (la conosci tu, o sporadico lettore di questa pagina? E dimmela!). Comunque il programma ormai c'è, ed è buono per cercare anagrammi del vostro nome.

P.S: volete che il programma vi stampi gli anagrammi in ordine alfabetico? Niente di più semplice: invece di scrivere la vostra stringa normalmente, scrivetela già anagrammata in modo che i caratteri siano in ordine alfabetico.

Aggiornamento del 23/09/2005: uno sporadico lettore si è fatto vivo e mi ha consigliato questa pagina in cui viene descritta la formula per contare le dismutazioni.

Aggiornamento del 24/08/2008: la pagina sopra è scomparsa da tempo, ma ho scritto il risultato ed una dimostrazione qui.
Funzionamento:

La funzione main si occupa prima di tutto dell'input dell'utente: chiede se si vuole le permutazioni o le dismutazioni, di quanti elementi e se le si vuole stampate a video; indi chiama la funzione parti (voce del verbo "partire") che inizializza la stringa da anagrammare con i caratteri inseriti dall'utente ed eventualmente altri e che a sua volta chiama la funzione vedimpo, la funzione ricorsiva che è i nucleo del programma, e che opera su un array di numeri da 0 a "enne".

Vedimpo riceve sempre nella variabile "stadio" la casella su cui operare (è 0 quando viene chiamata da parti) e, supponendo che le caselle precedenti "stadio" siano già state sistemate, sistema la casella "stadio" in tutti i modi possibili e poi richiama se stessa con uno stadio in più.

"Tutti i modi possibili" significa che se c'è un numero da 0 a "enne" che

- non figuri nelle caselle precedenti,

- se il programma sta funzionando in modalità dismutazioni, non sia uguale al numero dello stadio,

allora quello è un "modo possibile".

Se poi vedimpo viene chiamata con "stadio"="enne", significa che "enne" stadi sono già stati sistemati, ovvero che la stringa anagrammata è completa. Solo a questo punto viene considerata la stringa eventualmente immessa dall'utente, che viene stampata nell'ordine in cui sono i numeri da 0 a "enne" nell'array di numeri.

Note tecniche: - La fase di input delle scelte iniziali è l'unica cosa che ancora scoccia. Infatti mi sono accorto che la funzione scanf fa casino con i caratteri, perché interpreta come carattere l'andata a capo dello scanf precedente. Così ho dovuto mettere, per ogni carattere da inputtare, 2 funzioni scanf, di cui solo la seconda è quella buona. Solo che così se per sbaglio date in input una risposta con un numero pari di caratteri (comunque una risposta valida ha un solo carattere) si entra in un loop da cui si può uscire solo riimmettendo un numero pari di caratteri. Se qualcuno sa spiegarmi come diavolo si può condurre gli scanf a trattare in modo dignitoso i caratteri, lo faccia). La richiesta vale anche se qualcuno sa di una funzione tipo getchar che però non aspetti un invio per ricevere i caratteri da tastiera.

- Aggiornamento del 24/08/2008: Il codice sorgente è ora ampiamente commentato.