Hola, usa recursividad.
la idea es fijar un numero y rotar los siguientes
digamos n=3
1,2,3 entonces empiezas a rotar
2,3,1 y 3,1,2...y en cada uno de ellos, rotas solo los siguientes numeros
osea en 1,2,3 recursivamente llamas una funcion con 2,3 luego te quedara 2,3 y 3,2 y cuando lo concatenas te da
1,2,3 y 1,3,2
lo mismo haces en cada rotacion y te dan todas las permutaciones.
el codigo quedaria algo como
func(Conjunto s,Conjunto p){
if(size(s)==0){
imprimir(p);
retornar;
}
for(int n = 0;n<size(s);n++){
int r = s[0];
p.add(r);
s.delete(0);
func(s,p);
s = s.subconjunto(1,size(s)).add(r);
}
}
Esto no es ningun lenguaje, pero pense que asi lo entenderias, es notacion sobre conjuntos pero escrita

.
Si notas, en S tendras los numeros naturales del 1 al n, y en p iras guardando la recursion.
pd: te servira tambien ver esto
http://en.wikipedia.org/wiki/Factorial_number_system