fork download
copy 
  1. #include <iostream> 
  2. #include <cstdio>
  3. #include <string>
  4. #include <sstream>
  5. #include <vector>
  6. #include <list>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <stack>
  11. #include <bitset>
  12. #include <numeric>
  13. #include <iterator>
  14. #include <algorithm>
  15. #include <cmath>
  16. #include <chrono>
  17. #include <cassert>
  18.  
  19. using namespace std;
  20. using ll = long long;
  21. using ii = pair<int,int>;
  22. using vi = vector<int>;
  23. using vb = vector<bool>;
  24. using vvi = vector<vi>;
  25. using vii = vector<ii>;
  26. using vvii = vector<vii>;
  27.  
  28. const int INF = 2000000000;
  29. const ll LLINF = 9000000000000000000;
  30.  
  31. void apply(vi &row, vi &perm) {
  32. 	for (int i : perm) {
  33. 		swap(row[i], row[i+1]);
  34. 	}
  35. }
  36.  
  37. void precomp(vector<vvi> &v, int N = 8) {
  38. 	v.assign(9, vvi());
  39. 	v[2].push_back(vi(1, 0));
  40. 	v[2].push_back(vi(1, 0));
  41. 	v[3].push_back(vi(1, 0));
  42. 	v[3].push_back(vi(1, 1));
  43. 	v[3].push_back(vi(1, 0));
  44. 	v[3].push_back(vi(1, 1));
  45. 	v[3].push_back(vi(1, 0));
  46. 	v[3].push_back(vi(1, 1));
  47.  
  48. 	for (int n = 4; n <= N; ++n) {
  49. 		vi perm(n, 0);
  50. 		for (int i = 0; i < n; ++i) perm[i] = i;
  51.  
  52. 		vb had(n, false);
  53. 		had[n - 1] = true;
  54. 		for (int i = 0; i < v[n - 1].size(); ++i) {
  55. 			// If the next permutation leaves perm[n-1]
  56. 			// unchanged and perm[n-1] has not been at the
  57. 			// back yet, apply (n-1 n) as well, enumerate
  58. 			// all v[n-1] permutations on the current perm
  59. 			// and add (n-1 n) to the final permutation
  60. 			// as well.
  61. 			// Otherwise, just apply
  62. 			bool fixed = true;
  63. 			for (int _j = 0; _j < v[n - 1][i].size(); ++_j) {
  64. 				int j = v[n-1][i][_j];
  65. 				fixed = fixed && (n - 3 != j);
  66. 			}
  67. 			if (fixed && !had[perm[n - 2]]) {
  68. 				had[perm[n-2]] = true;
  69. 				// Merge (n-1 n), apply v[n-1] fully
  70. 				v[n].push_back(v[n-1][i]);
  71. 				apply(perm, v[n].back());
  72. 				v[n].back().push_back(n - 2);
  73. 				for (int j = i + 1; j < v[n-1].size(); ++j)
  74. 					v[n].push_back(v[n - 1][j]);
  75. 				for (int j = 0; j <= i; ++j)
  76. 					v[n].push_back(v[n - 1][j]);
  77. 				v[n].back().push_back(n - 2);
  78. 			} else {
  79. 				// Just apply v[n - 1][i]
  80. 				v[n].push_back(v[n-1][i]);
  81. 				apply(perm, v[n].back());
  82. 			}
  83. 		}
  84. 	}
  85. }
  86.  
  87. void printperm(vi &perm) {
  88. 	printf("%d", 1 + perm[0]);
  89. 	for (int i = 1; i < perm.size(); ++i)
  90. 		printf(" %d", 1 + perm[i]);
  91. 	printf("\n");
  92. }
  93.  
  94. int main() {
  95. 	vector<vvi> v;
  96. 	int n;
  97. 	scanf("%d", &n);
  98. 	precomp(v, n);
  99.  
  100. 	if (n == 1) { printf("1\n"); return 0; }
  101.  
  102. 	vi perm(n, 0);
  103. 	for (int i = 0; i < n; ++i) perm[i] = i;
  104. 	for (int i = 0; i < v[n].size(); ++i) {
  105. //		for (int j : v[n][i]) cerr <<"(" << j << " " << j+1 <<")";
  106. //		cerr<<endl;
  107. 		printperm(perm);
  108. 		apply(perm, v[n][i]);
  109. 	}
  110. //	printf("Size: %d\n", int(v[n].size()));
  111.  
  112. 	return 0;
  113. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
4
stdout
copy 
1 2 3 4
2 1 4 3
2 4 1 3
4 2 1 3
4 1 2 3
1 4 2 3
1 2 4 3
2 1 3 4
2 3 1 4
3 2 4 1
3 4 2 1
4 3 2 1
4 2 3 1
2 4 3 1
2 3 4 1
3 2 1 4
3 1 2 4
1 3 4 2
1 4 3 2
4 1 3 2
4 3 1 2
3 4 1 2
3 1 4 2
1 3 2 4
https://ideone.com/4ZjBV0
language:
C++14 (gcc 8.3)
created:
9 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!