论坛首页 → Java企业应用论坛 →

可遍历的全排列

浏览 4462 次
锁定老帖子 主题：可遍历的全排列
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • yiding_he
  • 等级: 五星会员
  • 性别:
  • 文章: 675
  • 积分: 566
  • 来自: 湖南
   发表时间：2007-03-07  
全排列是一种比较烦人的东西。本文讨论如何在不使用递归的情况下，让全排列结果能够被遍历（也就是实现 Iterator 接口），使得全排列的提供者能随时提供“下一个”全排列结果，直到给出所有的排列。

本文发表于：http://yiding-he.iteye.com

通常全排列是不可排序的，因为不同的遍历方式会按不同的顺序得到结果（如交换法、滚动法等）。我们需要选择一种方式，每次枚举都能得到唯一的结果，绝不重复。因为只有这样的方式才能用来遍历。那就是：

全排列树。想象一下，树中的每个节点就是一个全排列结果，其子节点是将其交换变化而来的。举个例子，
根节点为 (1, 2, 3) 的树，其一级子节点就是 (1, 2, 3) (2, 1, 3) (3, 1, 2) 三个，分别是从排列中的 [0]-[0] 交换、[0]-[1] 交换和 [0]-[2]交换得来的。而二级子节点，排列中的位置 [0] 不变，从 [1] 开始和其他位置交换。(2, 1, 3) 的子节点为 (2, 1, 3) 和 (2, 3, 1) 两个。以此类推到下一级，直到无法交换位置为止。实际上，(1, 2, 3) 的全排列树一共就是三层。

你可能看到了：这里不是有重复的节点了吗？没关系。虽然枝节点有重复，但叶子节点是绝无重复的。我们只需要遍历这棵树的最底层，就能得到所有全排列。

遍历的时候，如何确定“上一个”和“下一个”叶子节点的位置呢？用一个很直观的表示法：每个节点的子节点都从 0 开始标上号，根节点就不用标号了，然后根据叶子节点的路径将标号组合成一个数组，就是每个节点的位置。例如上面那棵树中的叶子节点(2, 1, 3)，位置就是 {1, 0}。它的下一个位置就是 {1, 1}，再下一个位置是 {2, 0}，不信把整个树画出来自己对对看。

实际上，因为叶子节点的位置都是绝对的，我就不一定非要从第一个结果来排起。给出任意一个排列结果，我都可以找到它在这棵树中的位置，然后直接求得下一个位置和下一个位置的排列结果。

基本的思路就是这些，然后就是用代码来实现。至于怎么思考实现的就略去了，下面是代码：
java 代码
 
  1. import sun.reflect.generics.reflectiveObjects.NotImplementedException;  
  2. import java.util.Iterator;  
  3.   
  4. /** 
  5.  * 全排列树 -- 可遍历的全排列 
  6.  */  
  7. class SortTree implements Iterator {  
  8.   
  9.     private int level;  
  10.   
  11.     private int[] defaultArr; // {1, 2, 3, 4, 5, ...} 这样一个数组  
  12.   
  13.     private int[] currentPosition;  
  14.   
  15.     public SortTree(int level) {  
  16.         this.level = level;  
  17.         init();  
  18.     }  
  19.   
  20.     private void init() {  
  21.         defaultArr = new int[level];  
  22.         for (int i = 0; i < level; i++) {  
  23.             defaultArr[i] = i;  
  24.         }  
  25.         currentPosition = getBeforeStartPosition();  
  26.     }  
  27.   
  28.     /** 
  29.      * 获得指定位置的全排列 
  30.      * 
  31.      * @param position 全排列在树中的位置 
  32.      * 
  33.      * @return 处于指定位置的全排列 
  34.      */  
  35.     public int[] getValue(int[] position) {  
  36.         int[] cloned = defaultArr.clone();  
  37.   
  38.         if (position.length != level - 1) {  
  39.             System.out.println("invalid position level");  
  40.             return new int[0];  
  41.         }  
  42.   
  43.         for (int i = 0; i < position.length; i++) {  
  44.             swap(cloned, i, i + position[i]);  
  45.         }  
  46.   
  47.         return cloned;  
  48.     }  
  49.   
  50.     /** 
  51.      * 获得指定的全排列的位置 
  52.      * 
  53.      * @param value 全排列中的一项 
  54.      * 
  55.      * @return 指定的项在全排列树中的位置 
  56.      */  
  57.     public int[] getPosition(int[] value) {  
  58.         int[] cloned = defaultArr.clone();  
  59.   
  60.         int[] position = new int[value.length - 1];  
  61.         for (int i = 0; i < value.length - 1; i++) {  
  62.             int pointer = 0;  
  63.             if (value[i] == cloned[i]) {  
  64.                 position[i] = 0;  
  65.             } else {  
  66.                 pointer++;  
  67.                 while (pointer < value.length) {  
  68.                     if (value[i] == cloned[pointer]) {  
  69.                         swap(cloned, i, pointer);  
  70.                         position[i] = pointer - i;  
  71.                     }  
  72.                     pointer++;  
  73.                 }  
  74.             }  
  75.         }  
  76.   
  77.         return position;  
  78.     }  
  79.   
  80.     /** 
  81.      * 获得下一个位置 
  82.      * 
  83.      * @param position 当前位置 
  84.      * 
  85.      * @return 下一个位置 
  86.      */  
  87.     public int[] getNextPosition(int[] position) {  
  88.         int[] result = position.clone();  
  89.         for (int i = result.length - 1; i >= 0; i--) {  
  90.             int upper = result.length - i;  
  91.             if (result[i] + 1 <= upper) {  
  92.                 result[i] += 1;  
  93.                 break;  
  94.             } else {  
  95.                 result[i] = 0;  
  96.             }  
  97.         }  
  98.         return result;  
  99.     }  
  100.   
  101.     /** 
  102.      * 是否还有下一个位置 
  103.      * 
  104.      * @param position 当前位置 
  105.      * 
  106.      * @return 如果还有则返回 true。 
  107.      */  
  108.     public boolean hasNextPosition(int[] position) {  
  109.         for (int i = 0; i < position.length; i++) {  
  110.             if (position[i] != defaultArr.length - i - 1) {  
  111.                 return true;  
  112.             }  
  113.         }  
  114.         return false;  
  115.     }  
  116.   
  117.     /** 
  118.      * 获得第一个位置之前的位置 
  119.      * 
  120.      * @return 第一个位置之前的位置 
  121.      */  
  122.     public int[] getBeforeStartPosition() {  
  123.         int[] position = new int[defaultArr.length - 1];  
  124.         position[position.length - 1] = -1;  
  125.         return position;  
  126.     }  
  127.   
  128.     private void swap(int[] ints, int a, int b) {  
  129.         int t = ints[a];  
  130.         ints[a] = ints[b];  
  131.         ints[b] = t;  
  132.     }  
  133.   
  134.     public boolean hasNext() {  
  135.         return hasNextPosition(currentPosition);  
  136.     }  
  137.   
  138.     public Object next() {  
  139.         currentPosition = getNextPosition(currentPosition);  
  140.         return getValue(currentPosition);  
  141.     }  
  142.   
  143.     public void remove() {  
  144.         throw new NotImplementedException();  
  145.     }  
  146. }  

使用方法：
java 代码
 
  1. SortTree tree = new SortTree(6);  
  2. int counter = 0;  
  3. while (tree.hasNext()) {  
  4.     int[] sort = (int[]) tree.next();  
  5.     printArray(sort);  
  6.     counter++;  
  7. }  
  8.   
  9. System.out.println("一共 " + counter + " 个结果");

代码仅用于检验思路，写法不甚严格。若要实用，最好能对参数加一些判断。
返回顶楼
         
论坛首页 → Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics