美文网首页
枚举排列

枚举排列

作者: 小烈yhl | 来源:发表于2019-01-02 23:09 被阅读0次

    生成1-n的排列

    具体题目为,输入整数n,按字典序大小从小到大顺序输出前n个数的所有排列。
    例如输入n=3,则要求得出集合{1,2,3}所有的字典序排列。如{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}

    主要思路是利用解答树


    image.png

    1、在第一个循环中确定第一个数
    2、在第二个循环中确定第二个数
    .
    .
    n、在第n个循环中确定第n个数
    在n+1个循环中输出排列

    具体我是用java进行了实现

    public class Meiju {
    
        public  void print_permutation(int n, int A[], int cur) {
    
            if (cur == n) {  //当第n+1次调用此函数时,输出其排列
                System.out.print('[');
                for (int i = 0; i < n; i++) {
                    System.out.print(A[i] + " ");
                }
                System.out.print(']' + " ");
            }
    
            else
                for (int i = 1; i <= n; i++) {//尝试在A[cur]填入1~n
                    boolean ok = true;//重置ok初始值
                    for (int j = 0; j < cur; j++)
                        if (A[j] == i) ok = false;//如果i在A[0]-A[cur-1]中出现过,则不填入
                    if (ok) {//如果 i 没出现过则填入,出现过就继续循环,然后尝试填入i+1
                        A[cur] = i;
                        print_permutation(n, A, cur + 1);
                    }
                }
    
        }
    
        public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int A[] = new int[n];
            Meiju test = new Meiju();
            test.print_permutation(n, A, 0);
        }
    
    }
    

    相关文章

      网友评论

          本文标题:枚举排列

          本文链接:https://www.haomeiwen.com/subject/dzfxrqtx.html