本文共 2768 字，大约阅读时间需要 9 分钟。

原文地址：

已知一个字符串，其中可能包括相同的字符。写一个函数打印这些字符的排列，但不能有重复的排列。

例子：

Input:  str[] = "AB"Output: AB BAInput:  str[] = "AA"Output: AAInput:  str[] = "ABC"Output: ABC ACB BAC BCA CBA CABInput:  str[] = "ABA"Output: ABA AAB BAAInput: str[] = "ABCA"Output: AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA

我们已经在前面讨论过了打印所有的排列，但是那个代码不能处理相同的字符，打印出来的会有相同的排序。

// Program to print all permutations of a string in sorted order.#include 
   
    #include 
    
     #include 
     
      /* Following function is needed for library function qsort(). */int compare(const void *a, const void * b){    return ( *(char *)a - *(char *)b );}// A utility function two swap two characters a and bvoid swap(char* a, char* b){    char t = *a;    *a = *b;    *b = t;}// This function finds the index of the smallest character// which is greater than 'first' and is present in str[l..h]int findCeil(char str[], char first, int l, int h){    // initialize index of ceiling element    int ceilIndex = l;    // Now iterate through rest of the elements and find    // the smallest character greater than 'first'    for (int i = l+1; i <= h; i++)        if (str[i] > first && str[i] < str[ceilIndex])            ceilIndex = i;    return ceilIndex;}// Print all permutations of str in sorted ordervoid sortedPermutations(char str[]){    // Get size of string    int size = strlen(str);    // Sort the string in increasing order    qsort(str, size, sizeof( str[0] ), compare);    // Print permutations one by one    bool isFinished = false;    while (!isFinished)    {        // print this permutation        static int x = 1;        printf("%d  %s \n", x++, str);        // Find the rightmost character which is smaller than its next        // character. Let us call it 'first char'        int i;        for (i = size - 2; i >= 0; --i)            if (str[i] < str[i+1])                break;        // If there is no such chracter, all are sorted in decreasing order,        // means we just printed the last permutation and we are done.        if (i == -1)            isFinished = true;        else        {            // Find the ceil of 'first char' in right of first character.            // Ceil of a character is the smallest character greater than it            int ceilIndex = findCeil(str, str[i], i + 1, size - 1);            // Swap first and second characters            swap(&str[i], &str[ceilIndex]);            // Sort the string on right of 'first char'            qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);        }    }}// Driver program to test above functionint main(){    char str[] = "ACBC";    sortedPermutations( str );    return 0;}
     
    
   

输出：

1  ABCC2  ACBC3  ACCB4  BACC5  BCAC6  BCCA7  CABC8  CACB9  CBAC10  CBCA11  CCAB12  CCBA

时间复杂度： O(n2 * n!)

转载地址：http://hgqii.baihongyu.com/