Welcome 微信登录

首页 / 操作系统 / 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 + " "）;  
  109.             for（int i = 0;i < num - 1;i++）{  
  110.                 System.out.print（n1[i] + ""）;  
  111.             }  
  112.             System.out.print（" "）;  
  113.             for（int i = 0;i < num;i++）{  
  114.                 System.out.print（s[i] + ""）;  
  115.             }  
  116.             System.out.println（）;  
  117.         }while（flag）;  
  118.     }  
  119. }  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图