By

文章目录

//实现字符串每个字符 的全排列,并求取全排列的个数
//分为三部分：1.首先，求取所有可能出现在第一个位置的字符；
//2.其次，把第一个字符和其后面的字符一一交换；
//3.接着，固定第一个字符，求后面所有字符的排列。重复步骤2

//全排列

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<assert.h>
using namespace std;
//  调试开关
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain
class Solution{
protected:
    vector<string> m_res;//字符数组，存储排好序的字符串
public:
    void Permutation(string str){
        int countt=0;
        m_res.clear();
        if(str.empty())
            return ;

        Perm(str,0);

        sort(m_res.begin(),m_res.end());
        //删除容器中重复 元素
        vector<string>::iterator new_end;
        new_end=unique(m_res.begin(),m_res.end());//把重复元素放在容器末尾
        //assert(m_res.size()==N);
        m_res.erase(new_end,m_res.end());//真正删除重复元素
        //输出容器中元素
        vector<string>::iterator iter=m_res.begin();
        for(;iter!=m_res.end();iter++)
        {
            countt++;
            cout<<*iter<<endl;
        }
        cout<<endl;
        cout<<countt<<endl;
       // return m_res;

    }

    void Perm(string str,int Begin){//str要排序的字符串，Begin代表排序部分的第一个字符的位置
        if(str[Begin]=='\0'){//全部已经排好序
           // debug<<str<<endl;
            m_res.push_back(str);
        }
        for(int i=Begin;str[i]!='\0';i++){
            if(i==Begin||str[i]!=str[Begin]){//排除重复
                swap(str[i],str[Begin]);//排序部分第一个位置的字符全部找到
                Perm(str,Begin+1);//递归排序之后的字符
                swap(str[i],str[Begin]);

            }
        }
    }
};
int __tmain( )
{
    Solution solu;
    solu.Permutation("abb");

    return 0;
}


//********************************************************************
//组合。从n个字符中挑选m个字符放到组合当中。有两个方案：第一个字符放到组合当中，剩下的m-1个字符从n-1个字符中挑选，
//另一种方案：第一个字符不放到组合当中，那么从剩下的n-1中挑选m-1个字符放到组合当中
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#include<assert.h>
#include<stdio.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，否则为0.a:100,b:010...
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
void Combination(string str){
    int countt=0;
    if(str.empty())
        return;
    int len=str.size();
    for(int i=1;i<(1<<len);i++){//从0~2^n-1，中可能出现的情况
        for(int j=0;j<len;j++){
            if(i&(1<<j)){//这个位置上有数
                cout<<str[j]<<" ";

            }
        }
        countt++;
        cout<<endl;

    }
    cout<<countt;
}
int main(){
    Combination("abc");
    return 0;
}

//**
//八皇后问题。不同行，不同列，不同斜角线。

#include

#include
using namespace std;
int count_number=0;
bool isDiagnal(int ColumnIndex[],int length){
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
if(i-j==ColumnIndex[i]-ColumnIndex[j] || j-i==ColumnIndex[i]-ColumnIndex[j])//对角关系
return false;
}

}
return true;

}
void Print(int ColumnIndex[],int length){
cout<<count_number<<”:”;
for(int i=0;i<length;i++){
cout<<ColumnIndex[i]<<” “;//输出列

}
cout<<endl;

}

void Permutation(int ColumnIndex[],int length,int index){
if(index==length){//index代表排列好的列
if(isDiagnal(ColumnIndex,length)){//状态合法，没有斜对角关系
count_number++;//一次符合要求的状态
Print(ColumnIndex,length);
}
}
else{
for(int i=index;i<length;i++){
swap(ColumnIndex[index],ColumnIndex[i]);//第一个位置可能的情况
Permutation(ColumnIndex,length,index+1);//递归后面的部分分成第一个元素以及剩下的元素
swap(ColumnIndex[index],ColumnIndex[i]);
}
}
}
void EightQueen(){
const int length=8;
int ColumnIndex[length];
for(int i=0;i<length;i++){
ColumnIndex[i]=i;//下标表示行，值代表列
}
Permutation(ColumnIndex,length,0);
}

int main(void)
{
EightQueen();
return 0;
}

文章目录