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

求全排列一共有四种方法,字典序法,递增进位制数法,递减进位制数法,邻位对换法.我在这里讲最简单的字典序法.
这个生成法要求传进来的序列必须已经按从小到大人规律排过序.否则它不能生成正确的全排列.至于为什么用这个方法就可以生成全排列,我的知识有限,证明不了,只有拿来用了再说.
假定序列为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 代码

public class Permulation {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4 };
        do {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + ",");
            }
            System.out.println();
        } while (new Permulation().nextPermutation(arr));

    }

    public boolean nextPermutation(int[] arr) {
        int postLeft = -1;
        for (int i = arr.length - 1; i > 0; i--) {
            if (arr[i - 1] < arr[i]) {
                postLeft = i - 1;
                break;
            }
        }
        if (postLeft < 0) {
            return false;
        }

        int postRight = -1;
        for (int i = arr.length - 1; i >= postLeft; i--) {
            if (arr[i] > arr[postLeft]) {
                postRight = i;
                break;
            }
        }
        swap(arr, postLeft, postRight);
        reverse(arr, postLeft + 1, arr.length);
        return true;
    }

    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) {
        for (int i = 0; i < (ind2 - ind1) / 2; i++) {
            swap(arr, ind1 + i, ind2 - 1 - (i));
        }
    }
}