排列与组合的算法实现

由于老师提出了全排列问题。我心血来潮，将组合也弄了一下。现在写篇日志记录一下。

全排列

目前我所知道的全排列算法有三种，下面一一介绍：

（1）分治算法：这个算法利用了分而治之的思想。我们先从2个数开始，比如说4,5，他们的全排列只有两个45和54。如果在前面加个3,那么全排列就是345,354,也就是3(54)，括号表示里面的数的全排列。当然还有4(35)，5(34)...写到这里，各位看官应该已经看出点门道了吧。三个数的全排列，可以分为三次计算，第一次计算3和(45)的全排列，第二次计算4和(35)的全排列.....也就是说，将序列第一个元素分别与它以及其后的每一个元素代换，得到三个序列，然后对这些序列的除首元素外的子序列进行全排列。思想其实还是挺简单的：

代码实现如下：

Code:

//input 8 12.61s consumed
//input 8 11.72s consumed remove '-' in the printed array
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LENGTH 27
int n=0;
void permute(int[],int,int);
void swapint(int &a,int &b);
void printIntArray (int[],int);
//Function Implementation
void swapint(int &a,int &b){
int temp;
temp = a;
a = b;
b = temp;
}
void printIntArray(int target[],int length){
int i;
for (i=0;i<length;i++) printf ("%d",target[i]);
printf ("/n");
}
void permute(int target[],int begin,int end){
if (begin==end) {
printIntArray(target,end+1);
n++;
return;
}
int i;
for (i=begin;i<=end;i++){
swapint(target[begin],target[i]);
permute(target,begin+1,end);
swapint(target[begin],target[i]);
}
}
//test Functions
void testPermute(){
int len;
scanf ("%d",&len);
int *testcase =(int *)malloc(len*sizeof(int));
int i;
for (i=0;i<len;i++) testcase[i]=i+1;
permute(testcase,0,len-1);
}
//Main Function
void main(){
testPermute();
printf ("n=%d",n);
}

需要注意的是交换了元素，然后进行递归对子序列进行全排列之后，需要将元素的位置换回来。这是为了要还原现场，也就是说递归函数permute的形参target数组在内存中只有一个，递归调用的时候，入栈的只是一个数组指针，递归对子序列进行全排列之后，必定会对原序列造成一定的乱序。因此每次递归之后，都需要还原现场。

当然还有一个方法是将数组放在一个结构体中，而且还不能使用指针哦。参数调用的时候也不能使用引用。这样递归的时候，内存中才会生成新的结构体，当然也有新的数组了。就不会影响其他的操作，不过可想而知，这样写多浪费内存空间，当然也浪费时间。

（2）字典序列算法

字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。我们来看看他的思路吧：

它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453....逐渐地从后往前递增。

看看算法描述：

首先，将待排序列变成有序（升序）序列。

然后，从后向前寻找，找到相邻的两个元素，Ti<Tj，（j=i+1)。如果没有找到，则说明整个序列已经是降序排列了，也就是说到达最终状态54321了。此时，全排列结束。

接着，如果没有结束，从后向前找到第一个元素Tk，使得Tk>Ti(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij.

算法是很清晰的。看看代码：

Code:

#include <stdio.h>
#include <stdlib.h>
//function definition
void Swap(int &a,int &b);
void Reverse (int[],int,int);
void printArray (int[],int);
int nextPermutation(int[],int);
void Swap(int &a,int &b){
int tmp;
tmp=a;
a=b;
b=tmp;
}
void Reverse(int target[],int begin,int end){
while (begin<end){
Swap(target[begin],target[end]);
begin++;
end--;
}
}
//function implementation
int nextPermutation(int target[],int end){
int i,j;
for (i=end-1;i>=0;i--)
if (target[i]<target[i+1]) break;
if (i<0) return 0; //means the permutation is over
j=i+1;
int k;
for (k=end;target[k]<=target[i];k--);
Swap(target[i],target[k]);
Reverse(target,j,end);
return 1;
}
void printArray (int target[],int length){
int i;
for (i=0;i<length;i++) printf ("%d-",target[i]);
printf ("/n");
}
//test function
void testPermute(){
printf ("input a number:");
int n;
scanf ("%d",&n);
int i;
int * testcase = (int*)malloc(n*sizeof(int));
for (i=0;i<n;i++) testcase[i]=i+1;
printArray (testcase,n);
while (nextPermutation(testcase,n-1)){
printArray (testcase,n);
}
}
//main function
void main(){
testPermute();
}

代码完全按照算法来做，大家应该不难看懂。我就不废话了。

（3）深搜回溯算法

深度搜索，判重，回溯，这个算法应该算是一个基础了。其中八皇后问题是它的经典应用。说实话感觉它就像个万金油一样，在啥地方都能使，但是就是不一定好使就对了。不过还是要实现一下。

其实细想一下，全排列跟八皇后问题是一样一样的。也是穷举一个数列，只是八皇后对数列的条件跟严格，也即是判重函数不同而已。没有区别的。看看代码：

Code:

//n=8 Time Consumed 11.78s
#include <stdio.h>
#include <stdlib.h>
//function definition
void printArray (const int[],int);
bool isExist(const target[],int);
void permute(int[],const int,int);
//function implementation
void printArray(const int target[],int n){
int i;
for (i=0;i<n;i++)
printf ("%d",target[i]);
printf ("/n");
}
bool isExist(const int target[],int pos){
if (pos==0) return false;
int i;
for (i=0;i<pos;i++)
if (target[i]==target[pos]) return true;
return false;
}
void permute (int target[],const int n,int i){
if (i==n) {
printArray(target,n);
return;
}
for (target[i]=1;target[i]<=n;target[i]++)
if (isExist(target,i) == false) permute(target,n,i+1);
//target[i]=1;
return;
}
//test functions
void testPermutation(){
int n;
printf ("Input a Number:");
scanf ("%d",&n);
int * testcase=(int*)malloc(n*sizeof(int));
int i;
for (i=0;i<n;i++) testcase[i]=1;
permute(testcase,n,0);
}
//main function
void main(){
testPermutation();
}

注意，我在递归函数permute中，回溯甚至没有将当时位置上的数消掉。看被注释掉的target[i]=1。而是直接在for循环中添加初始语句target[i]=1。这就表示说只要进行深一步搜索，都先将下一位置的数初始化掉。这样就不用在回溯时对当前位置的错误值进行处理了。更加简化了。

再看看非递归版的，也就是使用堆栈的形式：

Code:

// when n=8 time consumed 11.77s
#include <stdio.h>
#include <stdlib.h>
//function definition
void permute(int [],int);
void printArray(const int[],const int);
bool isExist(const int[],const int);
//function implementation
void printArray(const int target[],const int n){
int i;
for (i=0;i<n;i++)
printf ("%d",target[i]);
printf ("/n");
}
bool isExist(const int target[],int pos){
if (pos==0) return false;
int i;
for (i=0;i<pos;i++)
if (target[i]==target[pos]) return true;
return false;
}
void permute(int stack[],int n){
int sp=0; //stack pointer
while (sp>=0) {
stack[sp]++;
while (stack[sp]<=n && isExist(stack,sp)==true ) stack[sp]++;
if (stack[sp]<=n) {
//when stack is full,output the result
//and then backtrack
if (sp==n-1) {
printArray(stack,n);
sp--;
}
else {
//push stack, which means search foward
sp++;
stack[sp]=0;
}
}
else {
//backtrack
sp--;
}
}
return;
}
//test function
void testPermutation(){
int n;
printf ("Input a Number:");
scanf ("%d",&n);
int i;
int * testcase=(int*)malloc(n*sizeof(int));
for (i=0;i<n;i++) testcase[i]=0;
permute(testcase,n);
}
//main function
void main(){
testPermutation();
}

非递归形式算法思想是一样的，不过就是需要自己来维护一个堆栈。注意在循环中，需要首先对堆栈元素进行自加操作，不然的话，回溯之后，就不会改变堆栈值，而使程序陷入死循环。不过当然，你要使用do while来代替这种写法，那当然也是没有问题的。

我只是想说，只要是递归形式的算法，都可以用堆栈来实现非递归的形式。大家不妨来探讨一下这个一一对应的转换的具体形式。

组合

关于组合，我有一个比较帅的算法，在这里跟大家分享一下。呵呵。

这是非递归的算法，我感觉跟全排列的字典序列算法思想上比较像。

你看它是怎么实现的：

求n个数中的m个数的组合。

首先，初始化一个n个元素的数组（全部由0，1组成），将前m个初始化为1，后面的为0。这时候就可以输出第一个组合了。为1的元素的下标所对应的数。

算法开始：从前往后找，找到第一个10组合，将其反转成01，然后将其前面的所有1，全部往左边推，即保证其前面的1都在最左边。然后就可以按照这个01序列来输出一个组合结果了。

而如果找不到10组合，就表示说所有情况都输出了，为什么？你想，（以n=5,m=3为例）一开始是11100，最后就是00111，已经没有10组合了。

这种将问题转换为01序列（也就是真假序列）的想法值得我们考虑和借鉴。

最后看看实现代码：

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int l=0;
//function definition
void composition(const char [],int,int);
void printCompostion(const char[],const bool[],int);
//function implementation
void printCompostion(const char source[],const bool comp[],int n){
int i;
for (i=0;i<n;i++)
if (comp[i]==true) printf ("%c-",source[i]);
printf ("/n");
}
void compostion(const char* source,int n,int m){
bool * comp = (bool*)malloc(n*sizeof(bool));
int i;
for (i=0;i<m;i++) comp[i]=true;
for (i=m;i<n;i++) comp[i]=false;
printCompostion(source,comp,n);
l++;
while(true){
for (i=0;i<n-1;i++)
if (comp[i]==true&&comp[i+1]==false) break;
if (i==n-1) return; //all the compostion is found out
comp[i]=false;
comp[i+1]=true;
int p=0;
while (p<i){
while (comp[p]==true) p++;
while (comp[i]==false) i--;
if (p<i) {
comp[p]=true;
comp[i]=false;
}
}
printCompostion(source,comp,n);
l++;
}
}
//test function
void testCompostion(){
char* testcase = "abcdefghijklmno";
int n=strlen(testcase);
int m=7;
compostion(testcase,n,m);
}
//main function
void main(){
testCompostion();
printf ("total=%d/n",l);
}

01序列我是用bool类型来实现的。尽可能地少占用内存吧。而在实现将1往左移的步骤时，我是采用了将左边的0跟右边的1相调换的思想。

关于组合大家如果有更好的方法，不妨跟贴讨论哦。

（完）

排列与组合的算法实现

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希