/*
Algoritmo pensato a partire dalla consegna di un esercitazione
Universitaria (ing.unipd).
Si tratta di una soluzione iterativa. E' incluso l'output del
tempo di esecuzione.
Algoritmo e codice by Oligoatria
*/
public class IterativePermutations
{
public static void main
(String [] args
)
{
if (args.length == 0){
System.
out.
println("Devi dare una stringa come parametro sulla riga di comando");
}
long time
= System.
currentTimeMillis(); // tempo di sistema iniziale
String[] s
= getPermutations
(args
[0
]); // calcolo le permutazioni // richiede un parametro sulla riga di comando
time
= System.
currentTimeMillis() - time
; // tempo di sistema finale
for (int i=0; i<s.length; i++) // stampo ogni permutazione
{
System.
out.
println(i
+": "+s
[i
]);
}
System.
out.
println("Tempo di calcolo: " + time
+ "ms\nNumero di permutazioni: "+s.
length);
}
{
/* Controllo che non ci siano caratteri ripetuti */
for (int i=0; i<s.length(); i++){
for (int j=i+1; j<s.length(); j++)
if (s.charAt(i) == s.charAt(j))
}
/* Creo le stringhe */
int len = fattoriale(s.length());
/* Inizializzo la matrice */
char[][] mat = new char[len][s.length()];
for (int i=0; i<len; i++){
for (int j=0; j<s.length(); j++){
mat[i][j] = ' '; // carattere vuoto
}
}
for (int i=0; i<s.length(); i++) // per ogni carattere della stringa
{
char c = s.charAt(i); // carattere da inserire nel corso dell'iterazione
int fattore = fattoriale( (s.length()-i) -1 ); // il fattore di permanenza della posizione nel ciclo di lavoro attuale
/* Mi porto alla prima posizione libera dell'array corrente, con l'indice k */
int k = getFreePosition(mat[0], 0); // mi restituisce l'indice del primo carattere vuoto, a partire da 0 per ritornare ciclicamente allo stesso valore
if (k<0)
return null;
for (int j=0; j<len;j++) // per ogni permutazione
{
mat[j][k] = c;
if ( (j<len-1)&&( ((j+1) % fattore) == 0) ){
k = getFreePosition(mat[j+1], k+1); // mat[j][k] è sicuramente occupata --> parto da k+1
if (k<0)
return null;
}
}
}
/* Costruisco le stringhe da restituire */
for (int i=0; i<len; i++)
{
}
return as;
}
private static int getFreePosition(char[] s, int start) // restituisce la successiva posizione libera
{
if (start > s.length)
int n = start;
for (; n < s.length; n++) // controllo da start alla fine dell'array
if (s[n] == ' ')
return n;
for (n=0; n < start; n++) // dall'inizio dell'array a start (escluso)
if (s[n] == ' ')
return n;
return -1; // errore: nessuna posizione vuota trovata
}
public static int fattoriale(int n)
{
if (n<0)
if (n <= 1)
return 1;
int val = 1;
for (int i=n; i>1; i--){
val *= i;
}
return val;
}
}