Permutação (algoritmo para permutar)

public class Permutacao {
	
	public static void main(String[] args) {
		ArrayList lista = new ArrayList();
		lista.add("1");
		lista.add("2");
		lista.add("3");
		lista.add("4");
		ArrayList lpermutada =permuta(lista);
		for (int i=0;i<lpermutada.size();i++){
			String[]teste=(String[])lpermutada.get(i);
			System.out.print("\n");
			for(int j=0;j<teste.length;j++){
				System.out.print(teste[j]);
			}
		}
		System.exit(0);
	}
	
	private static int fatorial(int num){
		int valor=1;
		for (int i=1;i<=num;i++){
			valor=valor*i;
		}
		return valor;
	}
	
	private static ArrayList permuta(ArrayList lista){
		ArrayList lperm = new ArrayList();
		ArrayList permutacoes = new ArrayList();
		int n=lista.size();
		int nrPerm=fatorial(n);	
		int vaux[]=new int[n-1];
		int posBco[]=new int[n-1];
		for(int i=0;i<n-1;i++){
			vaux[i]=fatorial(n-1-i);
		}
		for(int k=0;k<nrPerm;k++){
			
			for(int i=0;i<n-1;i++){
				posBco[i]=0;
			}
			
			int soma_k=k;			
			int multiplicando=n-1;
			int indice=0;
			while(soma_k>0){
				int multiplicacao=vaux[indice]*multiplicando;
				if(multiplicacao<=soma_k){
					soma_k=soma_k-multiplicacao;
					posBco[indice]=multiplicando;
					multiplicando=n-1;
					indice++;
				}else{
					multiplicando--;
					if(multiplicando==0){
						indice++;
						multiplicando=n-1;
					}
				}
			}
			lperm.add(posBco.clone());
		}
		//inicia a permutação
		for(int k=0;k<lperm.size();k++){
			int indice=n-1;
			int[]posicoes=(int[])lperm.get(k);
			String [] individuo = new String[n];
			for(int i=0;i<n;i++){
				individuo[i]="";
			}
			int id=0;
			for(int i=0;i<posicoes.length;i++){
				int posicao=posicoes[i];
				int vazio=0;
				while(vazio<posicao){
					if(individuo[id].equals("")){
						vazio++;
					}
					id++;
				}
				while(individuo[id].equals("")==false){
					id++;
				}
				individuo[id]=(String)lista.get(indice);
				id=0;
				while(individuo[id].equals("")==false){
					id++;
				}
				indice--;
			}
			//último
			for(int i=0;i<individuo.length;i++){
				if(individuo[i].equals("")){
					individuo[i]=(String)lista.get(0);
				}
			}
			
			permutacoes.add(individuo.clone());
		}
		return permutacoes;
	}

}