Go语言视频零基础入门到精通

javalearner

字典序列算法
                                                                                    
     字典序列算法是一种非递归算法。而它正是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.
  
  
  例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
   自右至左找出排列中第一个比右边数字小的数字4    839647521
   在该数字后的数字中找出比4大的数中最小的一个5    839647521
   将5与4交换 839657421
   将7421倒转 839651247
   所以839647521的下一个排列是839651247。
   839651247的下一个排列是839651274。
(注：何谓按字典序排列
对两个字符串，先按字典顺序比较第一个字符，第一个字符相同的，比较第二字符，依此类推。。。
例：字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。）

1. import java.util.Scanner;
   
2. public class S1 {
   
3.         /**
   
4.          * @param args
   
5.          */
   
6.         public static void main(String[] args) {
   
7.                 // TODO 自动生成方法存根
   
8.                 S1 a = new S1();
   
9.                 Scanner input = new Scanner(System.in);
   
10.                 System.out.print("请输入要排列的元素有多少种:");
    
11.                 int count = input.nextInt();
    
12.                 int[] p = new int[count];
    
13.                 for (int i = 1; i <= p.length; i++) {
    
14.                         p[i-1] = i;
    
15.                 }
    
16.                 boolean con;
    
17.                 do {
    
18.                         a.pr(p);//输出排列p
    
19.                         con = a.next(p);//求出按字典序排列的下一个排列p
    
20.                 } while (con);
    
21.         }
    
22.         public int indexof(int[] n) {
    
23.                 int index = -1;
    
24.                 for (int i = n.length - 1; i >= 1; i--) {
    
25.                         if (n[i-1] < n[i]) {
    
26.                                 index = i - 1;
    
27.                                 break;
    
28.                         }
    
29.                 }
    
30.                 return index;
    
31.         }
    
32.         public int indexmin(int ini, int[] n) {
    
33.                 int index = n.length - 1;
    
34.                 int min = n[ini + 1];
    
35.                 for (int i = ini + 1; i < n.length; i++) {
    
36.                         if (n[i] <= min && n[i] > n[ini]) {
    
37.                                 min = n[ i ];
    
38.                                 index = i;
    
39.                         }
    
40.                 }
    
41.                 return index;
    
42.         }
    
43.         public void swap(int index1, int index2, int[] n) {
    
44.                 int temp;
    
45.                 temp = n[index1];
    
46.                 n[index1] = n[index2];
    
47.                 n[index2] = temp;
    
48.         }
    
49.         public void oppositeDirection(int index1, int[] n) {
    
50.            for (int i = index1 + 1, j = n.length - 1, k = 0, temp; k <= (n.length - i) / 2; i++, j--, k++) {
    
51.                         temp = n[i];
    
52.                         n[i] = n[j];
    
53.                         n[j] = temp;
    
54.                 }
    
55.         }
    
56.         public boolean next(int[] n) {
    
57.                 int index1 = indexof(n);
    
58.                 if (index1 == -1) {
    
59.                         return false;
    
60.                 }
    
61.                 int index2 = indexmin(index1, n);
    
62.                 swap(index1, index2, n);
    
63.                 oppositeDirection(index1, n);
    
64.                 return true;
    
65.         }
    
66.         public void pr(int[] n) {
    
67.                 for (int i = 0; i < n.length; i++) {
    
68.                         System.out.print(n[i] + "  ");
    
69.                 }
    
70.                 System.out.println();
    
71.         }
    
72. }

复制代码

运行：
  C:at>java S1
请输入要排列的元素有多少种:3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 C:at>java S1
请输入要排列的元素有多少种:4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1   
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/24/000521718.zip