fork download 
  1. #include <iostream>
  2. #include <set>
  3. #include <array>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. const size_t N = 10;
  9. typedef array<size_t, N> perm;
  10. typedef set<perm> perms;
  11.  
  12. perms s;
  13.  
  14. void init (perms& s) {
  15. 	s.clear();
  16. 	perm ta;
  17. 	for (size_t i = 0; i < N; ++i) ta[i] = i+1;
  18. 	s.insert(ta);
  19. 	while(next_permutation(ta.begin(), ta.end()))
  20. 		s.insert(ta);
  21. }
  22.  
  23. size_t sieve (perms& s, pair<size_t, size_t> p) {
  24. 	vector<perm> for_insert;
  25. 	vector<perms::iterator> for_erase;
  26.  
  27. 	for (auto sit = s.begin(); sit != s.end(); ++sit) {
  28. 		auto first = p.first - 1;
  29. 		auto second = p.second - 1;
  30. 		if ((*sit)[first] > (*sit)[second]) {
  31. 			for_erase.push_back(sit);
  32. 			for_insert.push_back(*sit);
  33. 			swap(for_insert.back()[first], for_insert.back()[second]);
  34. 		}
  35. 	}
  36.  
  37. 	for (auto& eit: for_erase)
  38. 		s.erase(eit);
  39.  
  40. 	for (auto& a: for_insert) {
  41. 		bool t = s.insert(a).second;
  42. 		//if (t) cout << "INSERT!" << endl;		
  43. 	}
  44.  
  45. 	return s.size();
  46. }
  47.  
  48. void show (const perms& s) {
  49. 	cout << s.size() <<  " total:" << endl;
  50. 	for (auto& a: s) {
  51. 		for (auto& e: a) cout << e;
  52. 		cout << endl;
  53. 	}
  54. }
  55.  
  56. int main() {
  57. 	init(s);
  58. 	cout << s.size() << endl;
  59.  
  60. 	cout << sieve(s, {1, 6}) << endl;
  61. 	cout << sieve(s, {2, 7}) << endl;
  62. 	cout << sieve(s, {3, 8}) << endl;
  63. 	cout << sieve(s, {4, 9}) << endl;
  64. 	cout << sieve(s, {5, 10}) << endl;
  65.  
  66. 	cout << sieve(s, {2, 4}) << endl;
  67. 	cout << sieve(s, {3, 5}) << endl;
  68. 	cout << sieve(s, {6, 8}) << endl;
  69. 	cout << sieve(s, {7, 9}) << endl;
  70.  
  71. 	cout << sieve(s, {2, 3}) << endl;
  72. 	cout << sieve(s, {1, 2}) << endl;
  73. 	cout << sieve(s, {8, 9}) << endl;
  74. 	cout << sieve(s, {9, 10}) << endl;
  75.  
  76. 	cout << sieve(s, {2, 9}) << endl;
  77. 	cout << sieve(s, {4, 6}) << endl;
  78. 	cout << sieve(s, {5, 7}) << endl;
  79. 	cout << sieve(s, {2, 4}) << endl;
  80. 	cout << sieve(s, {3, 5}) << endl;
  81. 	cout << sieve(s, {6, 8}) << endl;
  82. 	cout << sieve(s, {7, 9}) << endl;
  83. 	cout << sieve(s, {2, 3}) << endl;
  84. 	cout << sieve(s, {8, 9}) << endl;
  85.  
  86. 	cout << sieve(s, {4, 6}) << endl;
  87. 	cout << sieve(s, {5, 7}) << endl;
  88. 	cout << sieve(s, {4, 5}) << endl;
  89. 	cout << sieve(s, {6, 7}) << endl;
  90. 	cout << sieve(s, {3, 4}) << endl;
  91. 	cout << sieve(s, {7, 8}) << endl;	
  92.  
  93. 	cout << sieve(s, {5, 6}) << endl;
  94. 	cout << sieve(s, {4, 5}) << endl;
  95. 	cout << sieve(s, {6, 7}) << endl;
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106. 	show(s);
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 4.03s 645936KB
comments (?)
stdin 
Standard input is empty
stdout 
3628800
1814400
907200
453600
226800
113400
75600
50400
33600
16800
12036
9900
7106
5864
4056
2652
1532
990
560
280
188
129
88
67
46
33
17
11
7
4
2
1
1 total:
12345678910
https://ideone.com/MqLjdt
BG590 checker, 1-indexation
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

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!