Coding Challenge - Compute all the permutations in a given vector

[NicolaBernini]

CPP

Using Backtracking

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

void permutate_bt(vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
{
    if(l==(v.size()-1)) {res.push_back(v); return;}
    for(unsigned int i=l; i<v.size(); ++i)
    {
        iter_swap(v.begin()+i, v.begin()+l); 
        permutate_bt(v, res, l+1); 
        iter_swap(v.begin()+i, v.begin()+l); 
    }
}

int main()
{
        // The algo requires some in place modifications, hence the input needs to be passed as mutable 
        vector<vector<int>> res_bt;
    vector<int> v = {1,2,3}; 
    permutate_bt(v, res_bt);
}

Using Putfirst Method

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

void permutate_pf(const vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
{
    if(l==(v.size())-1) { res.push_back(v); return; }
    for(unsigned int i=l; i<v.size(); ++i)
    {
        auto t = v; 
        t.insert(t.begin(),v[i]); 
        t.erase(t.begin()+i+1); 
        permutate_pf(t, res, l+1); 
    }
}

int main() {
        // Here no in place modification hence the input vector can be passed as immutable 
        const vector<int> t = {1,2,3}; 
    vector<vector<int>> res_pf; 
    permutate_pf({1,2,3}, res_pf); 

}

Check

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

void permutate_bt(vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
{
    if(l==(v.size()-1)) {res.push_back(v); return;}
    for(unsigned int i=l; i<v.size(); ++i)
    {
        iter_swap(v.begin()+i, v.begin()+l); 
        permutate_bt(v, res, l+1); 
        iter_swap(v.begin()+i, v.begin()+l); 
    }
}

void permutate_pf(const vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
{
    if(l==(v.size())-1) { res.push_back(v); return; }
    for(unsigned int i=l; i<v.size(); ++i)
    {
        auto t = v; 
        t.insert(t.begin(),v[i]); 
        t.erase(t.begin()+i+1); 
        permutate_pf(t, res, l+1); 
    }
}

string to_str(const vector<int>& v)
{
    string res; 
    for(const auto& e : v) res += to_string(e) + " "; 
    return res; 
}

string to_str(const vector<vector<int>>& v)
{
    string res; 
    for(const auto& e : v) res += to_str(e) + "\n"; 
    return res;
}

const vector<int> t = {1,2,3}; 

int main() {
    // your code goes here
    vector<vector<int>> res_bt;
    vector<int> v = {1,2,3}; 
    permutate_bt(v, res_bt);

    unordered_set<string> gt; 
    for(const auto& e : res_bt) gt.insert(to_str(e)); 

    vector<vector<int>> res_pf; 
    permutate_pf({1,2,3}, res_pf); 

    unsigned int count=0; 
    for(const auto& e : res_pf) if(gt.find(to_str(e)) != gt.end()) count++; 

    cout << "BT" << endl; 
    cout << to_str(res_bt) << endl; 

    cout << "PF" << endl; 
    cout << to_str(res_pf) << endl; 

    cout << "Found=" << count << endl; 
    return 0;
}

Run it on Ideone

[NicolaBernini]

Python

Using Put First

def permutate_pf(v, res, l=0): 
    if l==len(v)-1: 
        res.append(v)
        return 

    for i in range(l, len(v)): 
        t = []
        t.append(v[i])
        for j in range(len(v)): 
            if(j!=i): 
                t.append(v[j])
        permutate_pf(t, res, l+1)

res = []

permutate_pf([1,2,3], res)

print(res)

Run it on Ideone