Algocademy Logo

Generate Valley Permutations in C++ (Time Complexity: O(n!))


Given a non-negative integer n, return all the valley permutations of length n.

A valley permutation is defined as a permutation that is a concatenation of two parts: a monotonically decreasing sequence and then a monotonically increasing sequence.

E.g. valley permutations follow this format: [p[0] < p[1] < p[2] < ... < p[k] > p[k+1] > p[k + 2] > ... > p[n]].


Example:

Input: n = 4

Output:[
    [1, 2, 3, 4],
    [2, 1, 3, 4],
    [3, 1, 2, 4],
    [3, 2, 1, 4],
    [4, 1, 2, 3],
    [4, 2, 1, 3],
    [4, 3, 1, 2],
    [4, 3, 2, 1]
]

Explanation:
Permutations suchs as [1, 4, 2, 3] are not valley because 1 < 4 > 2 < 3

Notes: n <= 10


Understanding the Problem

The core challenge of this problem is to generate all permutations of length n that follow the valley pattern. This pattern requires the sequence to first decrease and then increase. This type of permutation is useful in various applications such as sorting algorithms, data analysis, and more.

Potential pitfalls include generating permutations that do not follow the valley pattern or missing some valid permutations.

Approach

To solve this problem, we can use a backtracking approach to generate all permutations and then filter out those that do not follow the valley pattern.

1. **Naive Solution**: Generate all permutations of length n and then check each permutation to see if it follows the valley pattern. This approach is not optimal because it generates many invalid permutations.

2. **Optimized Solution**: Use backtracking to generate only those permutations that follow the valley pattern. This approach is more efficient as it avoids generating invalid permutations.

Algorithm

1. Use a backtracking function to generate permutations.

2. At each step, ensure that the current permutation follows the valley pattern.

3. If a valid permutation is found, add it to the result list.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to check if the current permutation is a valley permutation
bool isValley(const vector<int>& perm) {
    int n = perm.size();
    int i = 0;
    
    // Find the peak point
    while (i + 1 < n && perm[i] < perm[i + 1]) {
        i++;
    }
    
    // Check if the rest of the sequence is decreasing
    while (i + 1 < n && perm[i] > perm[i + 1]) {
        i++;
    }
    
    return i == n - 1;
}

// Backtracking function to generate valley permutations
void generateValleyPermutations(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        if (isValley(nums)) {
            result.push_back(nums);
        }
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        generateValleyPermutations(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

vector<vector<int>> valleyPermutations(int n) {
    vector<vector<int>> result;
    vector<int> nums(n);
    
    // Initialize the nums array with values from 1 to n
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    
    generateValleyPermutations(nums, 0, result);
    return result;
}

int main() {
    int n = 4;
    vector<vector<int>> result = valleyPermutations(n);
    
    for (const auto& perm : result) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Complexity Analysis

The time complexity of the backtracking approach is O(n!), as we generate all permutations of length n. The space complexity is O(n) due to the recursion stack and the storage of permutations.

Edge Cases

1. n = 0: The output should be an empty list.

2. n = 1: The output should be [[1]].

3. n = 2: The output should be [[1, 2], [2, 1]].

Testing

To test the solution comprehensively, include a variety of test cases:

  • Simple cases like n = 1 and n = 2.
  • Edge cases like n = 0.
  • Complex cases like n = 4 and n = 10.

Thinking and Problem-Solving Tips

1. Break down the problem into smaller parts and solve each part step-by-step.

2. Use backtracking to explore all possible solutions and prune invalid solutions early.

3. Practice solving similar problems to improve problem-solving skills.

Conclusion

Generating valley permutations is a classic problem that helps in understanding backtracking and permutation generation. By breaking down the problem and using an optimized approach, we can efficiently generate all valid valley permutations.

Additional Resources