你知道打印字符串中字符的所有排列用Java如何实现吗?下面给大家带来了具体的实现方法和实现思路。
题目：
输入一个字符串，按照典序打印出这个字符串中字符的所有排列。
例：
输入字符串abc。
打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括了大小写字母。
思路1：
递归算法
对于没有重复值的情况
固定第一个字符，递归取得首位后面的各种字符串组合;
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合;
递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
假如有重复值
因为全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
例abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
但是对bab，第二个数和第三个数不同，那么需要交换，得到bba。
因为这里的bba和开始第一个数与第三个数交换的结果相同了，所以这个方法行不通。
换一种思考方式，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，这个时候因为第三个数等于第二个数，
所以第一个数就不再用与第三个数交换了。
再考虑bab，它的第二个数与第三个数交换可以解决bba。这个时候全排列生成完毕!
代码实现：
public ArrayList < String > Permutation(String str)
{
ArrayList < String > list = new ArrayList < String > ();
if (str != null && str.length() > 0)
{
PermutationHelper(str.toCharArray(), 0, list);
Collections.sort(list);
}
return list;
}
private void PermutationHelper(char[] chars, int i, ArrayList < String > list)
{
if (i == chars.length - 1)
{
list.add(String.valueOf(chars));
}
else
{
Set < Character > charSet = new HashSet < Character > ();
for (int j = i; j < chars.length; ++j)
{
if (j == i || !charSet.contains(chars[j]))
{
charSet.add(chars[j]);
swap(chars, i, j);
PermutationHelper(chars, i + 1, list);
swap(chars, j, i);
}
}
}
}
private void swap(char[] cs, int i, int j)
{
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}思路2：
字典序排列算法
一个全排列可看做一个字符串，字符串可有前缀、后缀。
生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
这就要求这一个与下一个有尽可能长的共同前缀，也就是变化限制在尽可能短的后缀上。
例：839647521是1--9的排列。
1—9的排列最前面的是123456789，最后面的987654321，
从右到左扫描若都是增的，就到了987654321，也就没有下一个了。
否则找出第一次出现下降的位置。
例：如何得到346987521的下一个?
1，从尾部往前找第一个P(i-1) < P(i)的位置
3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
最终找到6是第一个变小的数字，记录下6的位置i-1
2，从i位置往后找到最后一个大于6的数
3 4 6 -> 9 -> 8 -> 7 5 2 1
最终找到7的位置，记录位置为m
3，交换位置i-1和m的值
3 4 7 9 8 6 5 2 1
4，倒序i位置后的所有数据
3 4 7 1 2 5 6 8 9
则347125689为346987521的下一个排列
代码实现：
public ArrayList < String > Permutation2(String str)
{
ArrayList < String > list = new ArrayList < String > ();
if (str == null || str.length() == 0)
{
return list;
}
char[] chars = str.toCharArray();
Arrays.sort(chars);
list.add(String.valueOf(chars));
int len = chars.length;
while (true)
{
int lIndex = len - 1;
int rIndex;
while (lIndex >= 1 && chars[lIndex - 1] >= chars[lIndex])
{
lIndex--;
}
if (lIndex == 0)
break;
rIndex = lIndex;
while (rIndex < len && chars[rIndex] > chars[lIndex - 1])
{
rIndex++;
}
swap(chars, lIndex - 1, rIndex - 1);
reverse(chars, lIndex);
list.add(String.valueOf(chars));
}
return list;
}
private void reverse(char[] chars, int k)
{
if (chars == null || chars.length <= k)
return;
int len = chars.length;
for (int i = 0; i < (len - k) / 2; i++)
{
int m = k + i;
int n = len - 1 - i;
if (m <= n)
{
swap(chars, m, n);
}
}
}思路3：
回溯法思想
代码实现：
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class Solution
{
public static void main(String[] args)
{
Solution p = new Solution();
System.out.println(p.Permutation("abc")
.toString());
}
public ArrayList < String > Permutation(String str)
{
List < String > res = new ArrayList < > ();
if (str != null && str.length() > 0)
{
PermutationHelper(str.toCharArray(), 0, res);
Collections.sort(res);
}
return (ArrayList) res;
}
public void PermutationHelper(char[] cs, int i, List < String > list)
{
if (i == cs.length - 1)
{
String val = String.valueOf(cs);
if (!list.contains(val))
list.add(val);
}
else
{
for (int j = i; j < cs.length; j++)
{
swap(cs, i, j);
PermutationHelper(cs, i + 1, list);
swap(cs, i, j);
}
}
}
public void swap(char[] cs, int i, int j)
{
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}用你自己的思路你会如何实现呢?更多Java实例，请继续来本站了解。