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

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

根据回溯算法

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

对于编程，请遵循以下算法

算法

main()

• 步骤 1： 开始
• 步骤 2： 定义字符串 str = "ABC"。
• 步骤 3： len = str.length()。
• 步骤 4： 打印 "字符串的所有排列是："
• 步骤 5： 调用 generatePermutation(str, 0, len)。
• 步骤 6： 结束

generatePermutation(String str, int start, int end)

• 步骤 1： 开始
• 步骤 2： if(start==end-1)
  打印 str
  否则转到步骤 3
• 步骤 3： 设置 i = start。重复步骤 4 到步骤 7，直到 i<end。
• 步骤 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： 定义 char ch
• 步骤 4： ch =b[i]
• 步骤 5： b[i] = b[j]
• 步骤 6： b[j] = ch
• 步骤 7： 返回 String.ValueOf(b)
• 步骤8： 结束

程序

输出

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