write c program for all permutation of a string using backtracking.

Permutation means all possible re-arrangements of a 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. The previous blog post for permutation of a string is discussed at http://wikistack.com/write-a-c-program-for-printing-all-permutation-of-a-string/. This implementation is different.

permutation of a string using backtracking

c program for permutation of a string using backtracking

#include<iostream>
#include<string.h>
using namespace std;

void perm (int k, char *arr, char *arrp, bool * v, int len);

int main ()
{
  char arr[] = "abc"; // to be permuted
  char arrp[sizeof(arr)-1]; // helper array
  bool visited[sizeof(arr)-1]; // visited array

// make visited false initially
  memset (visited, 0, sizeof (arr));

  // call perm
  perm (0, arr, arrp, visited, sizeof (arr) - 1);

  return 0;
}

void perm (int k, char *arr, char *arrp, bool * v, int len)
{
  if (k == len) // if k is equal to len
    {
        // print arrp
        for (int i = 0; i < len; i++)
	    cout << arrp[i] << " ";
        cout << endl;
    }

  for (int i = 0; i < len; i++)
    {
        if (!v[i]) // if v[i] is not visited
	   {
	     v[i] = true; // make visited 
	     arrp[k] = arr[i]; // copy to arrp
	     perm (k + 1, arr, arrp, v, len); // call perm
	     v[i] = 0; // backtrack
	    }
    }
}

Ref:

https://en.wikipedia.org/wiki/Permutation



Related Contents to follow