List all permutations of a given string in dictionary order in C

Understanding String Permutations

String permutations refer to all possible arrangements of characters in a given string. The dictionary order means sorting them lexicographically.

We will explore three different methods to list all permutations of a given string in C.

Method 1: Using Recursion

This method generates permutations recursively by swapping characters.

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

void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *str, int l, int r) {
    if (l == r)
        printf("%s\n", str);
    else {
        for (int i = l; i <= r; i++) {
            swap((str + l), (str + i));
            permute(str, l + 1, r);
            swap((str + l), (str + i));
        }
    }
}

int main() {
    char str[] = "abc";
    permute(str, 0, strlen(str) - 1);
    return 0;
}
            

Method 2: Using Next Permutation Algorithm

This method generates permutations using the next permutation algorithm.

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

int compare(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int next_permutation(char *str, int n) {
    int i = n - 2;
    while (i >= 0 && str[i] >= str[i + 1]) i--;
    if (i < 0) return 0;
    int j = n - 1;
    while (str[j] <= str[i]) j--;
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
    qsort(str + i + 1, n - i - 1, sizeof(char), compare);
    return 1;
}

int main() {
    char str[] = "abc";
    int n = strlen(str);
    qsort(str, n, sizeof(char), compare);
    do {
        printf("%s\n", str);
    } while (next_permutation(str, n));
    return 0;
}
            

Method 3: Using Recursion with Sorting

This method generates and sorts permutations manually.

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

void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

void permuteSorted(char *str, int l, int r) {
    if (l == r)
        printf("%s\n", str);
    else {
        for (int i = l; i <= r; i++) {
            swap((str + l), (str + i));
            permuteSorted(str, l + 1, r);
            swap((str + l), (str + i));
        }
    }
}

int main() {
    char str[] = "abc";
    int n = strlen(str);
    permuteSorted(str, 0, n - 1);
    return 0;
}