打印经过限定后的数字排列

On October 18, 2010, in 算法, 笔试面试, by sponge

题目：给定6个数字，1，2，2，3，4，5，打印所有的排列

要求：

所有的4均不会出现在排列的第4个位置
数字3和数字5不能相邻
排列不能重复。

实现思想：

采用回朔的方法便利所有可能的排列，其中把不符合题目要求的去除。需要额外注意的是，数字中出现了两个2，如果单纯的遍历，会打印两次2在某个位置的排列，要注意把这个重复给去除。

C语言代码实现如下：

#include<stdlib.h>
#include<stdio.h>
 
int a[6]={1, 2, 2, 3, 4, 5 }; 
int b[6]; //用来存放排列好的序列
int pointer; //回朔指针
int total; //总的排列个数
int range(){
	int i;
	if(pointer == 6){
		printf("total:%d, range: %d %d %d %d %d %d \n", 
		++total, b[0], b[1], b[2], b[3], b[4], b[5]);
	}
	for(i=0; i<6; i++){
		if(a[i] == 0)
			continue;
 
		if(a[1]!=0 && i==2)
			continue; //防止重复使用2
 
		if(pointer>0 && (b[pointer-1]==3 && a[i] == 5 
		   || b[pointer-1]==5 && a[i]==3)) //防止3,5相邻
			continue;
 
		if(pointer == 3 && a[i]==4)
			continue; //防止数字4出现在位置4
 
		b[pointer] = a[i];
		pointer ++;
		a[i] = 0; //使用过的数字给设置成0，防止重复使用
		range();
		pointer --;
		a[i] = b[pointer];		
	}
}
 
int main(){
	range();
	return 0;	
}