무차별 대입 없이 n번째 순열을 효율적으로 찾을 수 있는 방법은 무엇입니까?-PHP 튜토리얼-php.cn

무차별 대입 없이 n번째 순열을 효율적으로 찾을 수 있는 방법은 무엇입니까?

Patricia Arquette

풀어 주다： 2024-12-06 20:49:10

원래의

602명이 탐색했습니다.

How Can We Efficiently Find the nth Permutation Without Brute Force?

무차별 대입 없이 n번째 순열 찾기

요소 배열로 표현되는 순열이 주어지면, 그 사이의 모든 순열을 계산하지 않고도 n번째 순열을 효율적으로 계산하는 것이 가능합니까?

답은 계승분해에 있습니다. 순열의 사전순 순서를 고려하세요. 순열의 인덱스를 계승 분수로 분해함으로써 특정 순열을 도출할 수 있습니다.

가장 높은 계승부터 시작하여 계승으로 인수분해를 수행합니다.
몫은 다음을 나타냅니다. 순열 배열의 인덱스 같거나 낮을 수 있는 이전 값을 고려하여 조정합니다.

이 접근 방식을 사용하면 무차별 반복 작업 없이 원하는 순열로 직접 이동할 수 있습니다.

예를 들어 , 배열 {A, B, C}가 주어지면 크기 2의 세 번째 순열에 대한 계승 분해는 (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1. 이는 첫 번째 요소(B)에 해당하고 그 다음에는 0번째 요소(A)에 해당합니다.

다음 C 구현에서는 이 기술을 보여줍니다.

void ithPermutation(const int n, int i) {
    int *fact = (int *)calloc(n, sizeof(int));
    int *perm = (int *)calloc(n, sizeof(int));

    // Compute factorial numbers
    fact[0] = 1;
    for (int k = 1; k < n; k++) {
        fact[k] = fact[k - 1] * k;
    }

    // Compute factorial code
    for (int k = 0; k < n; k++) {
        perm[k] = i / fact[n - 1 - k];
        i = i % fact[n - 1 - k];
    }

    // Readjust values to obtain the permutation
    for (int k = n - 1; k > 0; k--) {
        for (int j = k - 1; j >= 0; j--) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    // Print permutation
    for (int k = 0; k < n; k++) {
        printf("%d ", perm[k]);
    }
    printf("\n");

    free(fact);
    free(perm);
}

로그인 후 복사

ithPermutation(10, 3628799)을 호출하면 10의 마지막 순열이 반환됩니다. 요소: