fork download
copy 
  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 = 8;
  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, 5}) << endl;
  61. 	cout << sieve(s, {2, 6}) << endl;
  62. 	cout << sieve(s, {3, 7}) << endl;
  63. 	cout << sieve(s, {4, 8}) << endl;
  64. 	cout << sieve(s, {1, 2}) << endl;
  65. 	cout << sieve(s, {3, 4}) << endl;
  66. 	cout << sieve(s, {5, 6}) << endl;
  67. 	cout << sieve(s, {7, 8}) << endl;
  68. 	cout << sieve(s, {1, 3}) << endl;
  69. 	cout << sieve(s, {6, 8}) << endl;
  70.     cout << sieve(s, {2, 7}) << endl;
  71.     cout << sieve(s, {4, 5}) << endl;
  72.     cout << sieve(s, {2, 3}) << endl;
  73.     cout << sieve(s, {2, 4}) << endl;
  74.     cout << sieve(s, {5, 7}) << endl;
  75.     cout << sieve(s, {6, 7}) << endl;
  76.     cout << sieve(s, {3, 4}) << endl;
  77.     cout << sieve(s, {5, 6}) << endl;
  78.     cout << sieve(s, {4, 5}) << endl;
  79.  
  80.  
  81.  
  82.  
  83. 	show(s);
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.02s 10064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
40320
20160
10080
5040
2520
1680
1120
560
280
200
144
96
48
28
18
11
7
4
2
1
1 total:
12345678
https://ideone.com/uwrB01
BG590 checker, 1-indexation
language:
C++14 (gcc 8.3)
created:
16 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!