Permutation of Strings in C

Back to: C Tutorials For Beginners and Professionals

Permutation of Strings in C Language with Examples

In this article, I will discuss the Permutation of Strings in C Language with Examples. Please read our previous article discussing How to Check if 2 Strings are Anagrams in C Language with Examples. At the end of this article, you will understand the following five approaches to Check if 2 Strings are Anagram:

1. What is the Permutation of Strings?
2. Permutation of Strings in C Using Backtracking
3. Permutation of Strings in C Using Heap’s Algorithm
4. Permutation of Strings in C Using Lexicographic Order
5. Permutation of Strings in C Using Breadth-First Search Method

Permutation of Strings in C:

Now, we will see how to find permutations of a string. First of all, we need to understand what it means by permutations. Then, we will see how to find permutations using c language with multiple approaches. Please observe the following string.

Here, we have taken a string ‘ABC’. And we want all permutations with all arrangements of ABC. The total number of permutations or arrangements we can of string ‘ABC’ is n! which means 3! Which is 6 (3*2*1). So, 6 arrangements are possible for the string ABC. Permutations are:

1. ABC
2. ACB
3. BAC
4. BCA
5. CBA
6. CAB

So, there are six possible arrangements of those alphabets of string ABC. Now we want all these arrangements, so how do we get this arrangement? For that, we will create some procedure, or we will create some logic for generating all these permutations. The following are the four approaches we can use to implement this logic:

1. Backtracking (Recursive Approach): This method is the most straightforward and commonly used. It involves swapping each character with every other character and then recursively solving for the rest of the string.
2. Heap’s Algorithm (Iterative or Recursive): Heap’s algorithm generates all possible permutations of n objects. It can be implemented either iteratively or recursively.
3. Lexicographic Order (Using Next Permutation): This approach generates permutations in lexicographic order. It can be implemented using the next permutation algorithm, which rearranges the string into the lexicographically next greater permutation.
4. Breadth-First Search (BFS) Approach: This method uses a queue to generate permutations in a breadth-first manner.

Approach 1: Permutation of Strings in C Example Using Backtracking Method

The backtracking method for generating permutations of a string in C is a systematic way to go through all the possible configurations of the string. This method involves making a choice, then recursively exploring the permutations that can be built from that choice, and then undoing the choice (backtracking) to make a different choice. Here’s how you can implement string permutations using backtracking in C:

• Swap Function: Create a function to swap two characters in a string.
• Recursive Permute Function: Implement a recursive function to generate permutations. This function swaps the current character with each subsequent character and then calls itself with the next character fixed.
• Backtracking: After each recursive call, swap back the characters to revert the string to its original state before the next iteration. This is the backtracking step.
• Base Case: The base case for the recursion is when the current character is at the end of the string.

Here’s a sample C code for this:

#include <stdio.h>
#include <string.h>

// Function to swap values at two pointers
void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

// Recursive function to generate permutations using backtracking
void permute(char *a, int l, int r) {
   if (l == r) {
       printf("%s\n", a);
   } else {
       for (int i = l; i <= r; i++) {
          swap((a + l), (a + i));
          permute(a, l + 1, r);
          swap((a + l), (a + i)); // backtrack
       }
   }
}

// Driver program to test the above functions
int main() {
    char str[] = "ABC";
    permute(str, 0, strlen(str) - 1);
    return 0;
}

In this code:

• swap is used to swap two characters.
• permute is the recursive function that generates the permutations. It recursively fixes one character at a time and generates all permutations for the rest of the string. After exploring all permutations with a fixed character, it backtracks to explore permutations with a different character fixed.
• The main function initializes the string and calls permute with the initial left and right indices.

When you run this program with a string, it will output all the permutations of that string. The backtracking ensures that all characters are considered for each position in the string, and the original state of the string is restored after each complete permutation is printed.

• Pros: Simple and intuitive.
• Cons: Can be inefficient due to many recursive calls, especially for longer strings.

Approach 2: Permutation of Strings in C Example Using Heap’s Algorithm

Heap’s Algorithm is an efficient method to generate all possible permutations of a given sequence (like a string). The algorithm minimizes movement: it generates each permutation by swapping only two elements of the array. Here’s how you can implement Heap’s Algorithm in C for string permutations:

#include <stdio.h>
#include <string.h>

// Function to swap values at two pointers
void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

// Function to print permutations of string
// This function takes three parameters:
// 1. String
// 2. Starting index of the string
// 3. Ending index of the string.
void heapPermute(char *a, int size, int n) {
    if (size == 1) {
        printf("%s\n", a);
    } else {
        for (int i = 0; i < size; i++) {
            heapPermute(a, size - 1, n);

            // if size is odd, swap first and last element
            // if size is even, swap ith and last element
            swap((size % 2) ? a : a + i, a + size - 1);
        }
    }
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);

    int n = strlen(str);
    heapPermute(str, n, n);
    return 0;
}

In this program:

• swap function is used to swap two characters.
• heapPermute is the function that implements Heap’s Algorithm. It generates all permutations of the string by recursively calling itself and swapping characters according to the algorithm’s rules.
• The main function reads a string from the user and calls heapPermute with the string and its length.

Heap’s Algorithm is efficient and does not involve creating additional copies of the string or using extra space for each recursive call, unlike some other permutation-generating algorithms. This makes it particularly suitable for generating permutations of longer strings.

• Pros: More efficient than the basic recursive approach.
• Cons: The logic is less intuitive than the simple backtracking method.

Approach 3: Permutation of Strings in C Example Using Lexicographic Order

Generating permutations of a string in lexicographic (or dictionary) order in C is a classic algorithmic problem. The approach is based on finding the next higher lexicographic permutation of the set of characters until no higher permutation is possible. This is achieved by following these steps:

• Find the Rightmost Character Smaller than its Next Character: Traverse the string from right to left and find the first character smaller than the character to its right. This is needed to identify the point of rearrangement.
• Find the Rightmost Character Greater than the Above Found Character: Again, traverse from right to left and find the first character greater than the character found in Step 1.
• Swap These Two Characters: Swap the characters found in steps 1 and 2.
• Reverse the String After the Original Position of the First Character: Reverse the string from the position next to the character found in Step 1 till the end of the string.
• Repeat the Process: Keep repeating these steps until no higher permutation is possible, i.e., the string is sorted in descending order.

Here’s a C code example to illustrate this:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// Function to swap values at two pointers
void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

// Function to reverse a string from `start` to `end`
void reverse(char *str, int start, int end) {
    while(start < end) {
        swap(&str[start], &str[end]);
        start++;
        end--;
    }
}

// Function to find the next lexicographic permutation
bool nextPermutation(char *str, int n) {
    int i, j;

    // Step 1
    for (i = n - 2; i >= 0; i--) {
        if (str[i] < str[i + 1])
            break;
    }

    // If no such character is found, then all are sorted in descending order
    if (i < 0)
        return false;

    // Step 2
    for (j = n - 1; j > i; j--) {
        if (str[j] > str[i])
            break;
    }

    // Step 3
    swap(&str[i], &str[j]);

    // Step 4
    reverse(str, i + 1, n - 1);

    return true;
}

int main() {
    char str[] = "ABC";
    int n = strlen(str);

    // Print permutations in lexicographic order
    do {
        printf("%s\n", str);
    } while (nextPermutation(str, n));

    return 0;
}

In this code:

• The swap function swaps the values of two characters.
• The reverse function reverses a part of the string.
• The nextPermutation function finds the next lexicographic permutation.
• The main function repeatedly calls nextPermutation and prints each permutation until all permutations are exhausted.

This program will print all permutations of the given string str in lexicographic order. Remember, the initial string should be in its first lexicographic permutation (i.e., sorted in ascending order) to cover all permutations.

• Pros: Generates permutations in a sorted order without recursion.
• Cons: Requires understanding of next permutation logic.

Approach 4: Permutation of Strings in C Example Using Breadth-First Search Method

Implementing a permutation generator for strings in C using a Breadth-First Search (BFS) approach is an interesting exercise. Unlike the more common recursive methods (like backtracking or Heap’s Algorithm), BFS builds permutations level by level, iteratively. This method can be implemented using a queue data structure. Here’s a basic outline of how you might implement this:

• Initialize a Queue: Start with a queue containing a single empty string or the string’s first character.
• Iteratively Build Permutations: For each level (up to the length of the input string), dequeue an element and enqueue new strings formed by inserting the next character of the input string at all possible positions in the dequeued string.
• Result: Once the length of the strings in the queue is equal to the length of the input string, all elements in the queue are the permutations of the input string.

However, implementing this in C can be complex due to the lack of a standard queue library. You would need to implement your own queue data structure. Here’s a simplified version of how this could look in C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 1000

// A Queue Node
typedef struct Node {
    char data[100];
    struct Node* next;
} Node;

// Queue structure
typedef struct {
    Node *front, *rear;
} Queue;

// Function to create a new queue node
Node* newNode(char *str) {
    Node* temp = (Node*)malloc(sizeof(Node));
    strcpy(temp->data, str);
    temp->next = NULL;
    return temp;
}

// Function to create an empty queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Function to add a string to the queue
void enQueue(Queue* q, char *str) {
    Node* temp = newNode(str);

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
}

// Function to remove a string from the queue
void deQueue(Queue* q, char *str) {
    if (q->front == NULL)
        return;

    Node* temp = q->front;
    strcpy(str, q->front->data);

    q->front = q->front->next;

    if (q->front == NULL)
        q->rear = NULL;

    free(temp);
}

// Function to check if the queue is empty
int isEmpty(Queue* q) {
    return (q->front == NULL);
}

// Function to generate permutations of the string using BFS
void generatePermutations(char *str) {
    Queue* q = createQueue();
    enQueue(q, "");

    while (!isEmpty(q)) {
        char s[100];
        deQueue(q, s);

        // If the length of s is equal to length of str, it is a permutation
        if (strlen(s) == strlen(str)) {
            printf("%s\n", s);
        } else {
            for (int i = 0; i <= strlen(s); i++) {
                char newStr[100];
                strncpy(newStr, s, i);
                newStr[i] = str[strlen(s)];
                strcpy(newStr + i + 1, s + i);
                enQueue(q, newStr);
            }
        }
    }

    free(q);
}

int main() {
    char str[MAX_SIZE];
    printf("Enter a string: ");
    scanf("%s", str);

    generatePermutations(str);
    return 0;
}

In this program:

• A queue is used to store intermediate stages of permutation.
• The generatePermutations function uses BFS to generate and print all permutations of the string.
• It dequeues a string, and for each position in the string, it enqueues a new string with the next character of the input string inserted at that position.

This BFS approach, while an interesting alternative to recursive methods, is generally less efficient in terms of time and space complexity, especially for longer strings. Implementing a queue in C also adds to the complexity of the solution.

• Pros: Non-recursive, good for understanding how permutations are built step by step.
• Cons: Can be less efficient in space and time than other methods.

Choosing the Right Approach

• For Learning and Simplicity: Use the backtracking method.
• For Efficiency: Consider Heap’s algorithm.
• For Generating Permutations in Sorted Order: Use the lexicographic order method.
• For Educational Purposes: The BFS approach can be insightful.

In the next article, I will discuss Structure in C Language with Examples. In this article, I explain the Permutation of String in C Language with Examples. I hope you enjoy this Permutation of String in C Language with Examples article. I would like to have your feedback. Please post your feedback, questions, or comments about this article.