Respuesta :
Answer:
#include <stdio.h>
#include <string.h>
void swap(char *x, char *y) {
char temp = *x;
*x = *y;
*y = temp;
}
// Uses a hashset-like approach to check for duplicates
int isUnique(char *str, int start, int end) {
int charCounts[256] = {0}; // Assuming ASCII characters
for (int i = start; i <= end; i++) {
charCounts[str[i]]++;
if (charCounts[str[i]] > 1) {
return 0; // Not unique
}
}
return 1; // Unique
}
void generatePermutations(char *str, int start, int end) {
if (start == end) {
if (isUnique(str, 0, end)) { // Check for complete permutation uniqueness
printf("%s\n", str);
}
} else {
for (int i = start; i <= end; i++) {
swap(str + start, str + i);
generatePermutations(str, start + 1, end);
swap(str + start, str + i); // Backtrack
}
}
}
int main() {
char str[] = "aat";
int n = strlen(str);
generatePermutations(str, 0, n - 1);
return 0;
}
Explanation:
swap Function: A simple function to swap two characters within a string.
isUnique Function: This function determines if a given permutation is unique. It creates a temporary array to keep track of the count of each character. If any character appears more than once, it's not unique.
generatePermutations Function:
Base Case: If start == end, it means a permutation is formed. We check its overall uniqueness with isUnique and print it if it passes the test.
Recursive Step:
Iterate through the string from start to end.
Swap the character at start with the current character in the loop.
Recursively call generatePermutations to explore permutations with the next character fixed.
Backtrack by swapping the characters back to their original positions.
main Function:
Defines the input string.
Calls generatePermutations to start the process.
Key Points:
Duplicate Prevention: The isUnique function ensures that only unique permutations are printed.
Backtracking: The swapping followed by backtracking is the core mechanism for generating different permutations.
