Location>code7788 >text

Find the next arrangement problem and the full arrangement problem

Popularity：507 ℃/2025-03-09 22:11:47

Arrangement, dictionary order and next arrangement

Suppose you have an array or sequence,Next ArrangementIt refers to an arrangement that is larger in dictionary order than the current arrangement. If the current arrangement is already the largest arrangement, the next arrangement is the smallest arrangement.

For example, given an array[1, 2, 3], its next arrangement is[1, 3, 2];The next one is[2, 1, 3]; and for[3, 2, 1], it is already the largest arrangement; generally stipulate that the next arrangement is cycled to the smallest arrangement, that is,[1, 2, 3]。

The key to finding the next arrangement is to start from the current arrangement and use the properties of the dictionary order to find the next larger arrangement. The core steps of this algorithm are as follows:

  1. Scan the array from right to left, find the first drop position. Find an elementnums[i], makenums[i] < nums[i + 1]. The existence of this position means that the current arrangement can be larger. If no suchi, indicating that the current arrangement is already the largest arrangement.

  2. Find thenums[i]The smallest element of the big:turn upiThe smallest element that is larger than him (becauseiAfter that, they are all decreasing, that is, the last one).

  3. Swap elements:exchangenums[i]andnums[j], this step will ensure that the new arrangement is larger.

  4. The reversal part:turn out to beiThe element at the location has been replaced with a larger element; to ensure the minimum dictionary order of the arrangement, thenums[i+1]arrivenums[n-1]The part of the part changes from descending order to ascending order, and becomes the smallest arrangement.

Why is this right?

This is determined by the nature of the dictionary order. Each arrangement is composed of step-by-step exchange from left to right in the dictionary order.

  • First, find the first element in non-descending order from back to forward, and determine the "can be added" part.
  • It should exchange with the smallest element afterwards and re-order other elements to ensure that the added dictionary order is minimal.
void nextPermutation(vector<int>& nums) {
    int n = ();
    int i = n - 2;
    
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) swap(nums[i], nums[n - 1]);
    reverse(() + i + 1, ());
}

Many languages ​​(including C++) come with this function, and the complexity is obviously\(O(n)\)。

Full arrangement problem

The full arrangement problem is given a length asnarray, requiring all permutations of the array to be returned. For example, given an array[1, 2, 3], we need to find out[1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]These six arrangements.

One feature of a full permutation is that it generates all possible permutations and each permutation contains a different order of all elements in the array. All arrangements are available in total\(n!\), you can directly enumerate with the next arrangement method above, the calculation amount is\(n! * n\)

Another method of backtracking is to gradually fill each position in the arrangement through recursive way, and select different elements at each step, and finally output all possible arrangements.

  1. initialization: Starting with an empty arrangement, fill each position recursively.
  2. Recursive fill arrangement: Each time we recurse, we select one of the remaining unused numbers in order and put it into the current permutation, recursively generating the remaining parts.
  3. Backtracking: When recursion reaches the bottom (i.e., a permutation is generated), we go back to the previous layer and try other options.
  4. Termination conditions: When the length of the arrangement is equal to the length of the array, it means that an arrangement has been completely generated and the result is added.
void permute(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, vector<bool>& visited) {
    if (() == ()) {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < (); i++) {
        if (visited[i]) continue;

        visited[i] = true;
        path.push_back(nums[i]); 

        permute(nums, path, result, visited);

        path.pop_back();
        visited[i] = false;
    }
}
  • Time complexity: The time complexity of the full arrangement problem isO(n!), because generating all permutations requiresn!each arrangement needs to be generatedO(n)Time to copy and save.
  • Space complexity: The space complexity isO(n), recursive depth.

Expand knowledge

The order of arrangement originates from dictionary order, so this method is not only suitable for integer arrays, but can also be extended to other types of arrays (such as strings, characters, etc.). It is not required that the numbers be continuous1 ~ n。

<Previous Next>