Permutation Problems

When to use Permutation

to check all possible placements
when asked how many possibilities, arrangements, posssible sequences which involve all the characters

Formulae

The number of permutations of n distinct objects is n factorial, usually written as n!.

caution

So the time complexity of any problem related to permulations is n!

Permutation TERMS used in Problem Statements

Permutation of length `N`

A permutation of length n is an array of size n consisting of n distinct integers in the range [1, n]. For example, (3, 2, 4, 1) is a permutation of length 4,
- but `(3, 3, 1, 4)` and `(2, 3, 4, 5)` are **not**, as `(3, 3, 1, 4)` contains **duplicate elements**, and `(2, 3, 4, 5)` contains elements **not in** `range [1,4]`.

`good` Permutation -- `codechef`

permutation P good, if the maximum element of the first half of P is less than(<) the minimum element of the second half of P.

`next_permutation` C++ `<algorithm>`

caution

sequence MUST be sorted to use next_permutation

<algorithm> header has next_permutation(str.begin(), str.end) which can be used in two ways

converts sequence to next `lexicographically larger PERMUTATION`

// str = "abcaa"
while (next_permutation(str.begin(), str.end()))
// now the str is Converted into "acaab"

check if the current string or sequence is lexicographically maximum i.e. no more other permutations can be formed.

while (next_permutation(str.begin(), str.end()))
// returns true or false

Create all permutaions of string

same as leetcode Permutation-1

by `swapping`

for loop (swapping ⏩ callingFunction ⏩ swappingBack)

my intution

here first I have to take each element by a for loop, and then I will swap the current index=i from for loop with the index=givenPos I have from the user
- in my for loop i starts with givenPos becoz I want my next elements to swap with each other to make add up to my cuurent combination. Also becoz I want my string to iget bigger in length from my current givenPos
when calling the recursiveFunction here I want my sequence to be of same size So, I will NOT return anything is my base case as I am making changes to the string direrctly aarrangement needs to change for permutation, So, I am swapping elements here.
Now after swapping ⏩ callingFunction I will have to swap those elements back i.e. backtracking becoz I want the original sequenc back as my work with the current sequence is over

by `adding` elements

info

converting nums to map then using map in for loop directly
class Solution {
    void helper(unordered_map<int, int>& bar, vector<int>& temp, vector<vector<int>>& res, int n){
        if(temp.size() == n){
            res.push_back(temp);
            return ;
        }
        for(auto &i : bar){
            if(i.second <= 0) continue;
            i.second --;
            temp.push_back(i.first);
            helper(bar, temp, res, n);
            temp.pop_back();
            i.second ++;
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_map<int, int> bar;
        for(int i : nums){
            bar[i] ++;
        }
        vector<int> temp;
        helper(bar, temp, res, nums.size());
        return res;
    }
};

my thought process

My intution here is :

NO pos is required as the permutation must have size equal to the given sequence.
only if my sequence has reached length of N only then I will add it to result as the permutation will contain all elements of the sequence only in different combinmations/order.
I will use a for loop to take each element form 0 to n and then I will check if that particular element has been taken before or not, if not taken then I will add that element to my permutationSequence and then I will call for the recursiveFunction, So that all other elements can also be added with my current element in all type of arrangements as my recursiveFunction will take each of them and repeat all steps again and again.
- After calling for the recursiveFunction I MUST REMOVE the added element and also mark that element is_NOT_taken becoz So that the element before it in my new permutationSequence can have other combinations. But this element will eventually be taken by recursion in any other for loop as my map has marked it as element_NOT_taken.

using `map` to store elements and then itrerating through the map. If **not using map** then must `sort()` the sequence before doing anything.

Another type of solution using an array storing index of each element: 'but need to sort as map is not used: Striver great Permutation Video

iterating throught map in for loop directly and checking element is taken or not
    vector<vector<int>> ans;
    map<int, int> mp;
    void foo(vector<int>& perm, vector<int>& nums) {    `pos` is NOT used as recursion is called from inside for loop
        if (perm.size() == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (auto &el:mp) {     // must PASS BY REFERENCE "&"  as making `changes directly `to the `el` of map
            if (el.second <= 0)  continue;
            --el.second;
            perm.emplace_back(el.first);
            foo(perm, nums);
            perm.pop_back();
            ++el.second;
        }
    }

main(){
    for(auto el:nums) {
        ++mp[el];
    }
    vector<int> perm;
    foo(perm, nums);    //  no `pos` is required here
}

using `next_permutation()`

int main()
{
    string str;
    cin >> str;
    vector<string> v;

    sort(str.begin(), str.end());

    v.emplace_back(str);
    int sum = 1;
    while (next_permutation(str.begin(), str.end()))
    {
        ++sum;
        v.emplace_back(str);
    }

    // can print now
}

all Permutations WITH duplicates

The given sequence has duplicates

by swapping and checking

by `adding` elements and checking if already taken

info

converting nums to map then using map in for loop directly
class Solution {
    void helper(unordered_map<int, int>& bar, vector<int>& temp, vector<vector<int>>& res, int n){
        if(temp.size() == n){
            res.push_back(temp);
            return ;
        }
        for(auto &i : bar){
            if(i.second <= 0) continue;
            i.second --;
            temp.push_back(i.first);
            helper(bar, temp, res, n);
            temp.pop_back();
            i.second ++;
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_map<int, int> bar;
        for(int i : nums){
            bar[i] ++;
        }
        vector<int> temp;
        helper(bar, temp, res, nums.size());
        return res;
    }
};

my thought process

My intution here is :

NO pos is required as the permutation must have size equal to the given sequence.
only if my sequence has reached length of N only then I will add it to result as the permutation will contain all elements of the sequence only in different combinmations/order.
I will use a for loop to take each element form 0 to n and then I will check if that particular element has been taken before or not, if not taken then I will add that element to my permutationSequence and then I will call for the recursiveFunction, So that all other elements can also be added with my current element in all type of arrangements as my recursiveFunction will take each of them and repeat all steps again and again.
- After calling for the recursiveFunction I MUST REMOVE the added element and also mark that element is_NOT_taken becoz So that the element before it in my new permutationSequence can have other combinations. But this element will eventually be taken by recursion in any other for loop as my map has marked it as element_NOT_taken.

Striver great Permutation Video

iterating throught map in for loop directly and checking element is taken or not
    vector<vector<int>> ans;
    map<int, int> mp;
    void foo(vector<int>& perm, vector<int>& nums) {    `pos` is NOT used as recursion is called from inside for loop
        if (perm.size() == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (auto &el:mp) {     // must PASS BY REFERENCE "&"  as making `changes directly `to the `el` of map
            if (el.second <= 0)  continue;
            --el.second;
            perm.emplace_back(el.first);
            foo(perm, nums);
            perm.pop_back();
            ++el.second;
        }
    }

main(){
    for(auto el:nums) {
        ++mp[el];
    }
    vector<int> perm;
    foo(perm, nums);    //  no `pos` is required here
}

using `next_permutation()`

int main()
{
    string str;
    cin >> str;
    vector<string> v;

    sort(str.begin(), str.end());

    v.emplace_back(str);
    int sum = 1;
    while (next_permutation(str.begin(), str.end()))
    {
        ++sum;
        v.emplace_back(str);
    }

    // can print now
}

next Permutation

Steps:

go throught the sequence in reverse order & find and element at index i wose next element at index i+1 is v[i] > v[i+1 and choose that index as pivot index
go throught the sequence in reverse order & find the first element which is greater than the element at pivot index
- now swap the greater element's index and pivot index
sort the elements of indices next to the swapped pivot element index

in-place/mutable change to the nums vector
void nextPermutation(vector<int> &nums)
{
    int pivot = -1;
    //  1. go throught the sequence in reverse order & find and element at index `i` wose next element at index `i+1` is `v[i] > v[i+1` and choose that index as **pivot index**
    for (int i = nums.size() - 2; i >= 0; i--)
    {
        if (nums.at(i) < nums.at(i + 1))
        {
            pivot = i;
            break;
        }
    }
    if (pivot >= 0)
    {
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            cout << "now" << i << endl;
            if (nums.at(i) > nums.at(pivot))
            {
                swap(nums.at(i), nums.at(pivot));   // 2. `swap` the greater element's index and pivot index
                sort(nums.begin() + pivot + 1, nums.end());     // 3. sort the elements of indices next to the swapped pivot element index
                break;
            }
        }
    }
    else
    {
        sort(nums.begin(), nums.end());
    }
}

Permutation Problems

When to use Permutation​

Formulae​

Permutation TERMS used in Problem Statements​

Permutation of length N​

good Permutation -- codechef​

next_permutation C++ <algorithm>​

converts sequence to next lexicographically larger PERMUTATION​

check if the current string or sequence is lexicographically maximum i.e. no more other permutations can be formed.​

Create all permutaions of string​

by swapping​

my intution​

by adding elements​

my thought process​

using next_permutation()​

all Permutations WITH duplicates​

by swapping and checking​

by adding elements and checking if already taken​

my thought process​

using next_permutation()​

next Permutation​

When to use Permutation

Formulae

Permutation TERMS used in Problem Statements

Permutation of length `N`

`good` Permutation -- `codechef`

`next_permutation` C++ `<algorithm>`

converts sequence to next `lexicographically larger PERMUTATION`

check if the current string or sequence is lexicographically maximum i.e. no more other permutations can be formed.

Create all permutaions of string

by `swapping`

my intution

by `adding` elements

my thought process

using `next_permutation()`

all Permutations WITH duplicates

by swapping and checking

by `adding` elements and checking if already taken

my thought process

using `next_permutation()`

next Permutation