Algorithm to find all possible permutations of a string or array

9.46K viewsProgramming
0

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

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

Answered question
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
Write your answer.

Categories