値が繰り返される場合を含む、配列のすべての順列を生成するにはどうすればよいですか?

配列の順列

個別の整数の配列が与えられた場合、合計数を見つけて、配列の可能な順列をすべてリストします。 array.

コード

次のコードは、配列の順列を見つけるための再帰アルゴリズムを提供します。

import java.util.*;

public class Permute {

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

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

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

このアルゴリズムは、すべての配列を生成します。最初の要素を配列内の他の各要素と交換し、残りの要素に対してアルゴリズムを再帰的に呼び出すことにより、配列を並べ替えます。 array.

反復子と値が繰り返される場合の拡張

このアルゴリズムの欠点は、配列内で値が繰り返される場合を処理できないことです。このケースに対処するには、再帰の代わりにスタックを使用するようにアルゴリズムを変更できます。次のコードは、配列の順列を見つけるための反復アルゴリズムを提供します。

import java.util.*;

public class Permute {

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

    private static void permuteIterative(int[] a) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        stack.push(0);
        visited.add(0);

        while (!stack.isEmpty()) {
            int k = stack.peek();
            if (k == a.length - 1) {
                System.out.println(Arrays.toString(a));
                stack.pop();
            } else {
                for (int i = k + 1; i < a.length; i++) {
                    if (!visited.contains(i)) {
                        swap(a, i, k);
                        stack.push(i);
                        visited.add(i);
                        break;
                    }
                }
                if (stack.peek() == k) {
                    stack.pop();
                    visited.remove(k);
                }
            }
        }
    }

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

このアルゴリズムは、スタックを使用して現在の順列を追跡します。アルゴリズムは、配列の最初の要素をスタックにプッシュすることから始まります。次に、アルゴリズムはスタックから要素を繰り返しポップし、配列内の次の未訪問の要素と交換します。配列内に未訪問の要素がもうない場合、アルゴリズムはその要素をスタックからポップし、スタック内の次の要素を続行します。

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