查找字符串的所有排列的Java程序

1 说明

为了解决这个问题，我们需要了解回溯的概念。

根据回溯算法：

• 将角色固定在第一个位置，然后将其余字符替换为第一个字符。像在ABC中一样，在第一次迭代中，通过分别将A与A，B和C交换来形成三个字符串：ABC，BAC和CBA。
• 对其余字符重复步骤1，例如固定第二个字符B，依此类推。
• 现在再次交换以返回到先前的位置。例如，从ABC，我们通过再次固定B来形成ABC，然后回溯到先前的位置并与C交换B。因此，现在我们有了ABC和ACB。
• 对BAC和CBA重复这些步骤，以获取所有排列。

2 算法思路

main()函数

• 步骤1：开始
• 步骤2：定义字符串str =“ ABC”。
• 步骤3： len = str.length（）。
• 步骤4：打印“All the permutations of the string are:”
• 步骤5：呼叫generatePermutation（str，0，len）。
• 步骤6：结束

generatePermutation(String str, int start, int end)函数

• 步骤1：开始
• 步骤2： if（start == end-1）
  PRINT str
  否则转到步骤3
• 步骤3： SET i =开始。直到i <结束，将步骤4重复到步骤7。
• 步骤4： str = swapstring（str，start，i）。
• 步骤5： generatePermutation（str，start + 1，end）。
• 步骤6： str = swapstring（str，start，i）。
• 步骤7： i = i + 1
• 步骤8：结束

swapString(String a, int i, int j)函数

• 步骤1：开始
• 步骤2： char [] b = a.toCharArray（）
• 步骤3：定义图表
• 步骤4： ch = b [i]
• 步骤5： b [i] = b [j]
• 步骤6： b [j] = ch
• 步骤7：返回String.ValueOf（b）
• 步骤8：结束

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class PermuteString {    
    //Function for swapping the characters at position I with character at position j    
    public static String swapString(String a, int i, int j) {    
        char[] b =a.toCharArray();    
        char ch;    
        ch = b[i];    
        b[i] = b[j];    
        b[j] = ch;    
        return String.valueOf(b);    
    }    
        
    public static void main(String[] args)    
    {    
        String str = "ABC";    
        int len = str.length();    
        System.out.println("All the permutations of the string are: ");    
        generatePermutation(str, 0, len);    
    }    
        
    //Function for generating different permutations of the string    
    public static void generatePermutation(String str, int start, int end)    
    {    
        //Prints the permutations    
        if (start == end-1)    
            System.out.println(str);    
        else    
        {    
            for (int i = start; i < end; i++)    
            {    
                //Swapping the string by fixing a character    
                str = swapString(str,start,i);    
                //Recursively calling function generatePermutation() for rest of the characters     
                generatePermutation(str,start+1,end);    
                //Backtracking and swapping the characters again.    
                str = swapString(str,start,i);    
            }    
        }    
    }    
}    

以上代码输出结果为：

All the permutations of the string are:
ABC
ACB
BAC
BCA
CBA
CAB