按字典顺序打印所有排列
我想以字典顺序打印字符串的所有排列。 我写这段代码：
void permute(char *a, int i, int n) { if (i == (n-1)) printf("\"%s\"\n", a); else { for (int j = i; j < n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); } } } 我有例如字符串abc ，所以我希望以左列中的字典顺序接收所有排列，但是我的结果与右列相同。
"abc" "abc" "acb" "acb" "bac" "bac" "bca" "bca" "cab" "cab"
有人可以帮我弄这个吗？ 我看到了一些算法，但看起来很难。 我想我可以在数组中保存所有生成的字符串，然后对这个数组进行排序，但是我不能写这个（我是C语言的初学者）。
在C.
在geeksforgeeks上有一个非常直接的算法描述（加上实现）：
给定一个字符串，按排序顺序打印它的所有排列。 例如，如果输入字符串是“ABC”，则输出应为“ABC，ACB，BAC，BCA，CAB，CBA”。
我们已经讨论了在这篇文章中打印所有排列的程序，但是在这里我们必须按递增顺序打印排列。
以下是按字典顺序打印排列的步骤
以非递减顺序对给定字符串进行排序并打印它。 第一个排列始终是以非递减顺序排序的字符串。
开始生成下一个更高的排列。 这样做直到下一个更高的排列是不可能的。 如果我们达到所有字符按非递增顺序排序的排列，则该排列是最后的排列。
生成下一个更高排列的步骤：
1.取出先前打印的排列，找到最右边的字符，小于下一个字符。 让我们将这个角色称为“第一个角色”。
现在找到“第一个角色”的天花板。 天花板是“第一个字符”右边的最小字符，大于“第一个字符”。 让我们将ceil字符称为“第二个字符”。
交换上面两步中找到的两个字符。
在“第一个字符”的原始索引之后对子字符串（以非递减顺序）排序。
我在下面重新实现了它：
#include #include #include void swap(char* left, char* right) { char temp = *left; *left = *right; *right = temp; } int compare (const void * a, const void * b) { return ( *(char*)a - *(char*)b ); } void PrintSortedPermutations(char* inStr) { // Re-implementation of algorithm described here: // http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ int strSize = strlen(inStr); // 0. Ensure input container is sorted qsort(inStr, strSize, sizeof(char), compare); int largerPermFound = 1; do{ // 1. Print next permutation printf("%s\n", inStr); // 2. Find rightmost char that is smaller than char to its right int i; for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){} // if we couldn't find one, we're finished, else we can swap somewhere if (i > -1) { // 3 find character at index j such that // inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i int j = i+1; int k; for(k=j;k inStr[i] && inStr[k] < inStr[j]) j = k; } // 3. Swap chars at i and j swap(&inStr[i], &inStr[j]); // 4. Sort string to the right of i qsort(inStr+i+1, strSize-i-1, sizeof(char), compare); } else { largerPermFound = 0; } }while(largerPermFound); } int main(void) { char str[] = "abc"; PrintSortedPermutations(str); return 0; }
产量
ABC
ACB
BAC
BCA
出租车
CBA
现场演示
在C ++中
来自std::next_permutation将为您完成此操作，只需确保首先对容器进行排序：
返回值
如果函数可以将对象重新排列为lexicographicaly更大的排列，则为true。 否则，该函数返回false以指示排列不大于前一个，但最低可能（按升序排序）。
例如：
std::string myStr = "abc"; std::stable_sort(std::begin(myStr), std::end(myStr)); do { for(auto&& element : myStr) std::cout << element << " "; std::cout << std::endl; } while (std::next_permutation(std::begin(myStr), std::end(myStr)));
输出：
ABC
ACB
BAC
BCA
出租车
CBA
现场演示
我假设你想要一个递归版本，因为你是初学者。
这是两个解决方案。
解决方案1）
由于您需要词典，所以您需要做的就是在需要选择时选择下一个最小的。 而已！
例如，这是python中的递归版本
def permute(done, remaining): if not remaining: print done return sorted_rem = sorted(remaining) l = len(sorted_rem) for i in xrange(0, l): c = sorted_rem[i] # Move to c to done portion. done.append(c) remaining.remove(c) # Permute the remaining permute(done, remaining) # Put c back. remaining.append(c) # Remove from done. del done[-1] permute([], [1,2,3,4])
而已。
解决方案2）
虽然解决方案1的工作原理很容易理解，但我怀疑我们可能会因为排序而浪费一些时间。 这个解决方案更接近你所拥有的。
递归基本上是伪装的数学归纳，这种思维方式对于理解如何编写递归程序非常有用。
例如，假设您的permute方法始终按字典顺序构造排列。
这是一个递归版本，有了这个假设，请阅读评论以了解发生了什么。
// By induction assumption, permute(a, i, n) // goes through all the permutations of a[i], ..., a[n-1] // in lexicographic order, by modifying a itself. void permute(char *a, int i, int n) { if (i == (n-1)) { printf("%s\n", a); return; } int j; // We pick the ni posibilities for the position a+i, then recursively // compute the permutations of a[i+1], ..., a[n-1] // So first pick the smallest possible for a+i, recurse. // Then the next possible for a+i, then recurse etc. for (j = i; j < n; j++) { permute(a, i+1, n); // By our induction assumption, at this point, // a[i+1], a[i+2], .., a[n-1] // must be the lexicographically the largest possible! // So now reverse that portion. reverse(a+i+1, a+n-1); // Now we need to pick the lexicographically next element for // position a+i. This is nothing but the element which is just // larger than the current a+i. int k = i+1; while(k < n && a[i] > a[k]) { k++; } if (k >= n) { continue; } // Choose the next value for a+i. swap(a+i, a+k); } // Notice that the portion a[i+1], ..., a[n-1] is sorted increasing. // when the loop exits. Also a[i] will be the largest element. // We need to reverse so that a[i], .., a[n-1] is the lexicographically // largest permutation to maintain the induction (recursion) assumption. reverse(a+i+1, a+n-1); }
注意这个和迭代版本之间的相似性（由其他人和下面的部分指定），你在那里反转一个块，并交换两个元素。
顺便说一句，用于按字典顺序生成排列的常用迭代算法是Narayana Pandita的算法，由其他人提及，但不是名称。
请看这个链接： http ： //en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
这就是std :: next of C ++和许多其他库使用的东西。
这个算法甚至可以在有重复元素的情况下工作，实际上可以用来生成组合！ （用零和1初始化数组）。
基本的想法是从我们的主字符串开始为“”，剩下的字符串为“abc”（或任何你想要的）。
现在到主字符串逐个字符追加。 这样一种方式，它不会重复使用的字符（对于所有可能的字符）。
重复相同，直到得到长度n（主弦的长度）。
好的，解释不明确但要注意代码。 它会让一切都清晰。
#include void perm(std::string sub, std::string rem, int n) { if(n==0) //print if n is zero ie length achieved std::cout<
产量
abc acb bac bca cab cba
恕我直言，首先对字符串的字符进行排序会更简单，因为排列的数量（ n! ）总是比字符数更大（或等于n = 1或2）。
而且你离解决方案不远，但你必须轮换而不是交换。 这是一个轻微的变体，它返回一个动态分配的字符串数组，这些字符串在main中打印：
#include #include #include int char_compare(const void *a, const void *b) { return (*((char *) a)) - (*((char *) b)); } int fact(int n) { int f = 1; while (n > 0) { f *= n--; if (f < 0) return 0; } return f; } void rotateback(char *a, int i, int j) { int k; char tmp; tmp = a[i]; for(k=i; ki; k--) { a[k] = a[k-1]; } a[i] = tmp; } void permute(char *a, int i, int n, char ***permuts) { int j; if (i == (n-1)) { **permuts = strdup(a); // store a copy of the string *permuts += 1; // and point to next location } else { for (j = i; j < n; j++) { rotate(a, i, j); permute(a, i+1, n, permuts); rotateback(a, i, j); } } } char ** permutations(const char *str_orig) { int i, j; size_t n = strlen(str_orig); size_t fact_n = fact(n); char ** permuts, **work; char * str = strdup(str_orig); // get a local copy qsort(str, n, 1, char_compare); // and sort it permuts = work = calloc(fact_n, sizeof(char *)); // allocate n! pointers permute(str, 0, n, &work); return permuts; } int main() { char str[] = "cab"; int i; char **permuts = permutations(str); for (i=0; i
输出正确：
"abc" "acb" "bac" "bca" "cab" "cba"
词法字符串排列的另一个变化是将置换存储在动态分配的指针到字符串的数组中，并将数组传递给qsort以按词汇顺序提供输出。 由于排列呈指数增长，因此在每次分配后检查内存耗尽尤为重要。 下面的字符串大小限制为16个字符，这可能仍会导致内存耗尽，具体取决于可用内存量。
更新传递数组的地址以保存字符串排列是重新分配在递归函数中工作所必需的。
#include #include #include #define MAXS 128 #define MAXC 16 size_t maxs; void swap (char *x, char *y); int cmp_pa (const void * a, const void * b); char **realloc_char (char **sp, size_t *n); void permute_pa (char ***pa, size_t *idx, char *a, int i, int n); int main (int argc, char **argv) { size_t i = 0; size_t idx = 0; size_t len = 0; char a[MAXC] = {0}; char **pa = NULL; maxs = MAXS; /* initialize realloc counter */ if (argc > 1) /* set string to permute */ strcpy (a, argv[1]); else strcpy (a, "abc"); len = strlen (a); /* lenght to permute or MAXC */ if (len > MAXC) len = MAXC; if (!(pa = calloc (MAXS, sizeof *pa))) /* allocate MAXS pointers */ return 1; permute_pa (&pa, &idx, a, 0, len - 1); /* call permute function */ printf ("\n no of permutations : %zu\n\n", idx); printf (" unsorted permutations of %s\n\n", a); for (i = 0; i < idx; i++) printf (" %s\n", pa[i]); qsort (pa, idx, sizeof *pa, cmp_pa); /* sort array of permutations */ printf ("\n sorted permutations of %s\n\n", a); for (i = 0; i < idx; i++) printf (" %s\n", pa[i]); for (i = 0; i < idx; i++) /* free all allocated memory */ free (pa[i]); free (pa); return 0; } /* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* qsort compare function */ int cmp_pa (const void * a, const void * b) { return strcmp (*(char**)a, *(char**)b); } /* realloc an array of pointers to strings setting memory to 0. */ char **realloc_char (char **sp, size_t *n) { char **tmp = realloc (sp, 2 * *n * sizeof *sp); if (!tmp) { fprintf (stderr, "Error: struct reallocation failure.\n"); // return NULL; exit (EXIT_FAILURE); } sp = tmp; memset (sp + *n, 0, *n * sizeof *sp); /* memset new ptrs 0 */ *n *= 2; return sp; } /* Function to store permutations of string in array of pointers-to-string This function takes five parameters: 1. allocated array of pointers-to-string 2. pointer to array index 3. string to permute 4. starting index of the string (zero based) 5. ending index of the string. (zero based) */ void permute_pa (char ***pa, size_t *idx, char *a, int i, int n) { int j; if (i == n) { (*pa)[*idx] = strdup (a); if (!(*pa)[*idx]) { fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__); exit (EXIT_FAILURE); } (*idx)++; if (*idx == maxs) *pa = realloc_char (*pa, &maxs); } else { for (j = i; j <= n; j++) { swap ((a+i), (a+j)); permute_pa (pa, idx, a, i+1, n); swap ((a+i), (a+j)); } } }
产量
$ ./bin/str_permute_lex no of permutations : 6 unsorted permutations of abc abc acb bac bca cba cab sorted permutations of abc abc acb bac bca cab cba
内存错误检查
$ valgrind ./bin/str_permute_lex ==29709== Memcheck, a memory error detector ==29709== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al. ==29709== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info ==29709== Command: ./bin/str_permute_lex ==29709== no of permutations : 6 ==29709== ==29709== HEAP SUMMARY: ==29709== in use at exit: 0 bytes in 0 blocks ==29709== total heap usage: 7 allocs, 7 frees, 1,048 bytes allocated ==29709== ==29709== All heap blocks were freed -- no leaks are possible ==29709== ==29709== For counts of detected and suppressed errors, rerun with: -v ==29709== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
这是一个自愿回答这个问题的答案。
这个问题被标记为与此问题重复。 这个答案对于另一个问题是可以接受的，即使这里没有意义。
这可以是一个简单的递归C实现，以按字典顺序获取所有排列。 它没有优化，但易于理解和实施：
- 获取要置换的元素的数组
- 在任何步骤中，迭代直到此处尚未使用的元素
- 将一个迭代元素添加到已使用元素的数组中
- 递归
- 当使用过的元素数组完全打印出来时。
具体实施：
#include #define SIZE 4 void disp(int *fullarr, int n, int * begin, int pos) { int i, j; int found; if (pos == n) { for(i=0; i< n; i++) { printf("%2d", begin[i]); } printf("\n"); return; } for (i=0; i