關於字串的組合演算法問題的C語言實現攻略

關於字串的組合演算法問題的C語言實現攻略

題目：輸入一個字串，輸出該字串中字元的所有組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。

上面我們詳細討論瞭如何用遞迴的思路求字串的排列。同樣，本題也可以用遞迴的思路來求字串的組合。

假設我們想在長度為n的字串中求m個字元的組合。我們先從頭掃描字串的第一個字元。針對第一個字元，我們有兩種選擇：第一是把這個字元放到組合中去，接下來我們需要在剩下的.n-1個字元中選取m-1個字元；第二是不把這個字元放到組合中去，接下來我們需要在剩下的n-1個字元中選擇m個字元。這兩種選擇都很容易用遞迴實現。下面是這種思路的參考程式碼：

#include#include#includeusing namespace std;#includevoid Combination(char *string ,int number,vector&result);void Combination(char *string){ assert(string != NULL); vectorresult; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i) Combination(string , i ,result);}void Combination(char *string ,int number , vector&result){ assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d個組合t",num++); vector::iterator iter = n(); for( ; iter != () ; ++iter) printf("%c",*iter); printf("n"); return ; } if(*string == ') return ; _back(*string); Combination(string + 1 , number - 1 , result); _back(); Combination(string + 1 , number , result);}int main(void){ char str[] = "abc"; Combination(str); return 0;}

由於組合可以是1個字元的組合，2個字元的字元……一直到n個字元的組合，因此在函式void Combination(char* string)，我們需要一個for迴圈。另外，我們用一個vector來存放選擇放進組合裡的字元。

用位運算來實現求組合

#includeusing namespace std;int a[] = {1,3,5,4,6};char str[] = "abcde";void print_subset(int n , int s){ printf("{"); for(int i = 0 ; i < n ; ++i) { if( s&(1<<i) ) // 判斷s的二進位制中哪些位為1，即代表取某一位 printf("%c ",str[i]); //或者a[i] } printf("}n");}void subset(int n){ for(int i= 0 ; i < (1<<n) ; ++i) { print_subset(n,i); }}int main(void){ subset(5); return 0;}

全組合

例如給定字串“abc”，全組合意思從中去0個元素，1個元素，一直到n個元素，介紹二進位制做法。以字串“abc”為例：

000 <---> NULL

001 <---> c

010 <---> b

011 <---> bc

100 <---> a

101 <---> ac

110 <---> ab

111 <---> abc

思路出來了，程式碼也比較好寫，分享一下我的程式碼：

/** * Write a method that returns all subsets of a set */ #include#include#include/** * 通過0到2^-1來標識子集 * * T = (n * 2^n) * */ void getSubset(char *str, int len) { int i, max, index, j; max = 1 << len; for (i = 1; i < max; i ++) { j = i; index = 0; while (j) { if (j & 1) { printf("%c", str[index]); } j >>= 1; index ++; } printf("n"); } } int main(void) { char str[1000]; while (scanf("%s", str) != EOF) { getSubset(str, strlen(str)); } return 0; }

從n中選m個數

這裡分為兩種方法：遞迴和回溯

遞迴

遞迴思路如下，從n個數中取出m個數，可以分解為以下兩步：

從n個數中選取編號最大的數，然後在剩下的n-1個數中選取m-1個數。直到從n-(m-1)中選取一個數為止 從n個數中選取次小的數，重複1的操作

程式碼如下：

/** * 遞迴法解決組合問題 */ void combine(int *arr, int n, int m, int *tmp, const int M) { int i, j; for (i = n; i >= m; i --) { tmp[m] = i; if (m == 0) { // 選出m個數 for (j = 0; j < M; j ++) { printf("%d ", arr[tmp[j]]); } printf("n"); } else { combine(arr, i - 1, m - 1, tmp, M); } } }

DFS

其實考慮到用dfs，這道題目就簡單很多，dfs的回溯條件就是臨時陣列的大小==k即可，同時附加一道LeetCode上的題目，用dfs思路ac

題目

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:

ac程式碼

public class Solution { public static ArrayListcombine(int n, int k) { ArrayListrs = new ArrayList(); ArrayListlist = new ArrayList(); dfs(1, k, n, list, rs); return rs; } public static void dfs(int pos, int k, int n, ArrayListlist, ArrayListrs) { if (() == k) { (new ArrayList(list)); } for (int i = pos; i <= n; i ++) { (i); dfs(i + 1, k, n, list, rs); ve(() - 1); } } }