C上的置换生成器

我需要一个简单的置换生成器算法，它可以应用于简单的C语言。

Answer 1

置换数字：

为了使用每个排列，您必须连接到打印function。

#include  #include  /** 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

所有

我找到了算法，以计算机编程艺术（TAOCP）的字典顺序生成排列：

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

以字典顺序生成有许多方法可以系统地生成给定序列的所有排列[需要引证]。 一种既简单又灵活的经典算法基于在词典排序中找到下一个排列（如果存在的话）。 它可以处理重复的值，在这种情况下，它每次生成不同的多集排列。 即使对于普通的排列，它也比在词典顺序中生成Lehmer代码的值（可能使用阶乘数系统）并将它们转换为排列更有效。 要使用它，首先要按顺序（弱）递增顺序对序列进行排序（这会给出其按字典顺序排列的最小排列），然后只要找到一个，就重复前进到下一个排列。 这种方法可以追溯到14世纪印度的Narayana Pandita，并且从那以后经常被重新发现。

以下算法在给定排列之后按字典顺序生成下一个排列。 它就地改变了给定的排列。

1. 找到最大的索引k，使得a [k]
2. 找到最大的索引l，使得a [k]
3. 用[l]交换[k]。
4. 将序列从[k + 1]反转到包括最终元素a [n]。

在步骤1之后，人们知道严格地在位置k之后的所有元素形成弱递减序列，因此这些元素的排列不会使其按字典顺序前进; 提前一个必须增加一个[k]。 步骤2找到最小值a [l]以替换[k]，并且在步骤3中交换它们使位置k之后的序列以弱降序排列。 在步骤4中反转该序列然后产生其按字典顺序排列的最小排列，以及整个序列的初始状态的词典inheritance器

Answer 3

这是Knuth的TAOCP中发现的经典算法（在其他地方）。

这是我用于项目euler问题的一个例子。 它以字典顺序创建字符串的所有排列，并将它们打印到标准输出。

 #include 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

这是一个简单的递归解决方案，用于生成在命令行上传递的一组字符的所有排列：

 #include  #include  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; }