The Permutation Algorithm for Arrays using Recursion

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Recursive Permutation Algorithm

At position 1, we have n choices, and at position 2, we have n-1 choices. The total number of permutations for n characters is N! (factorial).

The following C++ code gives a classic implementation of getting all permutations for given list/vector using Recursion. You might want to use the C++ next_permutation() or prev_permutation() to avoid re-inventing the wheel.

The recursive algorithm will partition the array as two parts: the permutated list and the remaining elements. Then, for current position e.g. 0, we can have n choices (by swapping A[0] to A[x] where x is from 0 to n-1), then we permutate the list recursively with current position advanced one position – remember to restore the position after the recursive calls.

Once the position reaches beyond the end – meaning we have exhausted the remaining elements, we add the current sequence into the final permutation list.

class Solution {
public:
    void permute(vector<int>& nums, int n, vector<vector<int>>& r) {
        if (n == nums.size()) {
            r.push_back(nums); // save this as one of the possibilities
        } else {
            for (int i = n; i < nums.size(); i ++) {
                swap(nums[i], nums[n]);
                permute(nums, n + 1, r); // placing next position
                swap(nums[i], nums[n]);  // restoring
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> r;
        permute(nums, 0, r);
        return r;
    }
};

When we have chosen k elements, we have n-k elements that can be sorted using recursion.

Generate Permutation Sequences using Next Permutation Algorithm

We can use The Next Permutation Algorithm in C++ (std::next_permutation) to generate all the permutation sequences:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> ans({nums});
        while (findNext(nums)) {
            ans.push_back(nums);
        }
        return ans;
    }
private:
    bool findNext(vector<int> &nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        } else {
            return false;
        }
        std::reverse(begin(nums) + i + 1, end(nums));
        return true;
    }
};

Of course, we don’t have to re-invent the wheel e.g. next_permutation is available in STL algorithm.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> ans({nums});
        while (next_permutation(begin(nums), end(nums))) {
            ans.push_back(nums);
        }
        return ans;
    }
};

See also: Teaching Kids Programming – Recursive Permutation Algorithm

Permutations and Combinations

• Using Bitmasking Algorithm to Compute the Combinations of an Array
• Teaching Kids Programming – Recursive Backtracking Algorithm to Compute the Combinations
• Teaching Kids Programming – Recursive Permutation Algorithm
• Teaching Kids Programming – Introduction to Permutation and Combination
• Teaching Kids Programming – Three Algorithms to Compute the Combination Number
• A Recursive Full Permutation Algorithm in Python
• The Permutation Iterator in Python
• GoLang: Full Permutation Command Line Tool
• The Permutation Algorithm for Arrays using Recursion
• Full Permutation Algorithm Implementation in BASH

–EOF (The Ultimate Computing & Technology Blog) —