Welcome 微信登录

首页 / 操作系统 / Linux / 用Java实现换位法生成全排列

用Java实现换位法生成全排列：
  1. import java.util.ArrayList;  
  2. import java.io.*;  
  3.   
  4. //换位法生成全排列   
  5. class ReplaceArrangement{  
  6.   
  7.     //从控制台读入数据   
  8.     private static String readDataFromConsole（String prompt） {  
  9.             BufferedReader br = new BufferedReader（new InputStreamReader（System.in））;  
  10.             String str = null;  
  11.             try {  
  12.                     System.out.print（prompt）;  
  13.                     str = br.readLine（）;  
  14.   
  15.             } catch （IOException e） {  
  16.                     e.printStackTrace（）;  
  17.             }  
  18.             return str;  
  19.         }  
  20.       
  21.     public static void main（String args[]）{  
  22.         class Node{  
  23.             int value = 0;// 元素值   
  24.             int dir = -1;// 0 : 左向箭头，1：有向箭头   
  25.         }  
  26.         System.out.println（"------换位法求全排列---------"）;  
  27.         System.out.println（"----第一个排列必须有序------"）;  
  28.           
  29.         int n = 0;//元素个数   
  30.         boolean flag = true;//从控制台读入数据不合法的话，该值一直为true   
  31.         while（flag）{  
  32.             try{  
  33.                 n = Integer.parseInt（readDataFromConsole（"请输入待排序元素个数: "））;  
  34.                 flag = false;  
  35.             }catch（Exception e）{  
  36.                 System.out.println（"请输入整数."）;  
  37.             }     
  38.         }  
  39.         flag = true;  
  40.         ArrayList<Node> nodes = new ArrayList<Node>（n）;  
  41.         Node node = null;  
  42.         for（int i = 1;i <= n;i++）{//排列初始化   
  43.             node =  new Node（）;  
  44.             while（flag）{  
  45.                 try{  
  46.                     node.value = Integer.parseInt（readDataFromConsole（"请输入第" + i + "个元素的值: "））;  
  47.                     flag = false;  
  48.                 }catch（Exception e）{  
  49.                     System.out.println（"请输入整数."）;  
  50.                 }  
  51.             }  
  52.             flag = true;  
  53.             node.dir = 0;  
  54.             nodes.add（node）;  
  55.             node = null;  
  56.         }  
  57.         for（int i = 0;i < n;i++）{  
  58.             System.out.print（nodes.get（i）.value + " "）;  
  59.         }  
  60.         System.out.println（）;  
  61.         int count = 1;  
  62.         while（true）{  
  63.             int j = 0; // 记录最大活动整数下标   
  64.             int Max = 0;  
  65.             for（int i = 0;i < n;i++）{ // 找出最大活动整数   
  66.                 if（0 == i && 0 == nodes.get（i）.dir）{  
  67.                     Max = Max;  
  68.                 }else if（n-1 == i && 1 == nodes.get（i）.dir）{ /// 此处应该是一次空操作，不可以轻易将Max 置为 0 ********   
  69.                     Max = Max;  
  70.                 }else if（0 == nodes.get（i）.dir && i>0 && nodes.get（i）.value>nodes.get（i - 1）.value && nodes.get（i）.value>Max）{  
  71.                     Max = nodes.get（i）.value;  
  72.                     j = i;  
  73.                 }else if（1 == nodes.get（i）.dir && i<n-1 && nodes.get（i）.value>nodes.get（i + 1）.value && nodes.get（i）.value > Max）{  
  74.                     Max = nodes.get（i）.value;  
  75.                     j = i;  
  76.                 }             
  77.             }  
  78.             //cout << endl;   
  79.             //cout << j << " " << Max << endl;   
  80.             if（ 0 == Max ） // 没有活动整数   
  81.                 break;  
  82.             if（ 0 == nodes.get（j）.dir）  // 交换最大整数与其相邻的数及方向   
  83.             {  
  84.                 int temp,dirtemp;  
  85.                 temp =nodes.get（j）.value;  
  86.                 dirtemp=nodes.get（j）.dir;  
  87.                 nodes.get（j）.value=nodes.get（j - 1）.value;  
  88.                 nodes.get（j）.dir=nodes.get（j - 1）.dir;  
  89.                 nodes.get（j - 1）.value=temp;  
  90.                 nodes.get（j - 1）.dir=dirtemp;  
  91.             }  
  92.             else if（ 1 == nodes.get（j）.dir）  
  93.             {  
  94.                 int temp,dirtemp;  
  95.                 temp =nodes.get（j）.value;  
  96.                 dirtemp=nodes.get（j）.dir;  
  97.                 nodes.get（j）.value=nodes.get（j + 1）.value;  
  98.                 nodes.get（j）.dir=nodes.get（j + 1）.dir;  
  99.                 nodes.get（j + 1）.value=temp;  
  100.                 nodes.get（j + 1）.dir=dirtemp;  
  101.             }  
  102.             for（int i=0;i<n;i++）//变换比最大活动整数大的数的方向   
  103.             {  
  104.                 if（nodes.get（i）.value>Max）  
  105.                 {  
  106.                     if（0 == nodes.get（i）.dir）{  
  107.                         nodes.get（i）.dir=1;  
  108.                     }else if（1 == nodes.get（i）.dir）{  
  109.                         nodes.get（i）.dir=0;  
  110.                     }  
  111.                 }  
  112.             }  
  113.             for（int i=0;i<n;i++）{  
  114.                 System.out.print（nodes.get（i）.value + " "）;  
  115.             }  
  116.             count++;  
  117.             System.out.println（）;  
  118.         }  
  119.         System.out.println（"排列总数为：" + count）;  
  120.     }  
  121. }  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图