软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

字符串的组合算法问题的C语言实现攻略

基本字符串组合问题

题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。

上面我们详细讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;第二是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码:

#includeiostream#includevector#includecstringusing namespace std;#includeassert.hvoid Combination(char *string ,int number,vectorchar result);void Combination(char *string){ assert(string != NULL); vectorchar result; int i , length = strlen(string); for(i = 1 ; i = length ; ++i) Combination(string , i ,result);}void Combination(char *string ,int number , vectorchar result){ assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d个组合\t",num++); vectorchar::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter)  printf("%c",*iter); printf("\n"); return ; } if(*string == '\0') return ; result.push_back(*string); Combination(string + 1 , number - 1 , result); result.pop_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来存放选择放进组合里的字符。
方法二:用位运算来实现求组合

#includeiostreamusing 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(1i) )     // 判断s的二进制中哪些位为1,即代表取某一位  printf("%c ",str[i]);  //或者a[i] } printf("}\n");}void subset(int n){ for(int i= 0 ; i  (1n) ; ++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 stdio.h   #include stdlib.h   #include string.h      /**    * 通过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 ArrayListArrayListInteger combine(int n, int k) {       ArrayListArrayListInteger rs = new ArrayListArrayListInteger();       ArrayListInteger list = new ArrayListInteger();              dfs(1, k, n, list, rs);              return rs;     }          public static void dfs(int pos, int k, int n, ArrayListInteger list, ArrayListArrayListInteger rs) {       if (list.size() == k) {         rs.add(new ArrayListInteger(list));       }              for (int i = pos; i = n; i ++) {         list.add(i);         dfs(i + 1, k, n, list, rs);         list.remove(list.size() - 1);       }     }   }