摘要：求字符串的全排列字符串的全排列設(shè)計一個算法，輸出一個字符串字符的全排列。的做法沒有結(jié)果的，都是在一個字符串上進(jìn)行的操作。字符串的全組合輸入三個字符，則它們的組合有。因此可以循環(huán)字符串長度，然后輸出對應(yīng)代表的組合即可。

  
求字符串的全排列

設(shè)計一個算法，輸出一個字符串字符的全排列。
比如，String = "abc"
輸出是"abc","bac","cab","bca","cba","acb"

從集合依次選出每一個元素，作為排列的第一個元素，然后對剩余的元素進(jìn)行全排列，如此遞歸處理；

比如：首先我要打印abc的全排列，就是第一步把a(bǔ) 和bc交換（得到bac,cab），這需要一個for循環(huán)，循環(huán)里面有一個swap，交換之后就相當(dāng)于不管第一步了，進(jìn)入下一步遞歸，所以跟一個遞歸函數(shù)， 完成遞歸之后把交換的換回來，變成原來的字串
遞歸方法1（July 方法）：

abc 為例子：
1. 固定a, 求后面bc的全排列： abc, acb。 求完后，a 和 b交換； 得到bac,開始第二輪
2. 固定b, 求后面ac的全排列： bac, bca。 求完后，b 和 c交換； 得到cab,開始第三輪
3. 固定c, 求后面ba的全排列： cab, cba
 即遞歸樹： 
　　　　　str:　　 a    　　　　 b 　　　　　　  c
　　　　　　 　　ab ac     　　ba bc  　　　     ca cb
　   　result:     abc acb    　 bac bca　     　   cab cba
　 

    public static void Permutation(char[] s, int from, int to) {
        if(to<=1)
            return;
        if(from == to){
            System.out.println(s);
        }
        else{
            for(int i=from;i<=to;i++){
                swap(s,i,from);
                Permutation(s,from+1,to);
                swap(s,from,i);
                }
        }
    }

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

遞歸方法2：
與上面算法區(qū)別：
本算法需要一個額外的存儲空間存放結(jié)果（buffer），固定第一個位置是哪個元素的時候，是通過一個循環(huán),然后看原始字符串上，每一個位置是什么元素。July的做法沒有結(jié)果的buffer，都是在一個字符串上進(jìn)行的操作。第一個swap的作用就是，依次拿起始字符和后面的每一個字符交換，這樣就能遍歷第一個位置上的所有可能字符

推薦一個youtube講解的視頻

n個數(shù)的全排列，一共有n！種情況. （n個位置，第一個位置有n種，當(dāng)?shù)谝粋€位置固定下來之后，第二個位置有n-1種情況...）

全排列的過程：

選擇第一個字符

獲得第一個字符固定下來之后的所有的全排列

選擇第二個字符

獲得第一+ 二個字符固定下來之后的所有的全排列

從這個過程可見，這是一個遞歸的過程。

還有一點需要注意是：
之前遞歸過程選擇的字符，下一次不能再被選： 第一個位置選了a, 其他位置就不能選a了
解決方法是1. 掃描之前選擇的字符 或者 2.創(chuàng)建一個與字符串等長的boolean數(shù)組，標(biāo)記該位置對于的字符是否已經(jīng)選擇。若選擇，則標(biāo)記true; 若未選擇，則標(biāo)記false.

public class Permutation {
    public static void permute(String str){
        int length = str.length();
        boolean[] used = new boolean[length];
        StringBuffer output = new StringBuffer(length);

        permutation(str,length,output,used,0);

    }

    // @para
    // position : 下一個放置的元素位置,所以調(diào)入時候是0
    // 
    static void permutation(String str, int length, StringBuffer output, boolean[] used, int position){
        // end of the recursion
        if(position == length){
            System.out.println(output.toString());
            return;
        }
        else{
            for(int i=0;i

個人認(rèn)為這個算法不如第一個遞歸方法，因為需要額外的空間；但是二者的時間復(fù)雜度是相同的，都是O(n！)。

字符串的全組合

輸入三個字符 a、b、c，則它們的組合有a b c ab ac bc abc。當(dāng)然我們還是可以借鑒全排列的思路，利用問題分解的思路，最終用遞歸解決。不過這里介紹一種比較巧妙的思路 —— 基于位圖。

假設(shè)原有元素n個，最終的組合結(jié)果有2^n - 1. 可以使用2^n - 1個位，1表示取該元素，0表示不取。 所以a表示001,取ab是011。
001,010,011,100,101,110,111。對應(yīng)輸出組合結(jié)果為：a,b,ab,c,ac,bc,abc。

因此可以循環(huán) 1~2^n-1(字符串長度)，然后輸出對應(yīng)代表的組合即可。

    public static void Combination(char [] s){
        if(s.length == 0){
            return;
        }
        int len = s.length;
        int n = 1<

    for(int j=0;j

j = 0， 1<
j = 1， 1<
j = 2， 1<

有限制的組合

Leetcode

  
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

  For example,

  If n = 4 and k = 2, a solution is:

  [

    [2,4],

    [3,4],

    [2,3],

    [1,2],

    [1,3],

    [1,4],

  ]


解題思路

基于位操作，這里我們主要借助一個二進(jìn)制操作 “ 求最小的、比 x 大的整數(shù) M，使得 M 與 x 的二進(jìn)制表示中有相同數(shù)目的 1”，如果這個操作已知，那么我們可以設(shè)置一個初始整數(shù) bit，bit 的低位第 1~k 個二進(jìn)制位為 1，其余二進(jìn)制位為 0，bit 的二進(jìn)制表示一種組合，然后調(diào)用上述操作求得下一個 bit，bit 的最大值為：bit 從低位起第 n-k+1~n 位等于 1，其余位等于 0，即 (1<

    public static List> combine(int n, int k) {
        if(n == 0 | k>n){
            return null;
        }
        int len = n;
        int nbit = 1<> result = new ArrayList>();
        //從1循環(huán)到2^len-1
        for(int i=kbit-1; i<= inbit; i = nextn(i)){
            List list = new ArrayList();
            for(int j=0;j>2;
    }



附錄： 位操作

  
求整數(shù)的二進(jìn)制表示中有多少個 1


方法1

應(yīng)用了n&=(n-1)能將 n 的二進(jìn)制表示中的最右邊的 1 翻轉(zhuǎn)為 0 的事實。只需要不停地執(zhí)行 n&=(n-1)，直到 n 變成 0 為止，那么翻轉(zhuǎn)的次數(shù)就是原來的 n 的二進(jìn)制表示中 1 的個數(shù)，其代碼如下：

    public int count1Bits(int n){
        int count = 0;
        while(n!=0){
            count++;
            n = n & (n-1);
        }
        return count;
    }


NextN

  
給定一個正整數(shù) N，求最小的、比 N 大的正整數(shù) M，使得 M 與 N 的二進(jìn)制表示中有相同數(shù)目的 1


方法1： 簡單枚舉

從 N+1 開始枚舉，對每個數(shù)都測試其二進(jìn)制表示中的 1 的個數(shù)是否與 N 的二進(jìn)制表示中 1 的個數(shù)相等，遇到第一次相等時就停止

    public int GetNextN(int n){
        int k = count1Bits(n);
        do{
            n++;
        }while(count1Bits(n) != k);
        return n;
    }


方法2： O(1)時間高效方法
參考

public int NextN(int n){
    int x = n&(-n);
    int t = n + x;
    int ans = t | ((n^t)/x)>>2;
    return ans;
}


想更一進(jìn)步的支持我，請掃描下方的二維碼，你懂的~