学步园

void swap(char &a,char &b)
{
    int t = a;
    a = b;
    b = t;
}
 
void permutation(char *a,int beg,int end)
{
    if(beg == end)
    {
        cout<<a<<endl;
    }
    else
    {
     
        for (int i=beg;i<end;++i)
        {
            swap(a[beg],a[i]);
            permutation(a,beg+1,end);
            swap(a[beg],a[i]);//细心,竟然把这个忘记
 
        }
    }
}
 
void Reversal(char *a,int beg,int end)
{
    while (beg<end)
    {
        swap(a[beg],a[end]);
        ++beg;
        --end;
    }
}
bool GenPermutation(char *a,int n)//n指长度
{
    for (int i = n-1;i>0;--i)
    {
        if (a[i-1]<a[i])
        {
            for (int j =n-1;j>i-1;--j)
            {
                if (a[j] >a[i-1])
                {
                    swap(a[j],a[i -1 ]);
                    Reversal(a,i,n-1);
                    cout<<a<<endl;
                    return true;
                }
            }
        }
    }
 
    return false;
}
 
int main()
{
    char a[] = "abc";
    cout<<a<<endl;
    while(GenPermutation(a,sizeof(a)-1));
     
    //permutation(a,0,sizeof(a)-1);
}

一、递归实现
从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例
固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
固定c，求后面ba的排列：cba，cab。代码可如下编写所示：

二、字典序排列
把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。
对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i < j）。如果不存在这样一对为升序的相邻元素，则所有排列均已找到，算法结束；否则，重新对当前排列从后向前扫描，找到第一个大于i的元素k，交换i和k，然后对从j开始到结束的子序列反转，则此时得到的新排列就为下一个字典序排列。

生成给定全排列的下一个排列
所谓一个的下一个就是这一个与下一个之间没有字典顺序中相邻的字符串。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

839647521的下一个排列.

从最右开始,找到第一个比右边小的数字4(因为4<7，而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5),交换4、5,此时5右边为7421,倒置为1247,即得下一个排列:839651247.用此方法写出全排列的非递归算法如下

算法的目的是要得到词典顺序，因为4是第一个比右边小的数字，所以4之后的串7521肯定是从从大到小的，所以将4和5交换后要对这个字串翻转

转自：http://dongxicheng.org/structure/permutation-combination/

3. 组合算法

3.1 全组合

在此介绍二进制转化法，即，将每个组合与一个二进制数对应起来，枚举二进制的同时，枚举每个组合。如字符串：abcde

00000 <– –> null

00001<– –> e

00010 <– –> d

… …

11111 <– –> abcde

3.2 从n中选m个数

(1) 递归

从n中找到一个数，然后在0到n-1中再找一个数，直到在n-(m-1)中选一个数

void Combine(char *a,int m,int end)//从0-end中选择m个
{
	if(m == 1)
	{
		for (int i=end;i >=0;--i)
		{
			swap(a[i],a[end]);
			cout<<a+end<<endl;
			swap(a[i],a[end]);
		}
	}
	else
	{
		for (int i=end;i>=0;--i)
		{
			swap(a[i],a[end]);
			Combine(a,m-1,end-1);
			swap(a[i],a[end]);
		}
	}
}


char a[] = "abcd";
Combine(a,3,3);

上面的算法是求从n个数找出m个数的全排列，而不是组合。。。下面代码才是m个数的组合

/// 求从数组a[1..n]中任选m个元素的所有组合。
 
/// a[1..n]表示候选集，n为候选集大小，n>=m>0。
 
/// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标)，
 
/// 常量M表示满足条件的一个组合中元素的个数，M=m，这两个参数仅用来输出结果。
 
void combine( int a[], int n, int m,  int b[], const int M )
 
{
 
  for(int i=n; i>=m; i--)   // 注意这里的循环范围
 
  {
 
    b[m-1] = i - 1;//当必有i-1时，的组合
 
    if (m > 1)
 
      combine(a,i-1,m-1,b,M);
 
    else                     // m == 1, 输出一个组合
 
    {
 
      for(int j=M-1; j>=0; j--)
 
      cout << a[b[j]] << " ";
 
      cout << endl;
 
    }
 
  }
 
}

(2) 01转换法

本程序的思路是开一个数组，其下标表示1到n个数，数组元素的值为1表示其代表的数被选中，为0则没选中。

首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。

然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的n-m的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5中选3的组合：

http://zhedahht.blog.163.com/blog/static/2541117420114172812217/

分析：在本系列博客的第28题《字符串的排列》中，我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

void Combination(char* string)

{

    if(string == NULL)

        return;

 

    int length = strlen(string);

    vector<char> result;

    for(int i = 1; i <= length; ++ i)

    {

        Combination(string, i, result);

    }

}

 

void Combination(char* string,int number, vector<char>& result)

{

    if(number == 0)

    {

        vector<char>::iterator iter = result.begin();

        for(; iter < result.end(); ++ iter)

            printf("%c", *iter);

        printf("\n");

 

        return;

    }

 

    if(*string ==
'\0')

        return;

 

int len = strlen(string);
if(len>=number)
{
result.push_back(*string);
Combination(string + 1, number - 1, result);
result.pop_back();
}
if(len > number)
{
Combination(string + 1, number, result);
}

}

}

      

                由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void
Combination(char* string)，我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符。

还有一种递归的方法：

void subSet(char *a, vector<char> &vt,int len) {

    if (len == 0) {
        for (int i = 0; i< vt.size(); ++i)
            cout<<vt[i];
        cout<<endl;
        return;
    }
    int size = strlen(a);
    int n = size - len;

    for (int i = 0; i <= n; ++i) {//从i处开始变量
        vt.push_back(*(a+i));
        subSet(a+i+1, vt, len - 1);
        vt.pop_back();
    }
}

下面是我自己写的一个非递归的算法：

char *a = "abcd";
	vector<string> vt;
	for (int i=0;i<strlen(a);++i)
	{
		int len = vt.size();
		char t[2]={0};
		t[0] = a[i];
		t[1] = '\0';
		string tmp = t;
		for (int j=0;j<len;++j)
		{
			

			vt.push_back(vt[j]+tmp);
		}
		vt.push_back(tmp);
		
	}
	
	for (int i=0;i<vt.size();++i)
	{
		cout<<vt[i]<<" ";
	}
	cout<<endl;