字符串全排列-循环递归

题目描述

输入一串字符串，输出该字符串所有的排列，并且无重复。
例如，输入：“abc”，输出：abc、acb、bac、bca、cab、cba

解决思路

正常思维，先固定一字母，求之后字母的全排列，该问题可划分为更小的子问题，直到所求子问题规模为0，输出结果。显然，使用递归的思路求解，下图为递归的过程：

image.png

递归具有两个基本特征：递归终止条件与递归式

• 递归终止条件：当所求全排列问题规模为0，即字符串长度为0
• 递归式：将所有全排列字符串的第一个字符依次与后面字符交换，然后递归进入下一层，递归返回时，还原交换

代码实现

package lanqiao.practise;

import java.util.Scanner;

public class Permutation {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //input a string ,output the permutation using recursive
        Scanner s = new Scanner(System.in);
        String string = s.nextLine();
        char[] a = string.toCharArray();
        permutation(a,a.length);
    }
    
    public static void permutation(char[] a,int n) {
        if(a.length == 0)
            return ;
        else {
            permutate(a,0,n);
        }
    }
    
    public static void permutate(char[] a,int k,int n) {
        if(k==n) {
            System.out.println(a);
            return ;
        }
        for(int i=k;i<n;i++) {
            //to prevent the repeated string, we could add a judgement
            if(i!=k&&a[i] == a[k])
                continue;
            swap(a,k,i);
            permutate(a,k+1,n);
            swap(a,k,i);
        }
    }
    public static void swap(char[] a,int i,int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}