집합의 n번째 순열을 어떻게 효율적으로 찾을 수 있나요?-PHP 튜토리얼-php.cn

집합의 n번째 순열을 어떻게 효율적으로 찾을 수 있나요?

Linda Hamilton

풀어 주다： 2024-12-07 06:46:16

원래의

345명이 탐색했습니다.

How Can We Efficiently Find the n-th Permutation of a Set?

n번째 순열 식별을 위한 효율적인 알고리즘

순열을 나타내는 요소 배열이 주어지면 이 질문은 다음과 같은 알고리즘의 가능성을 탐구합니다. 이전의 모든 순열을 계산하지 않고 n번째 순열을 효율적으로 계산합니다.

팩토라딕 순열 분해

이 솔루션은 팩토라딕 분해의 개념을 활용합니다. 계승으로 연속적인 나눗셈을 수행함으로써 순열 인덱스를 일련의 몫으로 분해합니다. 이 시퀀스는 원하는 순열을 나타냅니다.

몫 조정

그러나 초기 몫은 이전 값의 영향을 무시합니다. 따라서 조정 단계가 필요합니다. 각 몫에 대해 더 작거나 같은 이전 몫의 수만큼 값을 증가시킵니다.

구현

알고리즘의 C 구현이 제공됩니다. 아래:

void ithPermutation(const int n, int i) {
    int *fact = new int[n], *perm = new int[n];

    // Compute factorials
    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 %= fact[n - 1 - k];
    }

    // Adjust values for 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++)
        cout << perm[k] << " ";
    cout << "\n";

    delete[] fact;
    delete[] perm;
}

로그인 후 복사

예

예를 들어 ithPermutation(10, 3628799)는 10개 요소의 마지막 순열을 반환합니다.