Java回溯问题

嘿家伙。几个小时来我一直在努力解决回溯问题。任何人都可以借我一只手吗？问题如下：Java回溯问题

n骆驼编号从1到n是排列顺序。我想重新排列，这样每个骆驼在前面都有不同的骆驼。

这是我到目前为止有：

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; 

} 

}

这样，algorithems告诉我每更多钞票的解决方案重新安排一个字符串，但它这么想的尊重问题的最后一个条件。我试过ading这样的：

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

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

但经过我说这我得到了约10倍的显示的单词，那么它应该显示我

谁能给我我该怎么办的想法？

来源

2011-09-03 user846603

“前面”是否意味着我们只需要将元素更改为左侧？在那种情况下，不会简单地颠倒阵列就会得出答案？ – MAK

没有那个算法必须显示每一个可能的结果。例如，让我们取这个数字：1234下一次显示2不能在1前面3不能在2前面和4前面不能在3前面所以一个 – user846603

@MAK我们不得不倒转第一个元素的数组。因为他说“每个骆驼在前面都有不同的骆驼”。如果不是，最后一只骆驼在前面不会有骆驼。（没有骆驼==不同的骆驼）是假的，我认为是。 –

这当然不是最优化的解决方案，但对于简单的gettin结果，我会考虑检查所有的排列组合。产生每个置换的方法不难写（例如见String permutation）并检查一些骆驼是否有相同的回溯，根本不会有任何努力。

---编辑所以...几件事修补，很少没有：我工作的字符串，而不是字符数组。在这个问题中，char数组完全是误解。最好使用String对象（事实上，String是char数组）或int数组（这对我来说很难，因为我没有找到任何置换方法来应用这样的参数）。所以主要方法现在看起来：

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); 
}

我删除了你的类变量（长度，数量等），因为他们现在是不必要的。写出字符串非常简单，如果您想要更改输出格式，请改为使用String.length属性。

排列方法是从上述源中复制而来的，很少修改。它看起来如下：

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)); 
    } 

}

如果你要取消注释行检查如果（camelFit（前缀））它会显示每个输入字符串的排列。但！我们只想印刷符合问题条件的骆驼链。我们如何检查给定的链是否如此？简单的方法：

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; 
}

也许并非如此简单，因为我们要检查每对输入链（每一个追随者，跟随），每对输出链。如果任何两对之间没有任何匹配 - 给定链很好。

请注意，这个解决方案是绝对没有优化的。查找排列是O（n！）复杂度，检查对是O（n^2）复杂度。最终的复杂性是O（n^2）* O（n！）非常非常高。

来源

2011-09-03 12:40:00

该算法导致每个posbile排列 – user846603

如果你只要求确保

ⅰ）一个单一的新装置被产生，并且

ii）该新的安排必须满足条件，每个骆驼如下从所述一个不同般地它遵循原来的安排，

然后，你可以很容易满足这只是通过颠倒骆驼列表。

来源

2011-09-03 12:41:30 user926600

Java回溯问题

回答

相关问题