繰り返される要素の処理を含め、配列の一意の順列をすべて生成するにはどうすればよいですか?

配列の順列

配列の順列は、配列の要素を異なる順序で配置する可能なすべての方法です。たとえば、配列 [1, 2, 3] には次の順列があります:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

配列の順列を生成するアルゴリズムがいくつかあります。最も一般的なアルゴリズムの 1 つは、小さい配列の各置換の末尾に新しい要素を追加することによって、小さい配列のすべての置換を生成する再帰アルゴリズムです。

Java での再帰アルゴリズムの実装は次のとおりです。 :

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        for (int i = k; i < a.length; i++) {
            java.util.Collections.swap(a, i, k);
            permute(a, k + 1);
            java.util.Collections.swap(a, i, k);
        }
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        }
    }
}

上記のコードは、配列 a のすべての順列をconsole.

反復要素の処理

上記の再帰アルゴリズムは、反復要素を正しく処理しません。たとえば、配列 a に繰り返し要素が含まれている場合、アルゴリズムは重複した順列を生成します。

繰り返し要素を処理するには、ヒープ アルゴリズムと呼ばれる別のアルゴリズムを使用できます。ヒープのアルゴリズムは、配列の 2 つの要素を繰り返し交換することによって、配列のすべての順列を生成します。

Java でのヒープのアルゴリズムの実装は次のとおりです。

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 3, 4, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        } else {
            for (int i = k; i < a.length; i++) {
                if (i == k || a[i] != a[k]) {
                    java.util.Collections.swap(a, i, k);
                    permute(a, k + 1);
                    java.util.Collections.swap(a, i, k);
                }
            }
        }
    }
}

上記のコードは、すべての一意の順列を出力します。配列 a をコンソールに出力します。

以上が繰り返される要素の処理を含め、配列の一意の順列をすべて生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。