字典序全排列算法和组合算法

全排列的实现算法很多时候,大部分人喜欢用递归写,但是呢,其实可以用字典序写出非递归的版本,关键是更加当前序列生成下一个字典序,从顺序开始到逆序状态,输出每一次生成的序列就OK,上代码。
组合算法可以借助二进制数,对于每一个集合中的元素,它的命运就两种,选或者不选,这个可以映射到二进制数的0和1。

  • Full Permutation
//
// Created by mayusheng on 2017/9/27.
//
#include <iostream>
#include <vector>
#ifndef UNTITLED_FULL_PERMUTATION_HPP
#define UNTITLED_FULL_PERMUTATION_HPP
void full_permutation(std::vector<int> & array){//全排列算法
std::sort(array.begin(),array.end());
for(auto x: array)
std::cout<<x;
std::cout<<std::endl;
while(true)
{//查找最大的符合array[i]<array[i+1]的index i;
int it = -1;
for(int i=0;i<array.size()-1;++i)
{
if(array[i]<array[i+1])
it = i;
}
if(it == -1)//从顺序到逆序,array逆序之时,就是循环结束之时
break;
//从以上找到的index为it ,从it->array.size(),寻找大于array[it]的最小数,与array[it]交换
u_int dis_min = std::numeric_limits<u_int>::max();
int biger_s = -1;
for(int i=it+1;i<array.size();++i)
{
if(array[i]>array[it]) {
if(array[i]-array[it]<dis_min) {
dis_min = array[i] - array[it];
biger_s = i;
}
}
}
if(biger_s!=-1)
std::swap(array[it],array[biger_s]);
u_long begin=it+1,end = array.size()-1;
//将it+1到array.size()-1区间内的元素倒置,此时形成的新序列,就为字典序的下一个序列
while(begin<end)
{
std::swap(array[begin],array[end]);
++begin;
--end;
}
for(auto & x: array)
std::cout<<x;
std::cout<<std::endl;
}
}
#endif //UNTITLED_FULL_PERMUTATION_HPP
  • Combinatorial
//
// Created by mayusheng on 2017/9/27.
//
#include <iostream>
#include <vector>
#ifndef ALGORITHM_COMBINATORIAL_HPP
#define ALGORITHM_COMBINATORIAL_HPP
void combinatorial(std::vector<int> arrry){
u_long up_limit=0;
for(u_long i = 0;i<arrry.size();++i)
{
up_limit=up_limit*2 + 1;
}
//生成二进制位全为1的数,长度大小和array.size()一致
std::cout<<"*"<<up_limit<<std::endl;
//从0->up_limit,产生的数字查看二进制位,是1就选择该index下对应的元素。
for(u_long i=0;i<=up_limit;++i)
{
u_long it = i;
for(int j=0;j<arrry.size();++j)
{
if((it>>j)%2==1)
std::cout<<arrry[j];
}
std::cout<<std::endl;
//会显示一个空行,为空集
//注意,array元素不要超过128个,u_long最大为128bit(x64)
}
}
#endif //ALGORITHM_COMBINATORIAL_HPP