String Full Permutation Problem

Problem description ：

Enter a string , Print out all permutations of the string . for example , Input string ”abc”, The output has characters ’a’,’b’,’c’ All the strings that can be arranged ”abc”,”acb”,”bac”,”bca”,”cab”,”cba”.

Recursive implementation ：

Select a character from the string as the first character of the arrangement , Then arrange all the remaining characters . Such recursive processing , So as to get the full arrangement of all characters . The specific code is as follows ：

public class StringArrange {// Method 1： Recursive implementation 
    /*
     *  Parameters arrayA: The character array of the given string 
     *  Parameters start: Start traversing the position where the character and its subsequent characters will be exchanged 
     *  Parameters end: The last bit of the string array 
     *  The functionality ： All characters of the output string number are arranged 
     */
    public void recursionArrange(char[] arrayA,int start,int end){
        if(end <= 1)   
             return;
        if(start == end){
            for(int i = 0;i < arrayA.length;i++)
                System.out.print(arrayA[i]);
            System.out.println();
        }
        else{
            for(int i = start;i <= end;i++){
                swap(arrayA,i,start);
                recursionArrange(arrayA,start+1,end);
                swap(arrayA,i,start);
            }
        }
        
    }
    // Swap arrays m Location and n The value of the position 
    public void swap(char[] arrayA,int m,int n){
        char temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }
    
    public static void main(String[] args){
        StringArrange test = new StringArrange();
        String A = "abc";
        char[] arrayA = A.toCharArray();
        test.recursionArrange(arrayA,0,arrayA.length-1);
    }
}

Dictionary order arrangement implementation

（1） Find the last in the spread （ The most right ） The first position in an ascending order i.

（2） Find number one in the list i The last ratio on the right of bit ai Big place j.

（3） In exchange for ai and aj Value .

（4） The first i+1 The part from bit to the last bit is reversed .

The specific code is as follows ：

public class StringArrange {
    // Method 2： Dictionary order 
    /*
     *  Parameters arrayA： The character array of the given string 
     *  The functionality ： The dictionary order of all characters of the output string array is completely arranged 
     */
    public void dictionaryArrange(char[] arrayA){
        System.out.println(String.valueOf(arrayA));
        while(allArrange(arrayA))
            System.out.println(String.valueOf(arrayA));
    }
    // Determine the current array arrayA Whether the sequence can be arranged in dictionary order , If possible, arrange and return true, Otherwise return to false
    public boolean allArrange(char[] arrayA){
        int i;
        for(i = arrayA.length-2;(i >= 0) && arrayA[i] > arrayA[i+1];--i);
        if(i < 0)
            return false;
        int k;
        for(k = arrayA.length-1;(k > i) && arrayA[i] >= arrayA[k];--k);
        swap(arrayA,i,k);
        reverseArray(arrayA,i+1,arrayA.length-1);
        return true;
    }
    // Will be in the array a[m] To a[n] A segment of elements are arranged in reverse order 
    public void reverseArray(char[] arrayN,int m,int n){
        while(m < n){
            char temp = arrayN[m];
            arrayN[m++] = arrayN[n];
            arrayN[n--] = temp;
        }
    }
    // Swap arrays m Location and n The value of the position 
    public void swap(char[] arrayA,int m,int n){
        char temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }

    public static void main(String[] args){
        StringArrange test = new StringArrange();
        String A = "abc";
        char[] arrayA = A.toCharArray();
        test.dictionaryArrange(arrayA);
    }
}