按字典顺序打印所有排列
Print all permutation in lexicographic order
我想按字典顺序打印字符串的所有排列。我写了这段代码：
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" <
"cba" "cba"
> "cab"
有人可以帮我解决这个问题吗？我看到了一些算法，但它们看起来很难。我想我可以将所有生成的字符串保存在一个数组中，然后对这个数组进行排序，但是我不会写这个（我是 C 的初学者）。
在 C
有一个非常简单的算法描述（加上实现）
Given a string, print all permutations of it in sorted order. For
example, if the input string is “ABC”, then output should be “ABC,
ACB, BAC, BCA, CAB, CBA”.
We have discussed a program to print all permutations in this post,
but here we must print the permutations in increasing order.
Following are the steps to print the permutations lexicographic-ally
Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.
Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all
characters are sorted in non-increasing order, then that permutation
is the last permutation.
Steps to generate the next higher permutation:
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call
this character as ‘first character’.
Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater
than ‘first character’. Let us call the ceil character as ‘second
character’.
Swap the two characters found in above 2 steps.
Sort the substring (in non-decreasing order) after the original index of ‘first character’.
我在下面重新实现了它：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
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<strSize && inStr[k];++k)
{
if (inStr[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
cab
cba
在 C++ 中
<algorithm> 库中的 std::next_permutation 会为您执行此操作，只需确保您先对容器进行排序：
Return value
true if the function could rearrange the object as a lexicographicaly
greater permutation. Otherwise, the function returns false to indicate
that the arrangement is not greater than the previous, but the lowest
possible (sorted in ascending order).
例如：
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)));
输出：
a b c
a c b
b a c
b c a
c a b
c b a
恕我直言，首先对字符串的字符进行排序会更简单，因为排列数 (n!) 总是大于（或等于 n = 1 或 2）字符数。
你离解决方案不远，但你必须旋转而不是交换。这里有一个细微的变化，returns 打印在 main 中的动态分配字符串数组：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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; k<j; k++) {
a[k] = a[k+1];
}
a[j] = tmp;
}
void rotate(char *a, int i, int j) {
int k;
char tmp;
tmp = a[j];
for(k=j; k>i; 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<fact(strlen(str)); i++) {
printf("\"%s\"\n", permuts[i]);
free(permuts[i]);
}
free(permuts);
return 0;
}
输出正确：
"abc"
"acb"
"bac"
"bca"
"cab"
"cba"
词法字符串排列的另一个转折是将排列存储在动态分配的字符串指针数组中，并将该数组传递给 qsort 以提供按词法顺序的输出。由于排列呈指数增长，因此在每次分配后检查内存耗尽尤为重要。以下字符串大小限制为 16 个字符，这仍可能导致内存耗尽，具体取决于可用内存量。
已更新 传递数组地址以保存字符串排列对于重新分配在递归函数中起作用是必需的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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
<snip>
==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)
我假设你想要一个递归版本。
这里有两种解决方法。
解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 有效且易于理解，但我怀疑我们可能会在排序上浪费一些时间。这个解决方案更接近你所拥有的。
递归基本上是变相的数学归纳法，这种思维方式对于理解如何编写递归程序非常有用。
例如，假设您的置换方法总是按字典顺序构造排列。
这里是一个递归版本，基于这个假设，请阅读评论以了解发生了什么。
// 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 n-i 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 的算法，其他人提到过，但没有提到它的名字。
看到这个link：http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
这是 C++ std::next 和许多其他库所使用的。
这个算法甚至在有重复元素时也有效，而且实际上可以用来生成组合！ （用零和一初始化你的数组）。
这是自愿一个不回答这个问题的答案。
This other question 被标记为与此重复。这个答案对于另一个问题来说是可以接受的，即使它在这里没有意义。
这可能是一个简单的递归 C 实现，用于按字典顺序获取所有排列。它没有优化，但易于理解和实施：
- 获取要排列的元素的数组
- 在任何一步，遍历直到这里还没有使用过的元素
- 将迭代元素之一添加到已用元素数组
- 递归
- 当使用的元素数组已满时打印它。
具体实现：
#include <stdio.h>
#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<n; i++) {
found = 0;
for (j=0; j<pos; j++) {
if (fullarr[i] == begin[j]) {
found = 1;
break;
}
}
if (! found) {
begin[pos] = fullarr[i];
disp(fullarr, n, begin, pos+1);
}
}
}
int main() {
int i;
int fullarr[SIZE], begin[SIZE];
for (i=0; i<SIZE; i++) {
fullarr[i] = i;
}
disp(fullarr, SIZE, begin, 0);
return 0;
}
基本思路是以我们的主字符串作为“”开始，其余字符串作为 "abc"（或任何您想要的）。
现在向主字符串逐个字符追加。这样它就不会重复使用的字符（对于所有可能的字符）。
重复相同的操作直到得到长度 n（主字符串的长度）。
好的，解释不清楚，但请注意代码。它会让一切变得清晰。
#include<iostream>
void perm(std::string sub, std::string rem, int n)
{
if(n==0)
//print if n is zero i.e length achieved
std::cout<<sub<<"\n";
for(int i=0; i<n; i++)
//append a character and pass remaining to rem string
perm(sub + rem[i] , rem.substr(0,i) + rem.substr(i+1,n-1), n-1);
}
int main()
{
perm("", "abc", 3);
}
输出
abc
acb
bac
bca
cab
cba
void permute(string str,int index)
{
if(index == str.size())
{
cout<<str<<" ";
return;
}
else
{
for(int j=index;j<str.size();j++)
{
if(str[index] <= str[j]) // swap only in sorted order
swap(str[j],str[index]);
permute(str,index+1);
if(str[index] <= str[j]) // swap only in sorted order
swap(str[j],str[index]);
}
}
}
int main()
{
int t;
string str;
scanf("%d",&t);
while(t--){
// scanf("%d",&n);
cin>>str;
sort(str.begin(),str.end());
permute(str,0);
cout<<endl;
}
return 0;
}
好的，这是使用任何编程语言的方法。我将通过写下 S4 的所有排列来说明它，但可以很容易地看出它是如何概括的。人们需要了解称为循环的特殊排列。循环 (132) 是将 1 发送到 3、将 3 发送到 2 以及将 2 发送回 1 的排列。想象一个编号的圆圈，然后旋转该圆圈。循环（321）和（213）代表相同的循环和排列。一个 "two cycle" (13) 是一个 换位 ，只需交换 1 和 3 并保持所有其他成员相同。 A "one cycle" (2) 将 2 发送到 2 并保持其他一切不变，即它对任何元素都不做任何事情。但是，我会在下面写一个循环，使它看起来"pretty"。
有了这个介绍，让我们从集合 {[1,2,3,4]} 开始。我们通过以下几组循环对该组进行操作：
集合{(4)}。这对我们没有任何帮助
{[1,2,3,4]}.
我们用循环对 {(3),(43)} 对这个集合进行操作。这给了我们
{ [1,2,3,4], [1,2,4,3] },
一个包含两个元素的集合。我们用循环对第二组进行操作：
{(2),(32),(432)}。我们有
(2) { [1,2,3,4], [1,2,4,3] } = { [1,2,3,4], [1,2,4,3] }
(32) { [1,2,3,4], [1,2,4,3] } = { [1,3,2,4], [1,3,4,2] }
(432) { [1,2,3,4], [1,2,4,3] } = { [1,4,2,3], [1,4,3,2] }
写出这些，我们有一组 6 个元组：
{ [1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2 [1,4,2,3], [1,4,3,2] }
最后我们用循环 {(1),(21),(321),(4321)} 击中了这个集合。这将为我们提供 24 个元组，它们是 S4 的 4x6 = 24 个排列——全部按字典顺序排列！
from itertools import combinations
S,k = input().split()
for i in list(range(int(k)+1))[1:]:
for e in combinations(sorted(S),i ):
print(''.join(e))
我想按字典顺序打印字符串的所有排列。我写了这段代码：
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" <
"cba" "cba"
> "cab"
有人可以帮我解决这个问题吗？我看到了一些算法，但它们看起来很难。我想我可以将所有生成的字符串保存在一个数组中，然后对这个数组进行排序，但是我不会写这个（我是 C 的初学者）。
在 C
有一个非常简单的算法描述（加上实现）Given a string, print all permutations of it in sorted order. For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.
We have discussed a program to print all permutations in this post, but here we must print the permutations in increasing order.
Following are the steps to print the permutations lexicographic-ally
Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.
Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.
Steps to generate the next higher permutation:
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.
Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.
Swap the two characters found in above 2 steps.
Sort the substring (in non-decreasing order) after the original index of ‘first character’.
我在下面重新实现了它：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
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<strSize && inStr[k];++k)
{
if (inStr[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
cab
cba
在 C++ 中
<algorithm> 库中的 std::next_permutation 会为您执行此操作，只需确保您先对容器进行排序：
Return value
true if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).
例如：
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)));
输出：
a b c
a c b
b a c
b c a
c a b
c b a
恕我直言，首先对字符串的字符进行排序会更简单，因为排列数 (n!) 总是大于（或等于 n = 1 或 2）字符数。
你离解决方案不远，但你必须旋转而不是交换。这里有一个细微的变化，returns 打印在 main 中的动态分配字符串数组：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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; k<j; k++) {
a[k] = a[k+1];
}
a[j] = tmp;
}
void rotate(char *a, int i, int j) {
int k;
char tmp;
tmp = a[j];
for(k=j; k>i; 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<fact(strlen(str)); i++) {
printf("\"%s\"\n", permuts[i]);
free(permuts[i]);
}
free(permuts);
return 0;
}
输出正确：
"abc"
"acb"
"bac"
"bca"
"cab"
"cba"
词法字符串排列的另一个转折是将排列存储在动态分配的字符串指针数组中，并将该数组传递给 qsort 以提供按词法顺序的输出。由于排列呈指数增长，因此在每次分配后检查内存耗尽尤为重要。以下字符串大小限制为 16 个字符，这仍可能导致内存耗尽，具体取决于可用内存量。
已更新 传递数组地址以保存字符串排列对于重新分配在递归函数中起作用是必需的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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
<snip>
==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)
我假设你想要一个递归版本。
这里有两种解决方法。
解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 有效且易于理解，但我怀疑我们可能会在排序上浪费一些时间。这个解决方案更接近你所拥有的。
递归基本上是变相的数学归纳法，这种思维方式对于理解如何编写递归程序非常有用。
例如，假设您的置换方法总是按字典顺序构造排列。
这里是一个递归版本，基于这个假设，请阅读评论以了解发生了什么。
// 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 n-i 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 的算法，其他人提到过，但没有提到它的名字。
看到这个link：http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
这是 C++ std::next 和许多其他库所使用的。
这个算法甚至在有重复元素时也有效，而且实际上可以用来生成组合！ （用零和一初始化你的数组）。
这是自愿一个不回答这个问题的答案。
This other question 被标记为与此重复。这个答案对于另一个问题来说是可以接受的，即使它在这里没有意义。
这可能是一个简单的递归 C 实现，用于按字典顺序获取所有排列。它没有优化，但易于理解和实施：
- 获取要排列的元素的数组
- 在任何一步，遍历直到这里还没有使用过的元素
- 将迭代元素之一添加到已用元素数组
- 递归
- 当使用的元素数组已满时打印它。
具体实现：
#include <stdio.h>
#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<n; i++) {
found = 0;
for (j=0; j<pos; j++) {
if (fullarr[i] == begin[j]) {
found = 1;
break;
}
}
if (! found) {
begin[pos] = fullarr[i];
disp(fullarr, n, begin, pos+1);
}
}
}
int main() {
int i;
int fullarr[SIZE], begin[SIZE];
for (i=0; i<SIZE; i++) {
fullarr[i] = i;
}
disp(fullarr, SIZE, begin, 0);
return 0;
}
基本思路是以我们的主字符串作为“”开始，其余字符串作为 "abc"（或任何您想要的）。
现在向主字符串逐个字符追加。这样它就不会重复使用的字符（对于所有可能的字符）。
重复相同的操作直到得到长度 n（主字符串的长度）。
好的，解释不清楚，但请注意代码。它会让一切变得清晰。
#include<iostream>
void perm(std::string sub, std::string rem, int n)
{
if(n==0)
//print if n is zero i.e length achieved
std::cout<<sub<<"\n";
for(int i=0; i<n; i++)
//append a character and pass remaining to rem string
perm(sub + rem[i] , rem.substr(0,i) + rem.substr(i+1,n-1), n-1);
}
int main()
{
perm("", "abc", 3);
}
输出
abc
acb
bac
bca
cab
cba
void permute(string str,int index)
{
if(index == str.size())
{
cout<<str<<" ";
return;
}
else
{
for(int j=index;j<str.size();j++)
{
if(str[index] <= str[j]) // swap only in sorted order
swap(str[j],str[index]);
permute(str,index+1);
if(str[index] <= str[j]) // swap only in sorted order
swap(str[j],str[index]);
}
}
}
int main()
{
int t;
string str;
scanf("%d",&t);
while(t--){
// scanf("%d",&n);
cin>>str;
sort(str.begin(),str.end());
permute(str,0);
cout<<endl;
}
return 0;
}
好的，这是使用任何编程语言的方法。我将通过写下 S4 的所有排列来说明它，但可以很容易地看出它是如何概括的。人们需要了解称为循环的特殊排列。循环 (132) 是将 1 发送到 3、将 3 发送到 2 以及将 2 发送回 1 的排列。想象一个编号的圆圈，然后旋转该圆圈。循环（321）和（213）代表相同的循环和排列。一个 "two cycle" (13) 是一个 换位 ，只需交换 1 和 3 并保持所有其他成员相同。 A "one cycle" (2) 将 2 发送到 2 并保持其他一切不变，即它对任何元素都不做任何事情。但是，我会在下面写一个循环，使它看起来"pretty"。
有了这个介绍，让我们从集合 {[1,2,3,4]} 开始。我们通过以下几组循环对该组进行操作：
集合{(4)}。这对我们没有任何帮助
{[1,2,3,4]}.
我们用循环对 {(3),(43)} 对这个集合进行操作。这给了我们
{ [1,2,3,4], [1,2,4,3] },
一个包含两个元素的集合。我们用循环对第二组进行操作： {(2),(32),(432)}。我们有
(2) { [1,2,3,4], [1,2,4,3] } = { [1,2,3,4], [1,2,4,3] }
(32) { [1,2,3,4], [1,2,4,3] } = { [1,3,2,4], [1,3,4,2] }
(432) { [1,2,3,4], [1,2,4,3] } = { [1,4,2,3], [1,4,3,2] }
写出这些，我们有一组 6 个元组：
{ [1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2 [1,4,2,3], [1,4,3,2] }
最后我们用循环 {(1),(21),(321),(4321)} 击中了这个集合。这将为我们提供 24 个元组，它们是 S4 的 4x6 = 24 个排列——全部按字典顺序排列！
from itertools import combinations
S,k = input().split()
for i in list(range(int(k)+1))[1:]:
for e in combinations(sorted(S),i ):
print(''.join(e))