Java查找字符串的所有排列
要解决此问题，我们需要了解回溯的概念。
根据回溯算法:
将字符固定在第一位置，然后将其余字符替换为第一字符。像在ABC中一样，在第一次迭代中，通过分别将A与A，B和C交换来形成三个字符串: ABC，BAC和CBA。
对其余字符重复步骤1，例如修复第二个字符B等。
现在再次交换以返回上一个位置。例如，从ABC，我们通过再次固定B组成ABC，然后回溯到先前的位置并与C交换B。因此，现在我们有了ABC和ACB。
对BAC和CBA重复这些步骤，以获取所有排列。
要进行编程，请遵循以下算法:
算法
main()
步骤1: START
步骤2: 定义字符串str ="ABC"。
步骤3: len = str.length()。
步骤4: 打印"字符串的所有排列都是: "
步骤5: 调用generatePermutation(str，0，len)。
步骤6: END
generatePermutation (字符串str，int开头，int结束)
步骤1: START
步骤2: if(start == end-1)
PRINT str
否则请转到步骤3
步骤3: SET i =start。直到i < end，将步骤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: END
swapString (string a，int i，int j)
步骤1: START
步骤2: char [] b = a.toCharArray()
步骤3: 定义字符
步骤4: ch = b [i]
步骤5: b [i] = b [j]
步骤6: b [j] = ch
步骤7: 返回String.ValueOf(b)
步骤8: END
程序:
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
