#include void swap(int &x, int &y) { int h = x; x = y; y = h; } class Permutations { public: Permutations(int val_n) : n(val_n), _more(true) { a = new int[n]; for (int i = 0; i < n; i++) a[i] = i; } ~Permutations() { delete []a; } bool more() { return _more; } void next() { _more = false; for (int i = n-2; i >= 0; i--) if (a[i] < a[i+1]) { _more = true; for (int j = n-1; j > i; j--) if (a[j] > a[i]) { swap(a[j], a[i]); break; } i++; for (int j = n-1; j > i; j--, i++) swap(a[j], a[i]); break; } } int n; int *a; private: bool _more; }; void testSort(int n, bool (*before)(int x, int y), bool (*check)(int n, int *a, int *org_a)) { for (Permutations perms(n); perms.more(); perms.next()) { int a[n]; for (int i = 0; i < perms.n; i++) a[i] = perms.a[i]; { for (int c = 1; c < n; c++) for (int i = 0; i < c; i++) if (before(a[c], a[i])) { int e = c+1; for (int b = c; i < b; b--) { bool pass = true; for (int j = b; j < e; j++) if (before(a[b-1], a[j])) { pass = false; break; } if (pass) { for (int j = b; j < e; j++) swap(a[j-1], a[j]); e--; } } break; } } for (int i = 0; i < n; i++) printf("%3d", perms.a[i]); printf(" -> "); for (int i = 0; i < n; i++) printf("%3d", a[i]); if (check != 0) printf(" %s", check(n, a, perms.a) ? "ok" : "FAIL"); printf("\n"); } } bool test1(int x, int y) { return x == y-1; } bool check1(int n, int *a, int *a_org) { for (int i = 0; i < n-1; i++) if (a[i] > a[i+1]) return false; return true; } bool test2(int x, int y) { return x == y-2; } bool check2(int n, int *a, int *a_org) { int even = 0; int odd = 1; for (int i = 0; i < n; i++) if (a[i] % 2 == 0) { if (a[i] != even) return false; even += 2; } else { if (a[i] != odd) return false; odd += 2; } return true; } bool test3(int x, int y) { return x%2 == 0 && x == y-2; } bool check3(int n, int *a, int *a_org) { int even = 0; int i_odd = 0; while (i_odd < n && a_org[i_odd]%2 == 0) i_odd++; for (int i = 0; i < n; i++) if (a[i] % 2 == 0) { if (a[i] != even) return false; even += 2; } else { if (a[i] != a_org[i_odd]) return false; i_odd++; while (i_odd < n && a_org[i_odd]%2 == 0) i_odd++; } return true; } bool test4(int x, int y) { return x < y && (x == 4 || y == 4); } bool check4(int n, int *a, int *a_org) { int i_lt4 = 0; for (int i = 0; i < 4; i++) { while (i_lt4 < n && a_org[i_lt4] >= 4) i_lt4++; if (a[i] != a_org[i_lt4]) return false; i_lt4++; } if (a[4] != 4) return false; int i_gt4 = 0; for (int i = 5; i < n; i++) { while (i_gt4 < n && a_org[i_gt4] <= 4) i_gt4++; if (a[i] != a_org[i_gt4]) return false; i_gt4++; } return true; } int index(int n, int *a, int v) { for (int i = 0; i < n; i++) if (a[i] == v) return i; return -1; } #define BEFORE(X,Y) ((X) == x && (Y) == y) #define CHECK_PAIR(X,Y) if (index(n,a,X) >= index(n,a,Y)) return false; bool test5(int x, int y) { return BEFORE(0, 1) || BEFORE(1, 2) || BEFORE(2, 3) || BEFORE(3, 4) || BEFORE(1, 5) || BEFORE(5, 3) || BEFORE(5, 6) || BEFORE(6, 7) || BEFORE(7, 8) || BEFORE(4, 8); } bool check5(int n, int *a, int *a_org) { CHECK_PAIR(0, 1) CHECK_PAIR(1, 2) CHECK_PAIR(2, 3) CHECK_PAIR(3, 4) CHECK_PAIR(1, 5) CHECK_PAIR(5, 3) CHECK_PAIR(5, 6) CHECK_PAIR(6, 7) CHECK_PAIR(7, 8) CHECK_PAIR(4, 8) return true; } bool test6(int x, int y) { return BEFORE(0, 1) || BEFORE(0, 2) || BEFORE(1, 3) || BEFORE(1, 4) || BEFORE(2, 5) || BEFORE(2, 6) || BEFORE(3, 7) || BEFORE(3, 8); } bool check6(int n, int *a, int *a_org) { CHECK_PAIR(0, 1) CHECK_PAIR(0, 2) CHECK_PAIR(1, 3) CHECK_PAIR(1, 4) CHECK_PAIR(2, 5) CHECK_PAIR(2, 6) CHECK_PAIR(3, 7) CHECK_PAIR(3, 8) return true; } int main(int argc, char *argv[]) { testSort(9, test1, check1); testSort(9, test2, check2); testSort(9, test3, check3); testSort(9, test4, check4); testSort(9, test5, check5); testSort(9, test6, check6); return 0; }