歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

用Java實現用序數法生成全排列

用java實現用序數法生成全排列:

  1. import java.io.*;  
  2. import java.util.ArrayList;  
  3.   
  4. class Arrangement{  
  5.       
  6.     public static void main(String args[]){  
  7.         Arrangement arrangement = null;  
  8.         int num = 0;//要排序的個數   
  9.         boolean flag = true;//標志位,如果用戶輸入的待排序個數不合法,該值一直為true   
  10.         ArrayList<String> strs = new ArrayList<String>();  
  11.         while(flag){  
  12.             try{  
  13.                 num = Integer.parseInt(readDataFromConsole("請輸入待排序的個數:"));  
  14.                 flag = false;  
  15.             }catch(Exception e){  
  16.                 System.out.println("請輸入整數.");  
  17.             }  
  18.         }  
  19.         for(int i = 1; i <= num; i ++){  
  20.             strs.add(readDataFromConsole("請輸入第" + i + "個字符: "));   
  21.         }  
  22.         arrangement = new Arrangement(strs.toArray(new String[]{}));  
  23.         System.out.println("排列後的數據為:");  
  24.         arrangement.sort();  
  25.     }  
  26.       
  27.     private String[] str = null;  
  28.       
  29.     public Arrangement(String[] s){  
  30.         this.str = s;  
  31.     }  
  32.     //從控制台讀入數據   
  33.     private static String readDataFromConsole(String prompt) {  
  34.             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  35.             String str = null;  
  36.             try {  
  37.                     System.out.print(prompt);  
  38.                     str = br.readLine();  
  39.   
  40.             } catch (IOException e) {  
  41.                     e.printStackTrace();  
  42.             }  
  43.             return str;  
  44.         }  
  45.       
  46.     private void sort(){  
  47.         int num=str.length;  
  48.           
  49.         int[] n1 = new int[num -1];  
  50.         int[] nss = new int[num];  
  51.         String[] s = new String[num];  
  52.           
  53.         boolean flag = false;  
  54.         int x = 0;  
  55.           
  56.         do{  
  57.             if(x == 0){//第一遍初始化   
  58.                 for(int i = 0;i < num - 1;i ++){  
  59.                     n1[i] = 0;  
  60.                 }  
  61.             } else {//生成序數   
  62.                 for(int i = 0;i < num - 1;i ++){  
  63.                     if(n1[num - 2 - i] < i + 1){  
  64.                         n1[num - 2 - i] ++;  
  65.                         for(int j=num-1-i;j<num-1;j++){  
  66.                             n1[j] = 0;  
  67.                         }  
  68.                         break;  
  69.                     }  
  70.                 }  
  71.             }  
  72.             for(int i = 0;i < num - 1;i++){  
  73.                 if(n1[i] == (num - 1 - i)){  
  74.                     flag = false;  
  75.                 } else {  
  76.                     flag = true;  
  77.                     break;  
  78.                 }  
  79.             }  
  80.             for(int i = 0;i < num;i++){//標記位賦初值   
  81.                 nss[i] = 0;  
  82.             }  
  83.             for(int i = 0;i < num - 1;i++){//計算排列順序並為排列後的賦值   
  84.                 int hh = 0, j = 0;//記錄前邊總共移動的位數   
  85.                 do{  
  86.                     if(nss[num - 1 - hh] == 1){  
  87.                         hh++;  
  88.                         continue;  
  89.                     } else {  
  90.                         if(j == n1[i]){  
  91.                             break;//每個字母距最右端未填入的位置   
  92.                         } else {  
  93.                             hh++;  
  94.                             j++;  
  95.                         }  
  96.                     }  
  97.                 } while(true);  
  98.                 hh = num - 1 - hh;  
  99.                 s[hh] = str[num-1-i];  
  100.                 nss[hh] = 1;  
  101.             }  
  102.             for(int i = 0; i < num;i++){//查找空缺位   
  103.                 if(nss[i] == 0) {  
  104.                     s[i] = str[0];  
  105.                     break;  
  106.                 }  
  107.             }  
  108.             System.out.print(++x + "\t");  
  109.             for(int i = 0;i < num - 1;i++){  
  110.                 System.out.print(n1[i] + "");  
  111.             }  
  112.             System.out.print("\t");  
  113.             for(int i = 0;i < num;i++){  
  114.                 System.out.print(s[i] + "");  
  115.             }  
  116.             System.out.println();  
  117.         }while(flag);  
  118.     }  
  119. }  
Copyright © Linux教程網 All Rights Reserved