整列

シーケンスを求める

これは,プログラマ問題における「小数点を検索する」問題を解決する際に,ソートアルゴリズムが出現して整理された内容である.
1、2、3等の数字があります.これを繰り返さないで、順番を引き出してみてください.
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
以上のように6つの方法が存在する.
1,2,3,4の場合、数字が多くなります.アルゴリズムでこれを実現するにはどうすればいいですか?

上図は再帰関数でABCアルファベットをソートする方法です.
まず、ABCの最初のアルファベットは何ですか.種類は3種類あります.(配列順をABCとする.)
A
B
C
上記の場合、1番目がAの場合、1番目のパラメータ[0]のAを1番目のパラメータ[0]Aに置き換える.(実際は変わっていません.)
1番目のパラメータがBに設定されている場合、1番目のパラメータ[0]のAは2番目のパラメータ[1]Bに置き換えられる.
1番目のパラメータがCに設定されている場合、1番目のパラメータ[0]のAを3番目のパラメータ[2]Cに置き換える.
[0] <-> [0]
[0] <-> [1]
[0] <-> [2]
1番目のパラメータは固定されており、2番目と3番目のパラメータについては、上記の手順を繰り返します.
[0]<->[0]この場合に限る.Aなら.
[0][1]<->[0][1]:2番目のパラメータ[1]のBと2番目のパラメータ[1]のBを変更する.A B C
[0][1]<->[0][2]:2番目のパラメータ[1]のBと3番目のパラメータ[2]のCを変更する.A C B
最後の様子を見る.
[0][1]<->[0][1]この場合に限る.
[0][1][2]<->[0][1][2]変わりません.A B C
[0][1]<->[0][2]この場合に限る.
[0][2][1]<->[0][2][1]変化なし.A C B
npkのシーケンスを求めます.
すなわち,nにおいてk個からなるシーケンスが要求される.
perm(int[] arr, int depth, int n, int k)

アレイarr:データの搬送と交換を継続するアレイ.

dept:現在ツリー構造でどのような深さの交換操作が行われているかに関する変数.すなわち、最初の深さであれば、0の位置で動作する.
最初のパラメータと最初のパラメータを交換します(1,2,3,4)
1番目と2番目のパラメータを交換します(2、1、3、4)
1番目と3番目のパラメータを交換します(3,1,2,4)
1番目と4番目の因子を交換しています.(4,1,2,3)

n:総配列中の数字を表し、配列の長さである.定価

k:いくつか抽出して並べ替えることを示し、固定値である.

private static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) {
            print(arr, k);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

depthを確認し、kに等しい場合はシーケンスを作成しません.私が欲しいのはk個の数字のシーケンスです.ここでは4つの数字を設定し、4に達すれば出力できるという意味です.
深さによってfor文の開始点が異なります.深さが0ならば、1 XXX、2 XXX、3 XXX、4 XXXを抜いて、だから全部で4回の循环が必要です.
depth 0->1 XXXが作成された場合、ここではpermが再帰関数で呼び出され、depth呼び出しは以下に示す.
制作depth 1->2 XXXではなく、12 XX、13 XX、14 XXを制作します.
depth 2->次の123 X
depth 3->1234が充填されます.
depth 4->出力.
depth 0->2 XXXは、上記の手順を作成し、繰り返します.
また、上記のコードはswap関数を再び呼び出します.最初に現れたswapによって、元の配列の順序が変更されています.したがって、次回シーケンスを作成しようとすると、値が変更されるため、正しい値を作成できません.だから再び元の配列に戻ります.
Ex)
1 2 3 4から変換[1]<->[2]は1 3 2 4となる.
ここで再帰呼び出しを行い,最後まで探索し,結果を出力して返し,配列は1 3 2 4である.
現在は[1]<->[3]を交換して1 4 3 2を処理する必要があるが,実際には1 4 2 3である.
そのため、思わぬ配列が処理されます.したがって,変更後の配列を元の配列に戻さなければならない.
最終コード

private static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) {
            print(arr, k);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] arr, int k) {
        for (int i = 0; i < arr.length; i++) {
            if (i == k - 1) System.out.println(arr[i]);
            else System.out.print(arr[i] + ", ");
        }
    }

リファレンス

PERMUTATIONアルゴリズム