一个简单的字符组合算法

有个朋友问了我这个问题：

把几个数组里面的元素任意组合 并输出所有组合。C++中是有相关的函数，我们自己来实现一下吧。

当然大家一开始就会想到用递归，下面就给出简单的源码。

 

#include <iostream>
using namespace std;

char arr[100][100];

void work(int row, int col, char* str);

int main()
{
	int n,i,j,tmp;
	char* str;
	
	//输入
	cin>>n; //n个数组
	for(i = 0; i < n; i ++)
	{
		cin>>tmp;
		for(j = 0; j < tmp; j ++)
		{
			cin>>arr[i][j];
		}
		arr[i][j] = '\0';
	}
	arr[i][0] = '\0'; //把最后一行标记为\0
	
	//开始处理	
	str = (char*)malloc((n+1)*sizeof(char));
	work(0,0,str); //从0行0列开始处理
	cin>>n; //没多大用处，就是让程序停一下，看一下结果
	return 0;
}

void work(int row, int col, char* str) 
{	//函数中要访问的是row行的col列
	if(arr[row][0] == '\0') //到最后一行了，可以输出了
	{
		str[row] = '\0';
		cout<<str<<endl;
		return;
	}
	if(arr[row][col] == '\0') //到最后一列了，要换回上一行
	{	
		return;
	}
	
	//不是最后一行，也不是最后一列，输出，并枚举下面的行
	str[row] = arr[row][col];
	work(row+1,0,str);
	work(row,col+1,str);
}

 //测试数据：

3  //表示下面有三行,每行都不为空

3 a c t      //第一行,开关数字表示后面有几个字符

5 b e s 4 *  //第二行,开关数字表示后面有几个字符

4 3 - a #    //第三行,开关数字表示后面有几个字符

 

2

2 a b

2 1 2

 

3 

3 a c t  

5 b e s 4 *  

4 3 - a #

 

//思路：

//从第一行往下走，每走一步输出一个字符，走到\0行时，输出换行

//如果row行的col列是\0时，说明下面的行枚举完了，则要返回上一行的下一列的字符，再往下面的行枚举