Go Back   CodingForums.com > :: Server side development > Java and JSP

Before you post, read our: Rules & Posting Guidelines

Reply
 
Thread Tools Rate Thread
Enjoy an ad free experience by logging in. Not a member yet? Register.
Old 10-08-2012, 06:24 PM   PM User | #1
sorlaker
Regular Coder

 
Join Date: Dec 2009
Posts: 166
Thanks: 23
Thanked 1 Time in 1 Post
sorlaker has a little shameless behaviour in the past
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;
	}
}
sorlaker is offline   Reply With Quote
Reply

Bookmarks

Jump To Top of Thread


Thread Tools
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 04:15 AM.


Advertisement
Log in to turn off these ads.