打印给定字符串的所有不同排列，并使用重复项-yiteyi-C++库

给定一个可能包含重复项的字符串，编写一个函数来打印给定字符串的所有排列，以便在输出中不重复任何排列。例如：

null

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

我们在下面的帖子中讨论了打印所有排列的算法。强烈建议将以下帖子作为该帖子的先决条件。编写一个C程序来打印给定字符串的所有排列上面链接中讨论的算法不处理重复项。

CPP

                         // Program to print all permutations of a                       
                         // string in sorted order.                       
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
                         #include <string.h>                       
           
                         /* 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 b                       
                         void                                     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 order                       
                         void                                     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 "                                     , 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 character, 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 function                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "ACBC"                                     ;                       
                                                 sortedPermutations(str);                       
                                                 return                                     0;                       
                         }                       

输出

1  ABCC 2  ACBC 3  ACCB 4  BACC 5  BCAC 6  BCCA 7  CABC 8  CACB 9  CBAC 10  CBCA 11  CCAB 12  CCBA

以上代码摘自Lazy先生的以下评论。时间复杂度：O（n） ^2. *n！）辅助空间：O（1）

上述算法的时间复杂度为O（n2*n！）但我们可以通过对该算法进行一些修改，获得更好的时间复杂度O（n！*n），这在输入中所有不同字符的情况下都存在。独特字符算法可在此处找到—— https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

有效方法： 在查找所有排列的递归函数中，我们可以使用无序_集来处理活动字符串中剩余的重复元素。在对字符串的元素进行迭代时，我们将在无序_集中检查该元素，如果找到它，我们将跳过该迭代，否则我们将把该元素插入无序_集中。由于所有无序_集操作，如insert（）和find（）平均都在O（1）时间内，因此使用无序_集不会改变算法的时间复杂度。

算法实现如下——

C++

                         #include <algorithm>                       
                         #include <iostream>                       
                         #include <unordered_set>                       
                         using                                     namespace                                     std;                       
           
                         void                                     printAllPermutationsFast(string s, string l)                       
                         {                       
                                                 if                                     (s.length() < 1) {                       
                                                 cout << l + s << endl;                       
                                                 }                       
                                                 unordered_set<                                     char                                     > uset;                       
                                                 for                                     (                                     int                                     i = 0; i < s.length(); i++) {                       
                                                 if                                     (uset.find(s[i]) != uset.end()) {                       
                                                 continue                                     ;                       
                                                 }                       
                                                 else                                     {                       
                                                 uset.insert(s[i]);                       
                                                 }                       
                                                 string temp =                                     ""                                     ;                       
                                                 if                                     (i < s.length() - 1) {                       
                                                 temp = s.substr(0, i) + s.substr(i + 1);                       
                                                 }                       
                                                 else                                     {                       
                                                 temp = s.substr(0, i);                       
                                                 }                       
                                                 printAllPermutationsFast(temp, l + s[i]);                       
                                                 }                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 string s =                                     "ACBC"                                     ;                       
                                                 sort(s.begin(), s.end());                       
                                                 printAllPermutationsFast(s,                                     ""                                     );                       
                                                 return                                     0;                       
                         }                       

输出

ABCCACBCACCBBACCBCACBCCACABCCACBCBACCBCACCABCCBA

时间复杂度–O（n*n！）辅助空间–O（n）

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章