在C中

在geeksforgeeks上有一个非常简单的算法描述（包括实现）：

给定一个字符串，按排序顺序打印它的所有排列。例如，如果输入字符串为“ ABC”，则输出应为“ ABC，ACB，BAC，BCA，CAB，CBA”。

我们在本文中讨论了一个打印所有排列的程序，但是在这里我们必须按升序打印排列。

以下是按词典顺序打印排列的步骤

1. 以非降序对给定的字符串进行排序并打印。第一个排列始终是按非降序排序的字符串。

2. 开始生成下一个更高的排列。直到无法进行更高的排列为止。如果我们达到一个排列，其中所有字符都以非递增顺序排序，那么该排列就是最后的排列。

生成下一个较高排列的步骤：
1.进行先前打印的排列，并在其中找到最右边的字符，该字符小于下一个字符。让我们将此字符称为“第一个字符”。

1. 现在找到“第一个角色”的上限。天花板是“第一个字符”右侧的最小字符，大于“第一个字符”。让我们将ceil字符称为“第二个字符”。

2. 交换在以上两个步骤中找到的两个字符。

3. 在“第一个字符”的原始索引之后对子字符串进行排序（以不降序排列）。

我在下面重新实现了它：

#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 ++中

std::next_permutation从<algorithm>库中为您执行此操作，只需确保首先对容器进行排序：

返回值

如果函数可以将对象重新排列为字典序更大的排列，则为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
cab
cba

现场演示