Go语言视频零基础入门到精通

五菱

字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。我们来看看他的思路吧：
它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453....逐渐地从后往前递增。
看看算法描述：
    首先，将待排序列变成有序（升序）序列。然后，从后向前寻找，找到相邻的两个元素，Ti<Tj，（j=i+1)。如果没有找到，则说明整个序列已经是降序排列了，也就是说到达最终状态54321了。此时，全排列结束。

    接着，如果没有结束，从后向前找到第一个元素Tk，使得Tk>Ti(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij.
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
  自右至左找出排列中第一个比右边数字小的数字4    839647521
  在该数字后的数字中找出比4大的数中最小的一个5    839647521
  将5与4交换 839657421
  将7421倒转 839651247
  所以839647521的下一个排列是839651247。
  839651247的下一个排列是839651274。
(注：何谓按字典序排列
对两个字符串，先按字典顺序比较第一个字符，第一个字符相同的，比较第二字符，依此类推。。。
例：字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。）
[pre]import java.util.Scanner;public class S1 {        /**         * @param args         */        public static void main(String[] args) {                // TODO 自动生成方法存根                S1 a = new S1();                Scanner input = new Scanner(System.in);                System.out.print("请输入要排列的元素有多少种:");                int count = input.nextInt();                int[] p = new int[count];                for (int i = 1; i <= p.length; i++) {                        p[i-1] = i;                }                boolean con;                do {                        a.pr(p);//输出排列p                        con = a.next(p);//求出按字典序排列的下一个排列p                } while (con);        }        public int indexof(int[] n) {                int index = -1;                for (int i = n.length - 1; i >= 1; i--) {                        if (n[i-1] < n) {                                index = i - 1;                                break;                        }                }                return index;        }        public int indexmin(int ini, int[] n) {                int index = n.length - 1;                int min = n[ini + 1];                for (int i = ini + 1; i < n.length; i++) {                        if (n <= min && n > n[ini]) {                                min = n[ i ];                                index = i;                        }                }                return index;        }        public void swap(int index1, int index2, int[] n) {                int temp;                temp = n[index1];                n[index1] = n[index2];                n[index2] = temp;        }        public void oppositeDirection(int index1, int[] n) {           for (int i = index1 + 1, j = n.length - 1, k = 0, temp; k <= (n.length - i) / 2; i++, j--, k++) {                        temp = n;                        n = n[j];                        n[j] = temp;                }        }        public boolean next(int[] n) {                int index1 = indexof(n);                if (index1 == -1) {                        return false;                }                int index2 = indexmin(index1, n);                swap(index1, index2, n);                oppositeDirection(index1, n);                return true;        }        public void pr(int[] n) {                for (int i = 0; i < n.length; i++) {                        System.out.print(n + "  ");                }                System.out.println();        }}[/pre]运行：

C:\bat>java S1
请输入要排列的元素有多少种:3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
C:\bat>java S1
请输入要排列的元素有多少种:4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1