数字の全配列

1671 ワード
leetcode

タイトルの説明


与えられた数字nは、1~nの全配列を出力する.
テストサンプルを入力:
3

出力テストサンプル
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

 

基本的な考え方

  • 実は自然言語の記述の角度から、この問題はよく理解しています.与えられた数字nに対して、その全配列は必然的にn個の数字からなる.まず最初の位置を固定することができて、この時n個の数字が選択することができて、それから2個目の位置を固定して、この時n-1個の数字が選択することができて、...、最後の数字を固定すると、選択できるのは1つだけです.だから全部でn!の結果です.
  • ですが、上記の考え方をどのようにプログラムで実現しますか?この中に一つの思想が使われている.それは遡及である.上記の問題を、n個の箱があり、各箱の番号が1~nであるという問題に等価にすることができる.同時に、私たちはn個のカードを持っていて、各カードの数字は1~nです.今、このn個のカードをこのn個の箱に入れるように要求しています.箱ごとにカードを1枚しか入れられません.全部で何種類の方法がありますか?
  • まずカード1を箱1に入れ、カード2を箱2に入れます...、カードnを箱nに入れると、最初の置き方が得られる.今私たちが考えなければならないのは、どのようにして第1の方法に基づいて第2の放法を得るかということです.このとき、最後の箱のカードを持ち上げて、最後から2番目の箱のカードも取り出すことができます.このとき、私たちの手には全部で2枚のカードが残っています.最後から2番目の箱についても、2つの選択肢しかありません.n-1番のカードはすでにn-1番の箱に入っているので、n番のカードをn-1番の箱に入れるしかありません.同様に、最後の箱については、n-1の番号のカードしか入れられません.この時,我々は第2の方法を得た.それから私たちは次に遡って、後の3つの箱のカードを出して、すべての箱のカードを出すまで分析します.

    • コード実装

    package leetcode.graphic.search;

import java.util.Scanner;

/**
 * @ : 1-n 
 * @program:summary
 * @author:peicc
 * @create:2019-09-15 17:17:25
 **/
public class FullPerm {
    static int n;
    static int[] box;// 
    static int[] visited;// 
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        box=new int[n];
        visited=new int[n+1];
        dfs(0);
    }
    public static void dfs(int step){
        if(step>=n){
            for (int i = 0; i

     

    1514:数値の整数次数@jobdu
    ブルーブリッジカップブラシ問題記録(1)