Permutation generator in C

Question

I need a simple permutation generator algorithm that can be used in the simple C language.

Answer 1

Passes by numbers:

To use each permutation, you need to connect to the print function. A.

#include <stdio.h> #include <stdlib.h> /** Read a number, N, from standard input and print the permutations. */ void print(const int *v, const int size) { if (v != 0) { for (int i = 0; i < size; i++) { printf("%4d", v[i] ); } printf("\n"); } } // print void swap(int *v, const int i, const int j) { int t; t = v[i]; v[i] = v[j]; v[j] = t; } void rotateLeft(int *v, const int start, const int n) { int tmp = v[start]; for (int i = start; i < n-1; i++) { v[i] = v[i+1]; } v[n-1] = tmp; } // rotateLeft void permute(int *v, const int start, const int n) { print(v, n); if (start < n) { int i, j; for (i = n-2; i >= start; i--) { for (j = i + 1; j < n; j++) { swap(v, i, j); permute(v, i+1, n); } // for j rotateLeft(v, i, n); } // for i } } // permute void init(int *v, int N) { for (int i = 0; i < N; i++) { v[i] = i+1; } } // init int main() { int *v = (int*) malloc(sizeof(int)*10); init(v, 10); permute(v, 0, 10); free(v); } 

Answer 2

everything

I found algorithms for generating permutations in lexicographical order from the Art of Computer Programming (TAOCP):

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Lexicographic generation There are many ways to systematically generate all permutations of a given sequence [edit]. One classic algorithm, which is simple and flexible, is based on finding the next permutation in lexicographical order, if it exists. It can handle repeated values, in which case it generates separate multi-multiply permutations every time. Even for ordinary permutations, it is much more efficient than generating values ​​for the Lehmer code in lexicographical order (possibly using a system of numerical numbers) and converting them to permutations. To use it, start by sorting the sequence in a (slightly) ascending order (which gives it a lexicographically minimal permutation), and then repeats the transition to the next permutation until it can be found. This method dates back to Narayana Pandita in India of the 14th century, and since then it has often been discovered.

The following algorithm generates the next permutation lexicographically after this permutation. It changes the given permutation in place.

• Find the largest index k such that a [k] a [k + 1]. If such an index does not exist, the permutation is the last permutation.
• Find the largest index l such that a [k] a [l]. Since k + 1 is such an index, l is well defined and satisfies k <l.
• Change a [k] to [l].
• Cancel the sequence from [k + 1] to the final element a and include it in [n].

After step 1, it is known that all elements strictly after position k form a weakly decreasing sequence; therefore, no permutation of these elements will force it to advance in lexicographic order; to advance you need to increase a [k]. Step 2 finds the smallest value a [l] to replace a [k], and replacing them in step 3 leaves the sequence after position k in a slightly decreasing order. Turning to this sequence in step 4, then its lexicographically minimal permutation is obtained, and the lexicographic successor of the initial state for the entire sequence

Answer 3

This is a classic algorithm found (among other places) in Knuth TAOCP.

Here is an example that I used for the project Euler problem. It creates all permutations of the string in lexicographical order and prints them to standard output.

 #include<stdio.h> int main() { char set[10]="0123456789"; char scratch; int lastpermutation = 0; int i, j, k, l; printf("%s\n",set); while (!lastpermutation) { //find largest j such that set[j] < set[j+1]; if no such j then done j = -1; for (i = 0; i < 10; i++) { if (set[i+1] > set[i]) { j = i; } } if (j == -1) { lastpermutation = 1; } if (!lastpermutation) { for (i = j+1; i < 10; i++) { if (set[i] > set[j]) { l = i; } } scratch = set[j]; set[j] = set[l]; set[l] = scratch; //reverse j+1 to end k = (9-j)/2; // number of pairs to swap for (i = 0; i < k; i++) { scratch = set[j+1+i]; set[j+1+i] = set[9-i]; set[9-i] = scratch; } printf("%s\n",set); } } return 0; } 

Answer 4

Here is a simple recursive solution to create all character set permutations passed on the command line:

 #include <stdio.h> #include <string.h> int perm(const char *src, int len, char *dest, char *destbits, int n) { if (n == len) { printf("%.*s\n", len, dest); return 1; } else { int count = 0; for (int i = 0; i < len; i++) { if (destbits[i] == 0) { destbits[i] = 1; dest[n] = src[i]; count += perm(src, len, dest, destbits, n + 1); destbits[i] = 0; } } return count; } } int main(int argc, char *argv[]) { const char *src = (argc > 1) ? argv[1] : "123456789"; int len = strlen(src); char dest[len], destbits[len]; memset(destbits, 0, sizeof destbits); int total = perm(src, len, dest, destbits, 0); printf("%d combinations\n", total); return 0; }