*一个简洁版的结果过程说明，固定一个位，变换其他位
a b c d
a b d c
a c b d
a c d b
a d c b
a d b c
void perm(char* list, int i, int n)
{
int j;
if( i == n)
{
for(j=0; j <= n; ++ j) cout<<list[j]<<" ";
cout<<endl;
}else
{
for( j = i; j <= n; ++ j)
{
cout<<"i:j "<<i<<":"<<j<<list[j]<<endl;
swap(list[i], list[j]);
perm(list, i+1, n);
swap(list[i],list[j]);
}
}
}
1.basic permutation,递归实现，固定一个字母，从后往前依次交换字母，交换后恢复，递归回溯时，回到前一个字母，再重复以上操作，
*pB = d
a b c d ->a b c d (*pB = c)
a b d c -> a b c d (*pB = b)
a c b d -> a c d b , a c b d , a b c d(*pB = b)
b a c d -> b c a d ,....... (*pB = a)
// EightQueen.cpp : 定义控制台应用程序的入口点。
//StringPermutation
#include "stdafx.h"
void Permutation(char* pstr,char* pBegin);
void Permutation(char* str)
{
if(str == NULL)
return;
else
Permutation(str,str);
}
void Permutation(char* pstr,char* pBegin)
{
if(*pBegin == '\0')
printf("%s\n",pstr);
else
{
for(char* pch = pBegin; *pch != '\0'; ++ pch)
{
//是交换的两个指针指向元素的值，不是交换指针
char temp = *pch;
*pch = *pBegin;
*pBegin = temp;
Permutation(pstr, pBegin + 1);
temp = *pch;
*pch = *pBegin;
*pBegin = temp;
}
}
}
void Test(char* str)
{
if(str == NULL)
printf("NULL\n");
else
printf("Test on string %s begins\n",str);
Permutation(str);
printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
Test(NULL);
char string1[] = "";
Test(string1);
char string2[] = "a";
Test(string2);
Test("a");//编译通过，但是不能正确输出，why??
/*
char* p是一个指针，根本没分配内存，他指向的"abc123ABC" 是只读的，不能改变，你改变他的值肯定是错的
而char p[]是一个数组，已经分配内存，是将"abc123ABC" 复制到该内存里面，这个内存是可读写的
*/
char string3[] = "abc";
Test(string3);
return 0;
}
如果是java编写可以考虑，把数组传入，int 下标，length长度
考虑如果有重复的字符怎么处理：扩展1：存在相同字符的情况怎么求出全排列，在进行交换的那步添加一个判断如果两个字符相等不用进行交换，这样子输出的还是重复的，因为，在递归的过程中，是交换，固定第一个字符，再接着对后面的字符进行交换，固定的递归，代码是copy的网上的：
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<assert.h>
//在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等
bool IsSwap(char* pBegin , char* pEnd)
{
char *p;
for(p = pBegin ; p < pEnd ; p++)
{
if(*p == *pEnd)
return false;
}
return true;
}
void Permutation(char* pStr , char *pBegin)
{
assert(pStr);
if(*pBegin == '\0')
{
static int num = 1; //局部静态变量，用来统计全排列的个数
printf("第%d个排列\t%s\n",num++,pStr);
}
else
{
for(char *pCh = pBegin; *pCh != '\0'; pCh++) //第pBegin个数分别与它后面的数字交换就能得到新的排列
{
if(IsSwap(pBegin,pCh))
{
swap(*pBegin , *pCh);
Permutation(pStr , pBegin + 1);
swap(*pBegin , *pCh);
}
}
}
}
int main(void)
{
char str[] = "baa";
Permutation(str , str);
return 0;
}
扩展1：正方体八个顶点问题
全排列问题的STL用法（next_permutation类）点击打开链接
// EightQueen.cpp : 定义控制台应用程序的入口点。
//StringPermutation
#include "stdafx.h"
#include <algorithm>
using namespace std;
/*
总共只有8个点，因此直接给每个顶点编号， 然后求一个全排列，再判断是否存在合法解就好了。
另外也可以稍微优化一下，固定 一个点，求其他7个点的全排列， 复杂度为 O(7!) = 5040
*/
bool Can(int* Node)// 输入8个顶点的值
{
#define GetSum(x1,x2,x3,x4)(Node[Pos[x1]]+Node[Pos[x2]]+Node[Pos[x3]]+Node[Pos[x4]])
int sum = 0;
for(int i = 0; i < 8; ++ i)
sum += Node[i];
if(sum % 2 !=0) // 和为奇数?
return false;
int Pos[8] = {0,1,2,3,4,5,6,7};
do
{// 只需要检查3个面, 当一个面的顶点和 = Sum / 2 时,对面的顶点和必然也 = Sum / 2
if(GetSum(0,1,2,3) == sum / 2 && GetSum(0,2,4,6) == sum / 2 && GetSum(0,1,4,5))
//得到一组合法解,此时若需要可以输出
return true;
}while(next_permutation(Pos + 1, Pos + 7)); // 用STL求其余7个顶点的全排列
return false;
}
void Test(int *num)
{
if(num == NULL)
printf("NULL\n");
else
printf("Test on int[] begins\n");
char* s = Can(num) ? "yes":"no";
printf("It pass %s\n", s);
}
int _tmain(int argc, _TCHAR* argv[])
{
int num[8] = {1,2,3,4,5,6,7,8};
Test(num);
return 0;
}
扩展2：八皇后问题，全排列解法
2.组合问题
题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：
// EightQueen.cpp : 定义控制台应用程序的入口点。
//StringCombination
#include "stdafx.h"
#include <string.h>
#include <vector>
using namespace std;
//number是还需要添加的字符个数，vector是保存已有字符组合的容器
void Combination(char* str, int number, vector<char>& result);
void Combination(char* str)
{
if(str == NULL)
return;
vector<char> result;
int length = strlen(str);
//相当于N个字符取M个，length=M
for(int i = 1; i <= length; ++ i)
Combination(str, i, result);
}
//vector是取引用，&引用时别名，不用拷贝，值传递是需要拷贝的，有时间空间浪费
void Combination(char* str, int number, vector<char>& result)
{
//当组合数满足number的要求，输出
if(number == 0)
{
//对vector不熟悉，字符输出用%c,iter是指针所以是*iter
vector<char>::iterator iter = result.begin();
for(; iter < result.end(); ++ iter)
printf("%c",*iter);
printf("\n");
return;
}
//当字符搜索到'\0'结束,&&&&&&&&&&指针忘了写*str取值符
if(*str == '\0')
return;
//在result中添加字符直至满足number的要求
result.push_back(*str);
Combination(str + 1, number - 1, result);//深度调用，每一次调用返回都会在自己所在的层次中*删除一个字符，后在调用**
//*
result.pop_back();
//**
Combination(str + 1, number, result);
}
void Test(char* str)
{
if(str == NULL)
printf("NULL\n");
else
printf("Test on string %s begins\n",str);
Combination(str);
printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
Test(NULL);
char string2[] = "a";
Test(string2);
char string3[] = "abc";
Test(string3);
return 0;
}
(2) 01转换法
本程序的思路是开一个数组，其下标表示1到n个数，数组元素的值为1表示其代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的n-m的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。
排列的特殊方法：设有n个字符，模拟2进制加法器，某一个为1，则取对应的字符，若为0则不取，就能够实现字符组合。
int num 从 1 自增到 2^n -1, 将num右移i位，跟1做按位&操作，即可判断第i个字符取还是不取。
int main()
{
string str= "abc";
int N = str.size();
int num = pow(2.,N) ;
for(int i=1;i<num;i++)//因为除了一个也不取，一共有7个组合，所以是1~num
{
for(int j=0;j<N;j++)
{
if((i>>j)&1)
cout<<str[j];
}
cout<<endl;
}
return 0;
}
如果排列中有重复的字符，就先将字符串扫描一遍，记录下字符出现次数>1的字符，再去除字符串中重复字符，进行组合。
Subset
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S)
{
vector<vector<int> > result;
if(S.size() == 0)
return result;
sort(S.begin(), S.end());
int n = S.size();
vector<int> each;
result.push_back(each);
for(int i = 1; i < pow(2,n); ++ i)
{
each.clear();
for(int j = 0; j < n ; ++ j )
{
if( (i >> j) & 1 == 1 )
each.push_back(S[j]);
}
result.push_back(each);
}
return result;
}
};
SubsetII
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > result;
if(S.size() == 0)
return result;
sort(S.begin(), S.end());
int n = S.size();
vector<int> each;
result.push_back(each);
for(int i = 1; i < pow(2,n); ++ i)
{
each.clear();
for(int j = 0; j < n ; ++ j )
{
if( (i >> j) & 1 == 1 )
each.push_back(S[j]);
}
vector<vector<int> >::iterator itr = find(result.begin(), result.end(),each);
if(itr == result.end())
result.push_back(each);
}
return result;
}
};
1,2,3,4依次输出3个数的组合，2个数的组合，和一个数的组合
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
vector<vector<char> > result;
void Combination2(char* str, int i, vector<char> &perstr)
{
if(i == 0)
{
result.push_back(perstr);
return;
}
if(*str == '\0')
return;
perstr.push_back(*str);
Combination2(str+1, i-1, perstr );
perstr.pop_back();
Combination2(str+1, i, perstr );
}
void Combination(char* str)
{
if(str == NULL )
return;
vector<char> perstr;
int length = strlen(str);
// cout<<length<<endl;
for(int i = length-1; i >= 1; -- i)
Combination2(str,i,perstr);
}
int _tmain(int argc, _TCHAR* argv[])
{
char b[] = "1234";
// cout<<b[1]<<endl;
Combination(b);
for(size_t i = 0; i < result.size(); ++ i)
{
for(size_t j = 0; j < result[i].size(); ++ j)
cout<<result[i][j];
cout<<endl;
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
