求数组的全排列的非递归算法

求全排列一共有四种方法,字典序法,递增进位制数法,递减进位制数法,邻位对换法.我在这里讲最简单的字典序法.
这个生成法要求传进来的序列必须已经按从小到大人规律排过序.否则它不能生成正确的全排列.至于为什么用这个方法就可以生成全排列,我的知识有限,证明不了,只有拿来用了再说.
假定序列为a1,a2.... an (n > 0) ,如123456789,它从123456789开始,一直到987654321结束,中间有n个值,寻找这n个值需要做n步下面的操作:

1.找出比右边数字小的第一个数 找到这个数后,把它的位置记下来.设这个位置为pos_left;如果找不到,就说明排列完成了.
2.从右到左寻找第一个大于pos_left所在值的数,设为pos_right.
3.交换a[pos_left]与a[pos_right]的值.
4.逆转a[pos_left+1]到a[n]之间的值.
到此,寻找一个排列的步骤完成.

来个例子吧, 123, 做第1步,找到2比3小.pos_left = 2. 再做第2步,找到3比2大. pos_right = 3.然后做第3步,交换,得到 132 , 又因为pos_left后只有一个数,所以不用做逆转了.
这个太短了,干脆来个长点的 124653, 第1步找到4, pos_left = 3, 第2步找到5, pos_right = 5.然后交换得到125643, 再逆转得到125346, 从而得到新的排列.然后再对这个排列做上面4步,求出下一个排列....直到最后最后没有新排列可求出来.

java 代码

//here a permutation is a reordering of
//objects up to isomorphism
public boolean nextPermutation(int[] arr) {
  int last = Integer.MIN_VALUE;
  int n = arr.length;
  int p = n-1;
  for (;p>=0;p--) {
    if (arr[p]<last) {
      for (int j = n-1; j > p; j--) {
        if (arr[j]>arr[p]) {
          swap(arr,p,j);
          reverse(arr,p+1,n);
          return true;
        }
      }
      return false;
    }
    last = arr[p];
  }
  for (int i = 0; i < n; i++) arr[i]=i;
  return false;
}
public void swap(int[] arr, int ind1, int ind2) {
  int t = arr[ind1];
  arr[ind1] = arr[ind2];
  arr[ind2] = t;
}
public void reverse(int[] arr, int ind1, int ind2) {
  if (ind2<=ind1) return;
  for (int i = 0; i < (ind2-ind1)/2; i++) {
    swap(arr,ind1+i,ind2-1-(i));
  }
}