# Write a c program for printing all permutation of a string

Write a c program for printing all permutation of a string is a good problem to learn recursive backtracking algorithm.Let us consider a string “*abcd*“. Then permutation of abc will be *abcd, acbd, bacd, bcad, cbad, cabd*.

The permutation is all different arrangements of a given sequence but how can we generate all permutation?

A permutation can be obtained by selecting an element in the given set and recursively permuting the remaining elements.

#include <stdio.h> #include <string.h> void swap(char *p, char *q) { char temp; temp = *p; *p = *q; *q = temp; } void permute(char *a, int i, int length) { int j; if (i == length) { for(int x=0; x <= length; x++) printf("%c ", a[x]); printf("\n"); } else { for (j = i; j <= length; j++) { swap((a+i), (a+j)); permute(a, i+1, length); swap((a+i), (a+j)); //backtrack } } } int main() { char a[] = "abcd"; int n = strlen(a); permute(a, 0, n-1); return 0; }

The output is

abcd acbd bacd bcad cbad cabd

The above program will print all permutation with repetition. The above program needs to be modified for permutation of a string without repetition.

Reference:

http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html

## Leave a Reply