Java排列组合字符串的方法

Java排列组合字符串的方法攻略

在Java中，我们可以使用递归或者循环的方式实现字符串的排列和组合。下面我们会分别对这两种方法进行讲解。

字符串排列

字符串排列是将给定的字符串中的所有字符进行全排列。例如，字符串"abc"的全排列有"abc"、"acb"、"bac"、"bca"、"cab"和"cba"。

递归实现

在递归实现字符串排列时，我们可以将问题拆分为从左往右选取第一个字符，然后递归求解剩余字符的全排列。具体步骤如下：

1. 设定递归终止条件，即当字符串为空时，输出并返回；
2. 遍历字符串中的每一个字符，以此为第一个字符，在剩余字符中递归求解全排列；
3. 递归结束后，将第一个字符与剩余字符依次交换位置，以输出所有的排列情况。

下面是Java递归实现字符串排列的代码：

public void permute(char[] str, int index) {
    if (index == str.length - 1) {
        System.out.println(new String(str));
        return;
    }
    for (int i = index; i < str.length; i++) {
        swap(str, index, i); // 将第index个字符和第i个字符交换位置
        permute(str, index + 1); // 递归求解剩余字符的全排列
        swap(str, index, i); // 恢复交换前的状态
    }
}

public void swap(char[] str, int i, int j) {
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

循环实现

另一种实现字符串排列的方式是通过循环实现。具体步骤如下：

1. 将字符串转换成字符数组，并将所有字符按照字典序从小到大排序；
2. 循环遍历所有的字符数组元素，每次将当前字符与后面的元素分别交换，然后递归求解剩余字符的全排列。

下面是Java循环实现字符串排列的代码：

public void permute(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);

    while (true) {
        System.out.println(new String(chars));
        int i = chars.length - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i--;
        }
        if (i < 0) {
            break; // 已经是最后一个排列，结束循环
        }
        int j = i + 1;
        while (j < chars.length && chars[j] > chars[i]) {
            j++;
        }
        j--; // 找到第一个比chars[i]小的字符
        swap(chars, i, j);
        reverse(chars, i + 1, chars.length - 1);
    }
}

public void swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

public void reverse(char[] chars, int i, int j) {
    while (i < j) {
        swap(chars, i++, j--);
    }
}

字符串组合

字符串组合是从给定的字符串中选取一定数量的字符组成新的字符串。例如，字符串"abc"中选取2个字符的组合有"ab"、"ac"和"bc"。

递归实现

在递归实现字符串组合时，我们逐个确定选中的字符。具体步骤如下：

1. 递归终止条件为选中的字符数量等于所要求的字符串长度；
2. 遍历字符串中的每一个字符，以此选中字符，并递归求解剩余字符的组合；
3. 递归结束后，将当前字符从选中的字符组合中去掉，以继续判断其他可能的字符组合情况。

下面是Java递归实现字符串组合的代码：

public void combine(String str, int length, int index, StringBuilder sb) {
    if (sb.length() == length) {
        System.out.println(sb.toString());
        return;
    }
    for (int i = index; i < str.length(); i++) {
        sb.append(str.charAt(i)); // 选中当前字符
        combine(str, length, i + 1, sb); // 递归求解剩余字符组合
        sb.deleteCharAt(sb.length() - 1); // 去掉当前字符，继续循环选取下一个字符
    }
}

循环实现

另一种实现字符串组合的方式是通过循环实现。具体步骤如下：

1. 将字符串转换成字符数组，并将所有字符按照字典序从小到大排序；
2. 枚举所有可能的组合，从前往后选取不同位置的字符，并保证选中的字符是按照字典序从小到大的顺序排列，以避免重复的组合情况。

下面是Java循环实现字符串组合的代码：

public void combine(String str, int length) {
    if (str == null || str.length() == 0 || length == 0) {
        return;
    }

    char[] chars = str.toCharArray();
    Arrays.sort(chars);

    int[] comb = new int[length];
    for (int i = 0; i < comb.length; i++) {
        comb[i] = i;
    }

    while (comb[0] <= chars.length - length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < comb.length; i++) {
            sb.append(chars[comb[i]]);
        }
        System.out.println(sb.toString());

        int i = comb.length - 1;
        while (i >= 0 && comb[i] == chars.length - comb.length + i) {
            i--;
        }
        if (i < 0) {
            break; // 已经是最后一个组合，结束循环
        }
        comb[i]++;
        for (int j = i + 1; j < comb.length; j++) {
            comb[j] = comb[j - 1] + 1;
        }
    }
}

示例说明

以字符串"abc"为例，我们来演示一下上述两种实现方式。

String str = "abc";
int length = 2;

// 递归实现字符串排列
char[] chars = str.toCharArray();
permute(chars, 0);

// 循环实现字符串排列
permute(str);

// 递归实现字符串组合
combine(str, length, 0, new StringBuilder());

// 循环实现字符串组合
combine(str, length);

输出结果如下：

abc
acb
bac
bca
cab
cba
abc
acb
bac
bca
cab
cba
ab
ac
bc

其中，递归实现的结果与循环实现的结果是完全相同的。