반복되는 요소 처리를 포함하여 배열의 모든 고유 순열을 생성하는 방법은 무엇입니까?-C++-php.cn

반복되는 요소 처리를 포함하여 배열의 모든 고유 순열을 생성하는 방법은 무엇입니까?

Patricia Arquette

풀어 주다： 2024-12-27 22:53:11

원래의

366명이 탐색했습니다.

How to Generate All Unique Permutations of an Array, Including Handling Repeated Elements?

배열의 순열

배열의 순열은 배열의 요소를 다른 순서로 배열하는 가능한 모든 방법입니다. 예를 들어 배열 [1, 2, 3]에는 다음과 같은 순열이 있습니다.

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 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에 반복되는 요소가 포함되어 있으면 알고리즘은 중복 순열을 생성합니다.

반복되는 요소를 처리하기 위해 힙 알고리즘이라는 다른 알고리즘을 사용할 수 있습니다. 힙의 알고리즘은 배열의 두 요소를 반복적으로 교환하여 배열의 모든 순열을 생성합니다.

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