To solve this problem, we need to find the number of distinct permutations of a sequence of positive integers such that the sum of any two adjacent elements is a prime number.

Approach

1. Prime Check: First, we need a function to check if a number is prime. This helps us verify if the sum of adjacent elements in a permutation is prime.
2. Generate Unique Permutations: Since the sequence may contain duplicate elements, we generate all unique permutations of the sequence to avoid counting identical permutations multiple times.
3. Validate Permutations: For each unique permutation, we check if the sum of every pair of adjacent elements is a prime number. If all pairs satisfy this condition, the permutation is valid.

Solution Code

from itertools import permutations

def is_prime(s):
    if s <= 1:
        return False
    if s == 2:
        return True
    if s % 2 == 0:
        return False
    for i in range(3, int(s ** 0.5) + 1, 2):
        if s % i == 0:
            return False
    return True

def count_valid_permutations(sequence):
    unique_perms = set(permutations(sequence))
    valid_count = 0
    for perm in unique_perms:
        valid = True
        for i in range(len(perm) - 1):
            if not is_prime(perm[i] + perm[i+1]):
                valid = False
                break
        if valid:
            valid_count += 1
    return valid_count

# Example usage:
# sequence = [1, 1, 2]
# print(count_valid_permutations(sequence))  # Output: 3

Explanation

1. Prime Check Function: The is_prime function checks if a number is prime by testing divisibility up to the square root of the number. This is efficient for the small sums we encounter here.
2. Unique Permutations: Using itertools.permutations and converting the result to a set ensures we only consider distinct permutations, even if the sequence has duplicate elements.
3. Validation: For each permutation, we iterate through adjacent pairs and check if their sum is prime. If all pairs are valid, we count the permutation as valid.

This approach efficiently handles the problem constraints, especially for small sequences (up to 10 elements), where generating permutations is feasible. The use of unique permutations ensures we do not overcount, and the prime check ensures correctness.

Note: For larger sequences, more optimized approaches (like backtracking with pruning) might be needed, but this solution works well for typical problem constraints. However, the given approach is straightforward and effective for the problem's expected input size.

作者声明:本文包含人工智能生成内容。