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

This method generates permutations in lexicographical order.

#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 i = strlen(str) - 2;
    while (i >= 0 && str[i] >= str[i + 1]) i--;
    if (i < 0) return 0;
    int j = strlen(str) - 1;
    while (str[j] <= str[i]) j--;
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
    qsort(str + i + 1, strlen(str) - i - 1, sizeof(char), compare);
    return 1;
}

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

Method 3: Using STL (C++)

This method sorts the string and uses C++'s next_permutation function.

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

void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

bool nextPermutation(char *str, int n) {
    int i = n - 2;
    while (i >= 0 && str[i] >= str[i + 1]) i--;
    if (i < 0) return false;
    int j = n - 1;
    while (str[j] <= str[i]) j--;
    swap(&str[i], &str[j]);
    for (int k = i + 1, l = n - 1; k < l; k++, l--) {
        swap(&str[k], &str[l]);
    }
    return true;
}

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