| sorlaker |
10-08-2012 06:24 PM |
How to make anagram using backtracking?
Can anyone help me figure out this?
This is my code :
Code:
import java.util.Scanner;
class Permutar{
public static String auxWord;
public static int[] candidates = null;
public static void main(String[] args){
Scanner e = new Scanner(System.in);
String palavra = e.nextLine();
auxWord = palavra;
permutacao(palavra);
bt();
}
public static void bt(){
candidates = new int[auxWord.length()];
for (int i = 0; i < auxWord.length(); i++){
for (int a = 0; a < auxWord.length(); a++){
candidates[a] = -1;
}
candidates[0] = i;
//System.out.println("oi");
bt2();
}
}
public static void bt2(){
if (!accept()) return;
if (isFull()){
show();
//candidates[2] = -1;
//candidates[1] = -1;
return;
}
for (int i = 0; i < auxWord.length(); i++){
//System.out.println("oi2");
if (add(i)){
showL();
bt2();
showL();}
}
return;
}
public static boolean add(int n){
int i;
for (i = 0; i < auxWord.length(); i++){
if (candidates[i] == -1) break;
}
if (i == auxWord.length()){
return false;
}else{
candidates[i] = n;
return true;
}
}
public static boolean isFull(){
if (candidates == null) return false;
for (int i = 0; i < candidates.length; i++){
if (candidates[i] == -1) return false;
}
return true;
}
public static void showL(){
for (int i = 0; i < auxWord.length(); i++){
System.out.print(candidates[i]+" ");
}
System.out.println();
}
public static void show(){
for (int i = 0; i < auxWord.length(); i++){
System.out.print(auxWord.charAt(candidates[i]));
}
System.out.println();
}
public static void permutacao(String palavra){
int quant = palavra.length();
int valor = 1;
for (int i = quant; i > 0; i--){
valor *= i;
}
System.out.println("Permutacao de "+palavra+" ("+quant+" elementos). "+quant+"! = "+valor);
}
public static boolean accept(){
for (int j = 0; j < auxWord.length(); j++){
for (int k = 0; k < auxWord.length(); k++){
if (j != k && candidates[j] == candidates[k] && candidates[j] != -1 && candidates[k] != -1){
candidates[k] = -1;
return false;
}
}
}
return true;
}
}
|
