如何C语言中实现字符串组合算法
字符串组合的组合在开发中是很流行的，我们可以使用它实现一些夸大较大的功能，这就是等级的差别，本文是爱站技术频道小编介绍的如何C语言中实现字符串组合算法，一起参考下文的介绍吧！
基本字符串组合问题
题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。
上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：
#include#include #include using namespace std; #include void Combination(char *string ,int number,vector &result); void Combination(char *string) { assert(string != NULL); vector result; int i , length = strlen(string); for(i = 1 ; i &result) { assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d个组合\t",num++); vector ::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来存放选择放进组合里的字符。
方法二：用位运算来实现求组合
#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
全组合
例如给定字符串“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 >= 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
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 ArrayList> combine(int n, int k) {
ArrayList> rs = new ArrayList>();
ArrayList list = new ArrayList();
dfs(1, k, n, list, rs);
return rs;
}
public static void dfs(int pos, int k, int n, ArrayList list, ArrayList> rs) {
if (list.size() == k) {
rs.add(new ArrayList(list));
}
for (int i = pos; i
上文就是爱站技术频道小编介绍的如何C语言中实现字符串组合算法，相信大家选择平台都有很丰富的经验了，欢迎大家继续关注js.aizhan.com。
上一篇：浅析C++开发之虚函数与虚函数表
