Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <stdlib.h>
- using namespace std;
- typedef void(*cyclefn)(const unsigned int *, size_t);
- void permutation_cycles_recursive(const unsigned int *permutation, unsigned int *visited,
- unsigned int start, unsigned int current, unsigned int *path,
- size_t length, cyclefn fun)
- {
- visited[current] = 1;
- path[length] = current;
- if (start == current && length > 0) {
- fun(path, length);
- }
- else {
- permutation_cycles_recursive(permutation, visited, start, permutation[current],
- path, length + 1, fun);
- }
- }
- void permutation_cycles(const unsigned int *permutation, size_t n, cyclefn fun)
- {
- unsigned int i;
- unsigned int *visited = new unsigned int[n];
- unsigned int *path = new unsigned int[n];
- if (!(visited && path)) {
- free(visited);
- free(path);
- return;
- }
- for (i = 0; i < n; i++) {
- if (!visited[i]) {
- permutation_cycles_recursive(permutation, visited, i, i, path, 0, fun);
- }
- }
- free(visited);
- free(path);
- }
- void print(const unsigned int *cycle, size_t length)
- {
- if (length > 1) {
- unsigned int i;
- putchar('(');
- for (i = 0; i < length; i++) {
- printf("%u", cycle[i]);
- if (i < length - 1) {
- printf(", ");
- }
- }
- putchar(')');
- }
- }
- int main(void)
- {
- unsigned int permutation[] ={0, 3, 4, 2, 1}; ///alt exemplu {1, 3, 7, 0, 4, 8, 2, 6, 5};
- const size_t n = sizeof(permutation) / sizeof(permutation[0]);
- permutation_cycles(permutation, n, print);
- putchar('\n');
- return 0;
- }
Add Comment
Please, Sign In to add comment