字符串的組合算法成績的C說話完成攻略。本站提示廣大學習愛好者：（字符串的組合算法成績的C說話完成攻略）文章只能為提供參考，不一定能成為您想要的結果。以下是字符串的組合算法成績的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個數，可以分化為以下兩步：
代碼以下：
/**
* 遞歸法處理組合成績
*/
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);
}
}
}
