Print all distinct permutations of a given string with duplicates
问题描述
Given a string that may contain duplicates, write a function to print all permutations of given string such that no permutation is repeated in output.
Examples:
Input: str[] = "AB"
Output: AB BA
Input: str[] = "AA"
Output: AA
Input: str[] = "ABC"
Output: ABC ACB BAC BCA CBA CAB
Input: str[] = "ABA"
Output: ABA AAB BAA
Input: str[] = "ABCA"
Output: AABC AACB ABAC ABCA ACBA ACAB BAAC BACA
BCAA CABA CAAB CBAA
We have discussed an algorithm to print all permutations in below post. It is strongly recommended to refer below post as a prerequisite of this post.
算法
Write a C program to print all permutations of a given string
The algorithm discussed on above link doesn’t handle duplicates.
// 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 \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 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;
}