// perm-class.cc - Generate all permutations of an array. // Permutations not generated in lexicographic order. // // Fred Curtis, 2002-09-13 -- http://f2.org/fred/ // // This code is based on some beautiful non-recursive code // by Phillip Paul Fuchs: // http://www.geocities.com/permute_it/01example.html #include class perm_loop { private: int const n; int *p; int curr; public: bool swap_indices(int &i, int &j) { if (curr >= n) { return false; } // Decrement p[curr] and find index to swap with curr // i = curr; j = curr % 2 * --p[curr]; // Reset any run of zeroed p[i] and find next curr for (curr = 1; curr < n && !p[curr]; curr++) { p[curr] = curr; } return true; } void reset() { for(int i = 0; i < n; i++) { p[i] = i; } curr = 1; } perm_loop(int const _n) : n(_n), p(new int[n]) { reset(); } ~perm_loop() { delete p; } }; int main(void) { int const N = 4; perm_loop ploop(N); int a[N]; // Array to be permuted -- can be any type & hold any values for(int i = 0; i < N; i++) { a[i] = i + 1; } for (;;) { // Do something with the permutation // for(int x = 0; x < N; x++) { printf("%d ",a[x]); } printf("\n"); int i; int j; if (!ploop.swap_indices(i, j)) { break; } // Swap array elements i & j // int tmp = a[j]; a[j] = a[i]; a[i] = tmp; } return 0; }