字符串的组合算法问题的C语言实现攻略
基本字符串组合问题 题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。 上面我们详细讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;第二是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码: #include<iostream> #include<vector> #include<cstring> using namespace std; #include<assert.h> void Combination(char *string,int number,vector<char> &result); void Combination(char *string) { assert(string != NULL); vector<char> result; int i,length = strlen(string); for(i = 1 ; i <= length ; ++i) Combination(string,i,result); } void Combination(char *string,vector<char> &result) { assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d个组合t",num++); vector<char>::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter) printf("%c",*iter); printf("n"); return ; } if(*string == ' ') 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来存放选择放进组合里的字符。 #include<iostream> using 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; } 全组合 000 <---> NULL
/** * 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个数 这里分为两种方法:递归和回溯 递归
/** * 递归法解决组合问题 */ 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); } } }
题目 For example, ac代码 public class Solution { public static ArrayList<ArrayList<Integer>> combine(int n,int k) { ArrayList<ArrayList<Integer>> rs = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<Integer>(); dfs(1,k,n,list,rs); return rs; } public static void dfs(int pos,int k,ArrayList<Integer> list,ArrayList<ArrayList<Integer>> rs) { if (list.size() == k) { rs.add(new ArrayList<Integer>(list)); } for (int i = pos; i <= n; i ++) { list.add(i); dfs(i + 1,rs); list.remove(list.size() - 1); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |