InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Write a program for printing all permutations of a given string. |
|
Answer» A permutation means re-arranging the ordered list(L) elements into a correspondence of one-to-one with the L itself. It is also known as an “order” or “arrangement NUMBER”. There will be N! permutation for a string with length n. For finding all permutations of a given string, the recursive algorithm will make use of backtracking which finds the permutation of numbers by swapping a single element per iteration. We are providing the “XYZ” string as an input in the below given example. It will produce 6 permutations for a given string. The permutation for a string “XYZ” are “XYZ”, “YXZ”, “ZYX”, “XZY”, “YZX”, “ZXY”. // C Program to print all permutations of a given string including duplicates#include <stdio.h>#include <string.h>// Function for swapping values at two pointers void swap(char *a, char *b) { char temp; temp = *a; *a = *b; *b = temp;}/* Function for printing permutations of a string. This function takesthree parameters: String, Starting index of the string, LAST index ofthe string. */void permute(char *a, int beg, int end){ int i; if (beg == end) printf("%s\n", a); else { for (i = beg; i <= end; i++) { swap((a+beg), (a+i)); permute(a, beg+1, end); //backtracking method swap((a+beg), (a+i)); } }}// Driver program for testing above defined functions int MAIN(){ char string[] = "XYZ"; int n = strlen(string); permute(string, 0, n-1); return 0;}Output: XYZXZYYXZYZXZYXZXY |
|