Chinaunix首页 | 论坛 | 博客

黑照的ChinaUnix博客blacksapper.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

blacksapper

  • 博客访问： 435282
  • 博文数量： 78
  • 博客积分： 2307
  • 博客等级： 上尉
  • 技术积分： 920
  • 用 户 组： 普通用户
  • 注册时间： 2011-06-04 00:31
个人简介

IT老鸟，信息安全硕士。

文章分类

全部博文（78）

文章存档

2017年（2）

2012年（21）

2011年（55）

我的朋友
最近访客
推荐博文
相关博文
实现全排列

分类： Java

2011-06-13 09:53:59

今天放两个方法，第二个方法Java编程实现。

题目是输入数字n实现1到n的全排列 比如n=2则输出 12   21

方法0，见《组合数学》老外的教材

用递推法。第1层 1

第二层    （1空）1（2空）

空里面就是“二”的位置，

在空里面输入数字2

第三层（1空）1（2空）2（3空）                             （1空）2（2空）1（3空）

空里面就是“三”的位置以此类推

方法1，使用循环移位

比如123456循环左移1位就是  234561  再左移两位就是 456123

这个方法可以只在头处加上第n个数。一样是递推的方法，从第1层开始一直到第n层。

我懒。上面两个方法都没有编程实现。现在说第三个方法

数学方法：

理论：线性代数里面有个关于逆序数的说明。说了一下没有了。可能是我用的教材版本太低了吧。

初始行列式每行都是1到n每列都一样。比如6吧

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

接下来展开行列式。不过不是行列式运算而是新的运算规则。从上往下开始按列展开比如

a11和A11（a11的代数余子式）

1和

23456

23456

23456

23456

23456

a21和A21比如

2和

13456

13456

13456

13456

13456

接下来每一项都要运算。那么ai1和Ai1一共有6个要运算的。运算方法很简单就是放到那里比如第一个'1'(A11)  // '1'表示数字

对代数余子式继续按照行列式展开的方法从上到下依次展开，运算就OK了。运算和结果放到那里输出。

下面给出数学证明。

假设是n0个数

1.......n0

1.......n0

.......

1.......n0

第一次有n0个数参与运算。所以第一次每个数字都运算了。

然后是代数余子式。这个定义是去掉aij所在的行（往下运算了），去掉所在的列（以后这个数都遇不上了）

继续算。所以每个数字都参与了运算。这个不包含正副号，都是正的，毕竟不是行列式。

再举个例子加深影响。n=3

 

行列式

123

123

123

a11是1                        a12是2          a13是3

A11是                          A12是            A13是

23                                13                   12

23                                13                   12

就是‘1’A11         '2'A12     '3'A13三项

继续

23

23展开就是   '2'和新A12 '3'和新A13 

结果是23  和32   和‘1’运算这个结果就是123   132

剩下的一样。数学方法完毕。

这个编程太麻烦了代数余子式咋表示？都是二维数组我很懒。估计要用n*n*n的空间。中间结果都要记录下来，还要标记和调试。复杂。数学方法舍弃。

观察行列式

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

选取一个数比如3

      3

1 2   4 5 6

1 2   4 5 6

1 2   4 5 6

1 2   4 5 6

接下来运算，最开始的想法是从3开始要么朝左运动，要么朝右（选数）。每个节点只访问一遍。有没有想起二叉树输出先序中序和后序的代码。这个也复杂。要么线索化要么用栈。头疼。

直接使用广度优先搜索。仿照那个最小生成树的两个算法和自己改进的深度优先算法（未公开）。直接一个已运算数组，一个未运算数组保存每个值。

相关信息见这个帖子。不过付兄使用的是库函数。我懒得去看库函数了。今天先放方法。

题目是输入数字n实现1到n的全排列  比如n=2则输出 12   21

方法0，见《组合数学》老外的教材

用递推法。第1层 1

第二层    （1空）1（2空）

空里面就是“二”的位置，

在空里面输入数字2

第三层（1空）1（2空）2（3空）                             （1空）2（2空）1（3空）

空里面就是“三”的位置以此类推

方法1，使用循环移位

比如123456循环左移1位就是  234561  再左移两位就是 456123

这个方法可以只在头处加上第n个数。一样是递推的方法，从第1层开始一直到第n层。

我懒。上面两个方法都没有编程实现。现在说第三个方法

数学方法：

理论：线性代数里面有个关于逆序数的说明。说了一下没有了。可能是我用的教材版本太低了吧。

初始行列式每行都是1到n每列都一样。比如6吧

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

接下来展开行列式。不过不是行列式运算而是新的运算规则。从上往下开始按列展开比如

a11和A11（a11的代数余子式）

1和

23456

23456

23456

23456

23456

a21和A21比如

2和

13456

13456

13456

13456

13456

接下来每一项都要运算。那么ai1和Ai1一共有6个要运算的。运算方法很简单就是放到那里比如第一个'1'(A11)  // '1'表示数字

对代数余子式继续按照行列式展开的方法从上到下依次展开，运算就OK了。运算和结果放到那里输出。

下面给出数学证明。

假设是n0个数

1.......n0

1.......n0

.......

1.......n0

第一次有n0个数参与运算。所以第一次每个数字都运算了。

然后是代数余子式。这个定义是去掉aij所在的行（往下运算了），去掉所在的列（以后这个数都遇不上了）

继续算。所以每个数字都参与了运算。这个不包含正副号，都是正的，毕竟不是行列式。

再举个例子加深影响。n=3

行列式

123

123

123

a11是1                        a12是2          a13是3

A11是                          A12是            A13是

23                                13                   12

23                                13                   12

就是‘1’A11         '2'A12     '3'A13三项

继续

23

23展开就是   '2'和A12 '3'和A12 

结果是23  和32   和‘1’运算这个结果就是123   132

剩下的一样。数学方法完毕。

这个编程太麻烦了代数余子式咋表示？都是二维数组我很懒。估计要用n*n*n的空间。中间结果都要记录下来，还要标记和调试。复杂。数学方法舍弃。

观察行列式

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

选取一个数比如3

      3

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


  2. public class quanpailie {
  3.  
  4.     /**
  5.      * @param args
  6.      */
  7.     //全排列函数，支持数字输入和字符 输入
  8. //这个是字符串的前面是使用过的字母串，后面是未使用的。
  9.     public void quanpailie(String usingstr,String unusestr,int n){
  10.   
  11.         char a[]=unusestr.toCharArray();
  12.         //终止部分
  13. //递归结束的部分
  14.         if(usingstr.length()==n-1)
  15.         {
  16.             usingstr+=a[0];
  17.         //输出结果,采用打印的方式
  18.         //System.out.print(usingstr+"/t");
  19.         }
  20.            
  21.   
  22.         //递归部分
  23.         for(int i=0;i<a.length;i++){
  24.             String newusingstr=usingstr+a[i];
  25.             String newunusestr="";
  26.             for(int j=0;j<a.length;j++)
  27.             {
  28.                 if(i==j)continue;
  29.                 newunusestr+=a[j];
  30.             }
  31.                
  32.             quanpailie(newusingstr,newunusestr,n);
  33.         }
  34.     }
  35.        
  36. /*好吧我承认刚才使用了字符串的库函数。这个是只支持数组的。稍微改一下在C语言中也能运行。参数分别是数组和数组长度。数组分别是使用的和未使用的,最后一个是总长。其实可以不要的- -b */
  37.     public void fastquanpailie(char using[],int uslength,char unuse[],int unuslength,int n){
  38. //已使用的字符串长度加1
  39.         char newusing[] =new char[uslength+1];
  40.            
  41.         for(int i=0;i<uslength;i++)
  42.             newusing[i]=using[i];//新数组中写入原数组的值
  43.         if(n-1==uslength){
  44.             newusing[uslength]=unuse[0];//最后位置写入最后一个字母
  45.                
  46.             //输出结果
  47.             for(int i=0;i<newusing.length;i++)
  48.                 System.out.print(newusing[i]);
  49.                
  50.             System.out.print("/t");//为了好看
  51.         }
  52.         //递归部分
  53.         for(int i=0;i<unuslength;i++){
  54.             //初始化
  55.             char newunuse[] =new char[unuslength-1];
  56.             newusing[uslength]=unuse[i];//新一位写入新数组最后
  57.             for(int j=0,k=0;j<newunuse.length;)//处理老数组
  58.             {
  59.                 if(i==j){k++;}
  60.                 newunuse[j]=unuse[k];
  61.                 k++;j++;
  62.             }
  63.             fastquanpailie(newusing,uslength+1,newunuse,unuslength-1,n);
  64.         }
  65.     }
  66.        
  67.     //辅助输入的方法。把原始输入转化成函数可以识别的输入
  68.     public void inputmode(String str){
  69.         char a[]=str.toCharArray();
  70.         int strlength=a.length;
  71.         quanpailie("",str,strlength);
  72.     }
  73.     public void fastinputmode(char array[],int length){
  74.   
  75.            
  76.         fastquanpailie(null,0,array,length,length);
  77.     }
  78.     //数字输入辅助
  79.     public void Noinputs(int n){
  80.         String str="";
  81.         for(int i=1;i<=n;i++){
  82.             str+=i;
  83.         }
  84.         inputmode(str);
  85.     }
  86.     //字母输入辅助,比如输入1输出a输入2输出ab
  87.     public void letterinputs(int n){
  88.         char letterarray[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n',
  89.                 'o','p','q','r','s','t','u','v','w','x','y','z'};
  90.         String str="";
  91.         for(int i=0;i<n;i++){
  92.             str+=letterarray[i];
  93.         }
  94.         inputmode(str);
  95.     }
  96.     public void letterinputs1(int n){
  97.         char letterarray[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n',
  98.                 'o','p','q','r','s','t','u','v','w','x','y','z'};
  99.   
  100.         fastinputmode(letterarray,n);
  101.     }
  102.     public static void main(String[] args) {
  103.   
  104.         System.out.println("这个是字母输入");
  105.         long starttime=System.currentTimeMillis();
  106.            
  107.         quanpailie a=new quanpailie();
  108.         //a.letterinputs(12);
  109.         a.letterinputs1(6);
  110.         long endtime=System.currentTimeMillis();
  111.         System.out.println();
  112.         System.out.println( "用时"+(endtime-starttime));
  113.     }
  114.   
  115. }

最后还是使用了库函数System.out.print()这个不让用你就看不到结果了。一共有两个方法。分别是数字输出和字母输出。数字的一位就是一个数字。1到9都没问题。10怎么办？用字母输出。a对应1z对应26.这样n小于等于26都没问题。

程序复杂度N*N 空间复杂度N*N而且是递归函数。所以实际上n=8都是一秒以内。到了9就很慢了。到了10 编译器eclipse无法响应。在cmd下编译运行都没问题。可以到12.到14的时候我没耐心了。实际上调用System.gc()好像速度更慢了。不知道以前的对象生命周期是咋结束的。

完

阅读(1600) | 评论(0) | 转发(0) |
0

上一篇：C/C++总结（ZT）

下一篇：数据结构之双链表

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6