재귀 및 비재귀 알고리즘을 사용하여 배열의 모든 순열을 어떻게 생성할 수 있습니까?

배열의 순열: 심층 설명

배열의 순열을 생성하려면 요소가 어떻게 배열되어 있는지 이해하는 것이 중요합니다. 순열에는 배열 요소를 재배열하여 새 시퀀스를 만드는 작업이 포함됩니다. n개의 요소가 있는 배열의 가능한 순열 수는 n!으로 제공됩니다.

재귀 알고리즘

순열을 생성하는 한 가지 방법은 재귀 접근 방식을 사용하는 것입니다. 반복적으로 요소를 교환하고 나머지 배열 요소에 순열을 적용합니다.

public static void permute(java.util.List<Integer> arr, int k) {
    for (int i = k; i < arr.size(); i++) {
        java.util.Collections.swap(arr, i, k);
        permute(arr, k + 1);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        System.out.println(java.util.Arrays.toString(arr.toArray()));
    }
}

이 알고리즘은 시작됩니다. 첫 번째 요소를 나머지 요소 각각과 교환하여 그런 다음 나머지 요소에 동일한 작업을 반복적으로 적용합니다. 각 재귀 호출 후에 요소는 원래 위치로 다시 교체됩니다.

비재귀 알고리즘

반복 접근 방식의 경우 다음 단계를 고려하세요.

1. 오름차순으로 정렬된 배열부터 시작하세요. order.
2. 시퀀스가 내림차순이 아닌 첫 번째 인덱스를 찾습니다(예: a[i] < a[i-1]).
3. 값이 내림차순인 마지막 인덱스를 찾습니다. a[i-1]보다 크거나 같습니다.
4. a[i-1]을 마지막 요소와 교환합니다. index.
5. 배열의 꼬리에 있는 요소 순서를 반대로 바꿉니다(인덱스 i-1 뒤).

예: 배열 순열 [3, 4, 6 , 2, 1]

재귀 알고리즘:

1. 3을 4로 바꾸기: [4, 3, 6, 2, 1]
2. 재귀적으로 [4, 3, 6, 2, 1] 치환
3. 3을 6으로 바꾸기: [4, 6, 3, 2, 1]
4. 재귀적으로 순열 [4, 6, 3, 2, 1]
5. 모든 순열이 생성될 때까지 계속

비재귀적 알고리즘:

1. [1, 2, 3, 4, 6]으로 시작(오름차순 정렬)
2. 순서가 내림차순이므로 3단계로 진행
3. a[i] < a[i-1]: i = 4, 3 < 4
4. a[j] >= a[i-1]: j = 5인 마지막 인덱스를 찾습니다. 6 >= 3
5. a[i-1]을 다음과 교체합니다. a[j]: [1, 2, 6, 3, 4, 5]
6. 배열의 꼬리를 뒤집습니다: [1, 2, 3, 4, 5, 6]
7. 배열이 내림차순이 될 때까지(모든 순열이 생성되었음을 나타냄) 3~6단계를 반복합니다.

두 알고리즘의 결과 동일합니다. 가능한 모든 순열이 생성되고 인쇄됩니다.

위 내용은 재귀 및 비재귀 알고리즘을 사용하여 배열의 모든 순열을 어떻게 생성할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!