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