开始写这个东西的目的是在网上看到了这样一个故事:
- 今天下午我亲眼目睹了计算机学生是怎样谈恋爱的:上交大GPA第一名某男约了T大计算机系花在五道口华联的哈根达斯吃冰淇淋,结果那男的去了之后就一直在那拿只铅笔写面试代码直到冰淇淋化成水了还在人肉debug。最后系花MM自己去前台付了钱怏怏而去。真是太悲催了…我听到题目是:给定字符串,打印全排列。
去重姑且不论(直接建立一个数组用于去重即可),全排列(递归)算法的思想是:
- 长度为N的字符串的全排列,等价于N个长度为N-1的字符串的全排列
- 为了实现1,需要将第一个字符不停的后N-1个字符之一进行交换,然后再对长度为N-1的字符串做同样的交换,直到最终不存在没有交换过的部分(当然,一个字符串与自身的交换也视为一种交换)
代码如下:
#include#include void swap(char *a,int i,int j){ char temp; temp = a[i]; a[i] = a[j]; a[j] = temp;}int fuck(char *a, int m,int n){ if(m == n) { printf("%s\t",a); } else { int i; for(i = m ; i <= n; i++) { { swap(a,m,i); fuck(a,m + 1,n); swap(a,m,i);//交换完的部分一定要换回来,不然后面就没法处理了 } } }}main(){ char s[10] = "123"; fuck(s,0,2);}