字符串全排列—递归实现

阅读量: 504 编辑

字符串全排列

采用递归实现。

  • 外面的for循环是遍历每个字符向后进行交换

  • 第一次循环(i=k),和自己交换(a和a),剩下的bc继续递归

  • bc重复上面的过程,所以第一次输出是abc

    • 输出之后,要将交换的还原回来,保证arr并没有变化,然后继续递归

    • 在bc循环的时候,因为bc循环的 i会+1 ,就是 b和c会实现交换

    • 所以完成了acb的输出

  • i+1后,就是a和b的交换,也就是会变成 bac,剩下的 ac 会继续递归(重复上面bc的过程)

  • 同样的 i+2后,就是a和c的交换,也就会变成 cab,剩下是 ab 会继续递归

  • 我们这里只用了abc举例,如果是abcd,可以分成 a(bcd),然后a分别和b、c、d交换,同样递归即可。

public class FullPerm {

    public static void main(String[] args) {
        String s = "abc";
        char[] arr = s.toCharArray();
        fullRow(arr, 0, arr.length - 1);
    }

    /**
     * abc
     * acb
     * bac
     * bca
     * cba
     * cab
     */
    public static void fullPerm(char arr[], int k, int m) {
        if (k == m) {
            System.out.println(arr);
        } else {
            for (int i = k; i <= m; i++) {

                //交换第k个字符和第i个字符
                char temp;
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;

                //再对k后面的字符串进行全排列
                fullPerm(arr, k + 1, m);

                //排列完后再换回来继续下一层循环
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
            }
        }
    }

}


苏ICP备13052010号-3
©2022 南京匠成信息科技有限公司