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

gnwe1990

字典序列算法
                                                                                   
    字典序列算法是一种非递归算法。而它正是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。）

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();
        }
}
运行：

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