Write a c program to print all permutations of a given string. Permutation means all possible re-arrangements of collection of objects, where the order is important. for example {a,b,c} can be arranged like {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a}. If the order does not important, it is a Combination.

There are various solution of this problem:

(1) Using STL std::next_permutation

#include <iostream>
#include <algorithm>
using namespace std;

int main ()
{
  char mystr[] = "abc";
  sort (mystr, mystr + 3);
  do
    {
      cout << mystr[0] << ' ' << mystr[1] << ' ' << mystr[2] << '\n';
    }
  while (next_permutation (mystr, mystr + 3));
  return 0;
}

The output:

a b c
a c b
b a c
b c a
c a b
c b a

(2) C code for permutation of string using recursive backtracking

Write a c program to print all permutations of a given string

#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[] = "abc";
    int n = strlen(a);
    permute(a, 0, n-1);
    return 0;
}

Ref: http://rosettacode.org/wiki/Permutations
http://stackoverflow.com



Related Contents to follow