字符串的排列（剑指offer 28题及课后题拓展）

• permutation
  输入abc，得到abc,acb,bac,bca,cba,cab
  思路就是将输入的字符串的第一个字符跟后面的进行交换，也就是到不同的位置得到不同的排列，这样的解释对后面不大直观，应该说是第一个位置都有字符串所有的字符坐过，然后再递归后面。
  比如abc
  abc
  再递归对bc进行
  bac
  ...
  cba
  ....

import java.util.HashSet;
import java.util.Scanner;

public class Permutation {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if(sc.hasNextLine()) {
            String string = sc.nextLine();
            int count = numOfPermutation(string);
            System.out.println(count);
        }
    }

    public static int numOfPermutation(String string){
        if(string==null)
            return 0;

        HashSet<String> set = new HashSet<>();
        numOfPermutation(new StringBuilder(string), set, 0);
        return set.size();
    }

    public static void numOfPermutation(StringBuilder sb, HashSet<String> set, int startIndex){
        if(startIndex==sb.length()-1) {
            set.add(sb.toString());
        } else {
            for(int i=startIndex;i<sb.length();i++) {
                swap(sb, startIndex, i);
                numOfPermutation(sb, set, startIndex+1);
                swap(sb, startIndex, i);
            }
        }
    }

    public static void swap(StringBuilder sb, int i, int j){
        char ichar = sb.charAt(i), jchar=sb.charAt(j);
        sb.setCharAt(i, jchar);
        sb.setCharAt(j, ichar);
    }
}

• 所有长度的permutation
  输入abc得到 a,ab,abc,ac,acb,b,ba,bac,bc,bca,c,cb,cba,ca,cab

    public static void permutation2(String string) {
        permutation2(string.toCharArray(), 0);
    }

    public static void permutation2(char[] charArray, int startIndex) {
        for(int i=startIndex; i<charArray.length; i++) {
            utils.swap(charArray, startIndex, i);
            System.out.print(new String(Arrays.copyOf(charArray, startIndex+1))+",");
            utils.swap(charArray, startIndex, i);
        }
    }

• 组合
  输入abc，得到a,b,c,ab,ac,bc,abc，没有顺序。
  基本的思想就是递归，把原始的字符串不变顺序，从前后到后面，每次都对每个字符进行选择或者不选择，选择那么就把问题降为在剩下的字符中选择n-1个，不选择就还是在剩下的字符中选择n个。

    public static void combination(String string){
        for(int i=0;i<string.length();i++) {
            Queue<Character> queue = new LinkedList<>();
            combination(string.toCharArray(), 0,i+1, queue);
        }
    }

    public static void combination(char[] charArray, int fromIndex, int numCharsTobeSelected, Queue<Character> queue) {
        if (numCharsTobeSelected == 0) {
            for (Character ch : queue) {
                System.out.print(ch);
            }
            if(queue.size()>0)
                System.out.println();
            return;
        }

        int NumCharsLeft = charArray.length - fromIndex;
        if(NumCharsLeft < numCharsTobeSelected){
            return;
        }

        queue.add(charArray[fromIndex]);
        combination(charArray, fromIndex+1, numCharsTobeSelected - 1, queue);
        queue.poll();

        combination(charArray, fromIndex+1, numCharsTobeSelected, queue);
    }