# Algorithm to find all possible permutations of a string or array

8.02K views
0

How can I implement a generic algorithm which generates all possible permutations of a string or array elements ?

0

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()
{
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");
}

0

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";
}

Changed status to publish