Java backtraking problem

Hey guys. I've been strugling with a backtraking problem for hours. Can anyone lend me a hand? Here is the problem:

n camels numbered from 1 to n are the arranged order. I want to rearrange so that each camel has a diferent camel in front.

This is what I have so far:

import java.util.*;

public class NCamile{
static int size;
static int count;
static char[] arrN= new char[100];

public static void main(String[] args){
    System.out.print("Enter word: ");
    String numar = getInt();
    size = numar.length();
    count=0;

    for(int i=0; i < size ; i++){
        arrN[i] = numar.charAt(i);
    }
backtraking(size);  
}

public static void backtraking(int newsize){

    if (newsize == 1){
        return;
    }

 开发者_如何学运维   for(int i=0 ; i < newsize; i++){

        backtraking(newsize - 1);


            if(newsize == 2 ){

                    display();

                }




        rotate(newsize);
    }

}
public static void rotate(int newsize){
    int position = size - newsize;

    for(int i = position + 1; i < newsize; i++){
        char gigi;
        gigi = arrN[i - 1];
        arrN[i - 1] = arrN [i];
        arrN[i] = gigi;
    }
}

public static void display(){
    if (count < 9){
        System.out.print(" ");
    }

    System.out.print(++count+ ")" + " ");

    for(int i = 0 ; i < size ; i++)
        System.out.print(arrN[i]);
        System.out.print(" ");


    if(count % 10 == 0){
        System.out.println(" ");
    }
}


public static String getInt(){
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    return s;

}

}

With this, the algorithems show me every posible solution to rearrange a string, but it dosen't respect the last condition of the problem. I've tried ading this:

for(int j = 0 ; j < size ; j++){

   if (array[j] !=[array[j + 1] )
      display()
}

But after I added it I got about 10 times more displayed words then it should have shown me

Can anyone give me an idea on what should I do?

---

If you're only asked to insure that

i) a single new arrangement is produced, and

ii)that new arrangement must satisfy the condition that each camel follows a camel different from the one it followed in the original arrangement,

then you can easily satisfy this just by reversing the list of camels.

---

Surely this is not optimized solution, but for simply gettin result I would consider checking all of the permutations. Method producing every permutation wouldn't be hard to write (see e.g. String permutation) and checking if some camel has the same backtraced won't be any effort at all.

--- edit So... Few things mended, few not: I worked on String, not char array. Char array is completely misunderstand in this problem. It's better to use String object (cause in fact, String is char array) or int array (this have been hard to me, cause I haven't found any permutation method to be applied with such parameter). So the main method looks now:

private static String word;

public static void main(String[] args)
{
    System.out.print("Enter word: ");
    Scanner scan = new Scanner(System.in);
    word = scan.next();
    permutation(word);
}

I deleted your class variables (length, count, etc...) cause they are unnecessary right now. Writing out String is quite simple and if you would like to change output format - use String.length property instead.

Permutation method is copied from mentioned source, and little modified. It looks following:

public static void permutation(String s)
{
    permutation("", s);
}

private static void permutation(String prefix, String s)
{
    int n = s.length();
    if (n == 0)
            {
        if (camelFit(prefix))
            System.out.println(prefix);
            }
    else
    {
        for (int i = 0; i < n; i++)
            permutation(prefix + s.charAt(i),
                    s.substring(0, i) + s.substring(i + 1, n));
    }

}

if you would uncomment line checking if (camelFit (prefix)) it would display every permutation of input String. But! We would like to print only these camel chains, which fits problem conditions. How do we check if given chain is so? Simple method:

private static boolean camelFit(String prefix)
{
    for (int i = 0; i < word.length() - 1; i++)
    {
        char camel = word.charAt(i);
        char camelFollow = word.charAt(i+1);
        for (int j = 0; j < prefix.length() - 1; j++)
        {
            if (prefix.charAt(j)==camel && prefix.charAt(j+1)==camelFollow)
            {
                return false;
            }
        }
    }
    return true;
}

Maybe not so simple, because we have to check every pair of input chain (every follower and followed) with every pair of output chain. If there isn't any match between any two pairs - given chain is fine.

Please notice, that this solution is absolutely non-optimized. Finding permutations is O(n!) complexity and checking pairs is O(n^2) complexity. Final complexity is O(n^2)*O(n!) so very, very high.