Algorithm to find all possible permutations of a string or array
How can I implement a generic algorithm which generates all possible permutations of a string or array elements ?
Anonymous Answered question
Here is another C program to achieve the same.
It uses a macro N which is defined as of length 9 initially.
#include <stdio.h> #include <string.h> #define N 9 /// 9 characters as of now // array which will hold the permuted combination char table[N]; void permute(int, int); void display_table(int); int permute_count = 0; int main() { printf("Please enter the string\n"); gets(table); printf("\n\n"); permute(1, strlen(table)); printf("Total number of permutations is = %d\n", permute_count); return 0; } void permute(int low, int high) { char temp, tab[N]; int j = 0, k = 0; if(low == high) display_table(high); else { for(j = 0; j < high; j++) tab[j] = table[j]; for(k = low; k <= high; k++) { permute(low + 1, high); if(k != high) { temp = tab[low - 1]; tab[low - 1] = tab[k]; tab[k] = temp; for(j = 0; j < high; j++) table[j] = tab[j]; } } } } void display_table(int num) { int i = 0; for(i = 0; i < num; i++) putchar(table[i]); permute_count++; printf("\n"); }
Algol Answered question
Below Javascript code does that in a nutshell:-
window.onload = init; // patch init function to window onload event /* init function to be called on window load */ function init() { console.log(permuteString('', 'abcd')); console.log(permuteArray('', ['William', 'Henry', 'Gates', 'Junior'])); } /* finds permutations of all characters of a string */ function permuteString(prefix, string) { var n = string.length; if (n === 0) { console.log(prefix); } else { for (var index = 0; index < n; index++) { permuteString(prefix.concat(string[index]), string.slice(0, index).concat(string.slice(index + 1, n))); } } return "Complete"; } /* same function slightly modified for an array with an extra space delimiter */ function permuteArray(prefix, string) { var n = string.length; if (n === 0) { console.log(prefix); } else { for (var index = 0; index < n; index++) { // Note:- space has been concatenated to distinguish/delimit between different array elements permuteArray(prefix.concat(string[index])+' ', string.slice(0, index).concat(string.slice(index + 1, n))); } } return "Complete"; }
goli202084 Changed status to publish