반복되는 값이 있는 경우를 포함하여 배열의 모든 순열을 생성하는 방법은 무엇입니까?

배열의 순열

주어진 고유한 정수 배열의 총 수를 구하고 배열의 가능한 모든 순열을 나열합니다.

코드

다음 코드는 배열의 순열을 찾는 재귀 알고리즘을 제공합니다.

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;
    }
}

이 알고리즘은 첫 번째 요소를 배열의 다른 각 요소와 교체한 다음 재귀적으로 호출하여 배열의 모든 순열을 생성합니다. 나머지 배열에 대한 알고리즘.

반복되는 경우에 대한 반복자 및 확장 값

이 알고리즘의 단점은 배열에서 반복되는 값의 경우를 처리하지 못한다는 것입니다. 이 경우를 처리하기 위해 재귀 대신 스택을 사용하도록 알고리즘을 수정할 수 있습니다. 다음 코드는 배열의 순열을 찾기 위한 반복 알고리즘을 제공합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!