字符串的排列/组合

曾经终败给现在 2022-08-01 06:21 183阅读 0赞

# 排列 #

字符串“abc”的全排列：

abc

acb

bac

bca

cba

cab

**求整个字符串的排列，可以分为两步：**

**第一步，求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步，固定第一个字符，求后面所有字符的全排列。这个时候仍然把后面所有字符分为两部分：第一个字符以及其后所有字符。这是一个典型的递归问题。**

例如字符串“abc”的全排列：以a开头的全排列是a\{bc\}，递归得到bc的全排列，而bc的全排列又是以b开头，c的全排列（即c自己）；

同样，以b开头的全排列是b\{ac\}，递归得到ac的全排列，而ab的全排列又是以a开头，c的全排列。……

[http://blog.csdn.net/cinderella\_niu/article/details/42930281][http_blog.csdn.net_cinderella_niu_article_details_42930281]

## 无重复的全排列 递归方法 ##

如下是递归算法：

//全排列
    void swap(int &a, int &b) {
    	int temp = a;
    	a = b;
    	b = temp;
    }
    
    void Permutation(char str[], int index, int size) {
    	cout << "Permutation(" << index << ", " << size << ")" << endl;
    	if (index == size - 1) {
    		//cout << "全排列：";   //cout << str << endl;由于是全排列，还可以用这句打印结果
    		for (int i = 0; i < size; i++)
    			cout << str[i];
    		cout << endl;
    	}
    	else {
    		for (int i = index; i < size; i++) {
    			//cout << "\t" << str;
    			swap(str[index], str[i]);
    			//cout << " swap("  << index << ","<<  i << ") " << str << endl;
    			Permutation(str, index + 1, size);
    
    			//cout << "---\t" << str;
    			swap(str[index], str[i]);
    			//cout << " swap("  << index << ","<<  i << ") " << str << endl << endl;
    		}
    	}
    }

int main() {
      char test[] = "abc";
      Permutation(0, sizeof(test) - 1);
    }

下图分别是运行注释内语句和去掉注释内语句的运行结果：

![Center][] ![SouthEast][]

另一种写法：

void Permutation(char* pStr, char* pBegin)
    {
    	assert(pStr && pBegin);
    
    	if(*pBegin == '\0')
    		printf("%s\n",pStr);
    	else
    	{
    		for(char* pCh = pBegin; *pCh != '\0'; pCh++)
    		{
    			swap(*pBegin,*pCh);
    			Permutation(pStr, pBegin+1);
    			swap(*pBegin,*pCh);
    		}
    	}
    }

## 有重复的全排列 递归方法 ##

由于**全排列就是从第一个数字起每个数分别与它后面的数字交换。**我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如abb，第一个数与后面交换得bab、bba。然后abb中第二数就不用与第三个数交换了，但对bab，它第二个数与第三个数是不相同的，交换之后得到bba。与由abb中第一个数与第三个数交换所得的bba重复了。所以这个方法不行。

*换种思维*，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数a与第三个数b交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑bab，它的第二个数与第三个数交换可以得到解决bba。此时全排列生成完毕。

这样我们也得到了在全排列中去掉重复的规则——**去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。**用编程的话描述就是第i个数与第j个数交换时，要求\[i,j)中没有与第j个数相等的数。

void swap(int &a, int &b) {
            int temp = a;
            a = b;
            b = temp;
    }

//在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
    bool IsSwap(char *pszStr, int nBegin, int nEnd)
    {
    	for (int i = nBegin; i < nEnd; i++)
    		if (pszStr[i] == pszStr[nEnd])
    			return false;
    	return true;
    }
    //k表示当前选取到第几个数,m表示共有多少数.
    void PermutationHaveSameword(char *pszStr, int k, int m)
    {
    	if (k == m)
    	{
    		static int s_i = 1;
    		printf("  第%3d个排列\t%s\n", s_i++, pszStr);
    	}
    	else
    	{
    		for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
    		{
    			if (IsSwap(pszStr, k, i))
    			{
    				swap(pszStr[k], pszStr[i]);
    				PermutationHaveSameword(pszStr, k + 1, m);
    				swap(pszStr[k], pszStr[i]);
    			}
    		}
    	}
    }

int main(void)
    {
         char str[] = "aba";
         PermutationHaveSameword(str, 0, sizeof(str) - 2);
         //Combination(str);
         //Permutation(str, 0, sizeof(str) - 1);
         return 0;
    }

![Center 1][]

## 排列的非递归实习 ##

这个木有懂，参考 [http://blog.csdn.net/MoreWindows/article/details/7370155\#t2][http_blog.csdn.net_MoreWindows_article_details_7370155_t2]

至此我们已经运用了递归与非递归的方法解决了全排列问题，总结一下就是：

1．**全排列就是从第一个数字起每个数分别与它后面的数字交换。**

2．**去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。**

3．**全排列的非递归就是由后向前找替换数和替换点，然后由后向前找第一个比替换数大的数与替换数交换，最后颠倒替换点后的所有数据。**

## 全排列的变形：部分排列 ##

问题：从0-9这十个数字中选取3个数字进行排列，打印所有的组合结果。

这个问题就是全排列的变种了，全排列是求出了所有字母的排列方式，该题是求出了部分字母排列的方法。只需要将本文第一个程序“无重复的全排列 递归方法”中，程序结束的条件由if (index == size - 1)改为 if (index == m)即可，其中m是指要进行全排列的字符个数，比如m = 3。

//全排列
    void swap(int &a, int &b) {
    	int temp = a;
    	a = b;
    	b = temp;
    }
    //从size个字符中选取m个字符进行全排列，打印排列结果
    void Permutation(char str[], int index, int m, int size) {
    	if (index == m) {  //和本文第一个程序比只是这里打印时不太相同
    		for (int i = 0; i < m; i++)
    			cout << str[i];
    		cout << "\t";
    	}
    	else {
    		for (int i = index; i < size; i++) {
    			swap(str[index], str[i]);
    			Permutation(str, index + 1, size);
    			swap(str[index], str[i]);
    		}
    	}
    }

测试从0-9中选两个数的排列结果：

int main() {
       char test[] = "0123456789";
       Permutation(test, 0, 2, sizeof(test) - 1);
    }

![SouthEast 1][]

# 组合问题 #

题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

长度为n的字符串，能构成长度为1的组合、长度为2的组合、……、长度为n的组合。假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们**有两种选择**：第一是**把这个字符放到组合中去**，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是**不把这个字符放到组合中去**，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

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);
    }
    //使用vector容器来存放要放入组合的字符
    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);
    	cout << *string << endl;
    	Combination(string + 1 , number - 1 , result);
    	result.pop_back();
    	Combination(string + 1 , number , result);
    }

![SouthEast 2][]

## 使用位运算求组合问题 ##

一个长度为n的字符串，它的组合有2^n-1中情况，我们用1 ~ 2^n-1的二进制来表示，每种情况下输出当前位等于1的字符。

![SouthEast 3][]

void Combination(char *str)
    {
    	int len=strlen(str); 
    	for(int cur=1; cur < (1<<len); cur++)  //遍历所有的情况，1<<len就等于2^len，遍历1 ~ 2^len-1
    	{
    		for(int j=0; j < len; j++)  //遍历所有的字符
    		{
    			if(cur & (1 << j))  //判断哪一位为1，即输出该位
    				cout << str[j]; 
    		}
    		cout << endl;  //一种情况结束
    	}
    }

# 八皇后问题 #

八皇后问题：

### [程序员面试题精选100题(58)-八皇后问题\[算法\] ][100_58_-_] ###

# [经典回溯算法（八皇后问题）][Link 1] #

参考： [http://blog.sina.com.cn/s/blog\_6fb300a30100mvzp.html][http_blog.sina.com.cn_s_blog_6fb300a30100mvzp.html]

[http://dongxicheng.org/structure/permutation-combination/][http_dongxicheng.org_structure_permutation-combination]

[http://blog.csdn.net/hackbuteer1/article/details/7462447][http_blog.csdn.net_hackbuteer1_article_details_7462447]

[http://www.it165.net/pro/html/201412/28579.html][http_www.it165.net_pro_html_201412_28579.html]

### [程序员面试题精选100题(59)-字符串的组合\[算法\] ][100_59_-_] ###

[http_blog.csdn.net_cinderella_niu_article_details_42930281]: http://blog.csdn.net/cinderella_niu/article/details/42930281
[Center]: https://img-blog.csdn.net/20150622084407936?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzA3NDQ2NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[SouthEast]: /images/20220731/b7db0bf5415a435abf87070a21aaea4d.png
[Center 1]: /images/20220731/0034b4b5d8b54e99a0d35e71816d7707.png
[http_blog.csdn.net_MoreWindows_article_details_7370155_t2]: http://blog.csdn.net/MoreWindows/article/details/7370155
[SouthEast 1]: /images/20220731/d7e187d6d4b141a78c2d9b569363e052.png
[SouthEast 2]: /images/20220731/2a907e6c543844c2a35e29eb78ba5672.png
[SouthEast 3]: /images/20220731/b77caba56bc24beaad3dfd182b6558ed.png
[100_58_-_]: http://zhedahht.blog.163.com/blog/static/2541117420114331616329/
[Link 1]: http://www.cnblogs.com/gaoteng/archive/2012/04/11/2442692.html
[http_blog.sina.com.cn_s_blog_6fb300a30100mvzp.html]: http://blog.sina.com.cn/s/blog_6fb300a30100mvzp.html
[http_dongxicheng.org_structure_permutation-combination]: http://dongxicheng.org/structure/permutation-combination/
[http_blog.csdn.net_hackbuteer1_article_details_7462447]: http://blog.csdn.net/hackbuteer1/article/details/7462447
[http_www.it165.net_pro_html_201412_28579.html]: http://www.it165.net/pro/html/201412/28579.html
[100_59_-_]: http://zhedahht.blog.163.com/blog/static/2541117420114172812217/