字符串的组合算法问题的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 ,int number , 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 == '\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来存放选择放进组合里的字符。
方法二：用位运算来实现求组合

#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;
}

全组合
例如给定字符串“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个数，可以分解为以下两步：

1. 从n个数中选取编号最大的数，然后在剩下的n-1个数中选取m-1个数。直到从n-(m-1)中选取一个数为止
2. 从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 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, int n, 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, k, n, list, rs);
        list.remove(list.size() - 1);
      }
    }
  }