Geneva Trading

01Minimum Number of Permutation Operations

A permutation of n numbers is a sequence where each number from 1 to n appears exactly once. For a given permutation p and any arbitrary array arr, a permutation operation is defined as For each index i (1 ≤ i ≤ n) temp_arr[i] = arr[p[i]] arr = temp_arr Given a permutation p of n numbers, start with any arbitrary array arr of n distinct elements and find out the minimum number of permutation operations (at least 1) needed in order to reach the original array. Since the answer can be quite large, return the answer modulo (10⁹ + 7)

Constraints

1 ≤ n ≤ 10⁵
1 ≤ p[i] ≤ n
p contains all distinct elements, the integers 1 through n

Example 1

Input:

p = [1, 3, 2]

Output:

Explanation: In the above example, n = 3. Taking any arbitrary array arr = [7, 8, 9] In each operation:

the element at index 1 stays at index 1
the element at index 2 gets mapped to index 3
the element at index 3 gets mapped to index 2 After applying operation for the first time on arr, the resulting array is [7, 9, 8]. After applying operation for the second time the resulting array is [7, 8, 9]. After 2 operations we get back to the original array, hence we return 2 as the answer.

解法

置换分解为若干个循环，恢复原数组所需的最少操作数 = 所有循环长度的最小公倍数。先 DFS 标记每个循环、记录长度，再对所有长度求 LCM；最后对 10⁹ + 7 取模。复杂度 O(n log MAX)，空间 O(n)。

from math import gcd
from typing import List

def min_permutation_operations(p: List[int]) -> int:
    MOD = 10**9 + 7
    n = len(p)
    seen = [False] * n
    ans = 1
    for i in range(n):
        if seen[i]:
            continue
        j = i
        length = 0
        while not seen[j]:
            seen[j] = True
            j = p[j] - 1
            length += 1
        ans = ans * length // gcd(ans, length)
    return ans % MOD

class Solution {
    int minPermutationOperations(int[] p) {
        final int MOD = 1_000_000_007;
        int n = p.length;
        boolean[] seen = new boolean[n];
        long ans = 1;
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            int j = i, length = 0;
            while (!seen[j]) {
                seen[j] = true;
                j = p[j] - 1;
                length++;
            }
            ans = ans / gcd(ans, length) * length % MOD;
        }
        return (int) ans;
    }

    private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
}

class Solution {
public:
    int minPermutationOperations(vector<int>& p) {
        const int MOD = 1'000'000'007;
        int n = p.size();
        vector<bool> seen(n, false);
        long long ans = 1;
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            int j = i, length = 0;
            while (!seen[j]) {
                seen[j] = true;
                j = p[j] - 1;
                ++length;
            }
            ans = ans / __gcd(ans, (long long) length) * length % MOD;
        }
        return (int) ans;
    }
};