by: Jayson McleodPosted on

The permutation algorithm in C language that utilizes recursion is ready for your exploration. The algorithm originates from Eytan Gurari’s lecture notes for the CIS 680 course, unfortunately no longer accessible online. 

Table of Contents

However, they can still be unearthed via the Wayback Machine under the “CIS 680: DATA STRUCTURES” section. An intriguing illustration, portraying a partial recursion tree, borrowed from his materials, serves as a visual aid for enhanced comprehension.

Below is an example of a C language program implementation for number permutation, utilizing recursion:

#include <string.h>

typedef void (*permutationfn)(const char *);

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

static void permutations_recursive(char *str, unsigned int left, unsigned int right,
        permutationfn fun)
{
    if (left == right) {
        fun(str);
    }
    else {
        unsigned int i;
        for (i = left; i <= right; i++) {
            swap(str + left, str + i);
            permutations_recursive(str, left + 1, right, fun);
            swap(str + left, str + i);
        }
    }
}

void permutations(char *str, permutationfn fun)
{
    permutations_recursive(str, 0, strlen(str) - 1, fun);
}

This code is adaptable for generating permutations of various number combinations, allowing for an in-depth exploration of recursion in C language.

Example

Here is a sample program:

#include <stdio.h>

int main(void)
{
    char str[] = "ABCD";
    permutations(str, (permutationfn)puts);
    return 0;
}

The output yields various permutations:

ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC


Delve into the universe of recursive permutations in C language, unveiling the capacity to generate a plethora of combinations.

Summary


In this exploration of a C language program for number permutation using recursion, we’ve unveiled a robust algorithm capable of generating a myriad of combinations from a given set of elements. Courtesy of Eytan Gurari’s lecture notes for CIS 680, this algorithm offers a distinctive insight into the universe of recursive permutations, even as the primary source becomes increasingly elusive online.

As demonstrated in this code, recursion allows for an intricate examination of the problem, breaking it down into smaller, manageable steps. By recursively swapping elements, the program explores and records all possible arrangements, providing a comprehensive overview of the diverse permutations.

The algorithm serves as a testament to the profound capabilities embedded in recursive programming. Each output, a distinct arrangement, underscores the algorithm’s utility in scenarios demanding a thorough exploration of all possible combinations arising from a given set of elements. The adaptability and precision inherent in this algorithm earmark it as a valuable resource for programmers, mathematicians, and analysts alike, seeking to navigate the complex terrains of combinatorial challenges with grace and efficiency.

Leave a Reply