We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Permutations III

Number: 3780

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an integer n, generate all permutations of the numbers 1 through n so that no two adjacent elements are both odd or both even (i.e. they alternate in parity). The list of all valid alternating permutations should be returned sorted in lexicographical order.

Key Insights

  • Use backtracking to generate all permutations by exploring one decision at a time.
  • At every decision point, check the parity of the last number in the current permutation and the candidate number to ensure they alternate (one odd, one even).
  • Iterating candidates in increasing order naturally produces lexicographical order.
  • Pruning invalid paths early reduces unnecessary exploration.

Space and Time Complexity

Time Complexity: O(n * n!) in the worst-case scenario as each permutation of length n is generated. Space Complexity: O(n) for the recursive call stack and O(n!) for storing all valid permutations.

Solution

We solve the problem using backtracking. We maintain a list (or array) that holds the current permutation. At each recursive call, we choose a number that has not yet been used, and we ensure that its parity is different from the last element added (if any). If the current permutation length equals n, it is valid and added to the result list. By iterating numbers in ascending order, the result set naturally becomes sorted in lexicographical order. The algorithm uses recursion and backtracking with a simple check on the parity condition, leveraging a boolean visited/used array or set to track the numbers in use.

Code Solutions

# Function to generate all alternating permutations using backtracking.
def alternating_permutations(n):
    results = []  # list to hold all valid permutations
    current = []  # current permutation path
    
    def backtrack():
        # If the current permutation has reached length n, add a copy to results.
        if len(current) == n:
            results.append(current.copy())
            return
        # Iterate over numbers 1 through n (ordered to maintain lexicographical order)
        for num in range(1, n + 1):
            # If current is not empty, check alternating parity condition with the last number.
            if current:
                # If both current last and num have the same parity, skip.
                if (current[-1] % 2) == (num % 2):
                    continue
            # If the number is already in current permutation, skip to avoid duplicates.
            if num in current:
                continue
            # Choose the candidate.
            current.append(num)
            # Explore further.
            backtrack()
            # Backtrack: remove the last added number.
            current.pop()

    backtrack()
    return results

# Example usage:
if __name__ == '__main__':
    n = 4
    result = alternating_permutations(n)
    print(result)
← Back to All Questions