快捷導(dǎo)航

字符串的組合算法問題的C語言實(shí)現(xiàn)攻略

更新時(shí)間：2015年08月07日 15:33:48 投稿：goldensun

這篇文章主要介紹了字符串的組合算法問題的C語言實(shí)現(xiàn)攻略,是根據(jù)ACM總結(jié)的經(jīng)典算法問題,需要的朋友可以參考下

基本字符串組合問題

題目：輸入一個(gè)字符串，輸出該字符串中字符的所有組合。舉個(gè)例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。

上面我們?cè)敿?xì)討論了如何用遞歸的思路求字符串的排列。同樣，本題也可以用遞歸的思路來求字符串的組合。

假設(shè)我們想在長度為n的字符串中求m個(gè)字符的組合。我們先從頭掃描字符串的第一個(gè)字符。針對(duì)第一個(gè)字符，我們有兩種選擇：第一是把這個(gè)字符放到組合中去，接下來我們需要在剩下的n-1個(gè)字符中選取m-1個(gè)字符；第二是不把這個(gè)字符放到組合中去，接下來我們需要在剩下的n-1個(gè)字符中選擇m個(gè)字符。這兩種選擇都很容易用遞歸實(shí)現(xiàn)。下面是這種思路的參考代碼：

#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個(gè)組合\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個(gè)字符的組合，2個(gè)字符的字符……一直到n個(gè)字符的組合，因此在函數(shù)void Combination(char* string)，我們需要一個(gè)for循環(huán)。另外，我們用一個(gè)vector來存放選擇放進(jìn)組合里的字符。
方法二：用位運(yùn)算來實(shí)現(xiàn)求組合

#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的二進(jìn)制中哪些位為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個(gè)元素，1個(gè)元素，一直到n個(gè)元素，介紹二進(jì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來標(biāo)識(shí)子集 
   * 
   * 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個(gè)數(shù)

這里分為兩種方法：遞歸和回溯

遞歸
遞歸思路如下，從n個(gè)數(shù)中取出m個(gè)數(shù)，可以分解為以下兩步：

從n個(gè)數(shù)中選取編號(hào)最大的數(shù)，然后在剩下的n-1個(gè)數(shù)中選取m-1個(gè)數(shù)。直到從n-(m-1)中選取一個(gè)數(shù)為止
從n個(gè)數(shù)中選取次小的數(shù)，重復(fù)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個(gè)數(shù) 
        for (j = 0; j < M; j ++) { 
          printf("%d ", arr[tmp[j]]); 
        } 
        printf("\n"); 
      } else { 
        combine(arr, i - 1, m - 1, tmp, M); 
      } 
    } 
  }

DFS
其實(shí)考慮到用dfs，這道題目就簡(jiǎn)單很多，dfs的回溯條件就是臨時(shí)數(shù)組的大小==k即可，同時(shí)附加一道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:

201587153428237.jpg (130×173)

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

您可能感興趣的文章: