fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <unordered_set>
  6. using namespace std;
  7.  
  8.  
  9.  
  10. void permutate_bt(vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
  11. {
  12. 	if(l==(v.size()-1)) {res.push_back(v); return;}
  13. 	for(unsigned int i=l; i<v.size(); ++i)
  14. 	{
  15. 		iter_swap(v.begin()+i, v.begin()+l); 
  16. 		permutate_bt(v, res, l+1); 
  17. 		iter_swap(v.begin()+i, v.begin()+l); 
  18. 	}
  19. }
  20.  
  21.  
  22.  
  23. void permutate_pf(const vector<int>& v, vector<vector<int>>& res, const unsigned int l=0)
  24. {
  25. 	if(l==(v.size())-1) { res.push_back(v); return; }
  26. 	for(unsigned int i=l; i<v.size(); ++i)
  27. 	{
  28. 		auto t = v; 
  29. 		t.insert(t.begin(),v[i]); 
  30. 		t.erase(t.begin()+i+1); 
  31. 		permutate_pf(t, res, l+1); 
  32. 	}
  33. }
  34.  
  35.  
  36.  
  37. string to_str(const vector<int>& v)
  38. {
  39. 	string res; 
  40. 	for(const auto& e : v) res += to_string(e) + " "; 
  41. 	return res; 
  42. }
  43.  
  44. string to_str(const vector<vector<int>>& v)
  45. {
  46. 	string res; 
  47. 	for(const auto& e : v) res += to_str(e) + "\n"; 
  48. 	return res;
  49. }
  50.  
  51.  
  52. const vector<int> t = {1,2,3}; 
  53.  
  54.  
  55. int main() {
  56. 	// your code goes here
  57. 	vector<vector<int>> res_bt;
  58. 	vector<int> v = {1,2,3}; 
  59. 	permutate_bt(v, res_bt);
  60.  
  61. 	unordered_set<string> gt; 
  62. 	for(const auto& e : res_bt) gt.insert(to_str(e)); 
  63.  
  64. 	vector<vector<int>> res_pf; 
  65. 	permutate_pf({1,2,3}, res_pf); 
  66.  
  67. 	unsigned int count=0; 
  68. 	for(const auto& e : res_pf) if(gt.find(to_str(e)) != gt.end()) count++; 
  69.  
  70. 	cout << "BT" << endl; 
  71. 	cout << to_str(res_bt) << endl; 
  72.  
  73. 	cout << "PF" << endl; 
  74. 	cout << to_str(res_pf) << endl; 
  75.  
  76. 	cout << "Found=" << count << endl; 
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BT
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

PF
2 1 3 
3 1 2 
1 2 3 
3 2 1 
1 3 2 
2 3 1 

Found=6
https://ideone.com/njmATt
Compute all the Permutations in 2 ways: Backtracking and Put First appunto
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!