Home
The Permutation Algorithm for Arrays using Recursion
Tags:, , ,

The Permutation Algorithm for Arrays using Recursion

April 21, 2016 No Comments algorithms, c / c++, Permutation, Recursion, recursive

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
};
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
};
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.

1
2
3
4
5
6
7
8
9
10
11

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;
    }
};
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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
863 words
Last Post: Binary Tree Level Order Traversal in C/C++
Next Post: C++ Coding Exercise - Longest Common Prefix

The Permanent URL is: The Permutation Algorithm for Arrays using Recursion

Related posts:

  1. Compute the Sliding Window Max using Monetone Decreasing Double-ended Queue Given a list of integers nums and an integer k, return the maximum values of...
  2. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  3. Compute the Indices of the Target Element in Array/List using Python or Javascript Given an array (or list), and a target element, find all the indices that the...
  4. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  5. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  6. Simple Multithreading in Python Creating threads is very easy in Python. The following is the example that I use...
  7. Password Protect or IP Restriction on WordPress wp-admin Folder (htaccess and htpasswd) wp-admin folder is the most important folder in a wordpress installation. It mainly contains the...
  8. Teaching Kids Programming – Maximum Number of Space Partitions by N Straight Lines (Pizza Cutting Problem, Math, DP, Recursion) Teaching Kids Programming: Videos on Data Structures and Algorithms Given a Pizza or Cake or...

Leave a Reply