关于字符串的组合算法问题的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); } } }
-
内部排序之堆排序的实现
堆排序(HeapSort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。下面小编为大家整理了内部排序之堆排序的实现,希望能帮到大家!(1)基本概念a)堆:设有n个元素的序列:{k1,k2,...,kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系:ki≤k2i,ki≤k2i+1或ki...
-
了解什么是编程语言
学习编程语言之前,首先要搞清楚“编程语言”这个概念。下面一起来看看!很小的时候,父母就教我们开口说话,也教我们如何理解别人讲话的意思。经过长时间的熏陶和自我学习,我们竟然在不知不觉中学会了说话,同时也能听懂其他小朋友说话的意思了,我们开始向父母要零花钱...
-
浅谈高职C语言课程的教学分析与设计
C语言作为学院网络技术专业的人门课程,旨在通过锻炼学生的逻辑思维,墙养学生在职业岗位中实际应用的能力.目前,该专业的学生毕业后主要从事网站开发和网络管理等方面的工作,而在这些领域几乎都以C语言作为应用的开发工具.但从历年教学实践来看,教师往往付出的精力多...
-
计算机C语言考点大全
C语言是世界上最流行、使用最广泛的高级程序设计语言之一。下面小编整理了计算机C语言考点大全,希望对大家有帮助!【考点1】C程序C语言程序结构有三种:顺序结构,循环结构(三个循环结构),选择结构(if和switch)【考点2】main函数每个C语言程序中main函数是有且只...