permutation of a string in c++

[varunrathi]

Can anybody help me with permutation in c++. say if the entered string is "stop" then there must be 24 (=4*3*2*1) different words made by the letters s,t,o,p. Similarly if the entered string is "abcde" then there will be 120 (=5*4*3*2*1) different words made using the letters a,b,c,d,e.
Please Help. It`s eating up my head.

[vegaseat]

The STL has a function next_permutation() which you can apply to a vector. This sample code is written for integers, it is your mission to apply your genius to make it work with characters! Report back your success to this illustrious forum!

// permutations of a three digit integer number
// Dev C++

#include <iostream>
#include <algorithm>   // next_permutation() via stl_algo.h
#include <vector>      // stl vector header
#include <iterator>    // ostream_iterator
#include <stdlib.h>    // system()

using namespace std;

int main()
{
  vector<int> iV;
  
  iV.push_back(0);
  iV.push_back(1);
  iV.push_back(2);

  // display original
  cout << "original number:\n";
  copy(iV.begin(),iV.end(),ostream_iterator<int>(cout,""));
  cout << endl;
  cout << "permutations:\n";
  // loop until all permutations are generated and displayed
  // does not display original number
  while (next_permutation(iV.begin(), iV.end())) 
  { 
    copy(iV.begin(),iV.end(),ostream_iterator<int>(cout,""));
    cout << endl;
  }
    
  system("PAUSE");	
  return 0;
}

[varunrathi]

Vegaseat, Thanks for your help and the trouble u took for me, but i am using turbo c++ and ur code was for dev c++.Turbo c++ does not provide the function u assisted. Thanks anyways. see if u can help me further with turbo/borland c++.

[vegaseat]

Any reasonably modern C++ compiler should give you access to the Standard Template Libraries!!!

If Borland Turbo C++ does not provide STL, you do yourself a favor by getting into a more updated version. You can always download the Dev C++ IDE, which uses the open source GCC/G++ compiler, for free at:

http://sourceforge.net/projects/dev-cpp/

I recommend it, it installs easily and it's a joy to code and compile with this system.

[varunrathi]

Thanks vegaseat for ur help again. Hope dev c++ will help me improve.
I actually wanted the logic to generate the permutations

[vegaseat]

Actually, the algorithm for the next_permutation() is in the header file called stl_algo.h

Once you installed DevCpp this header file should be in
..\include\C++\3.3.1\bits\

Other compilers may have different directories.

[Asif_NSU]

To vegaseat:
I appreciate ur effort to help out varunrathi. However, i think he wanted help with generating permutation(anagrams) of a given word, not to learn how to use STL. I believe if u had given him the pseudo code or the algorithm --that would have helped him more than anything. From ur code varunrathi will gain little or no knowledge as how to generate permutations.

To varunrathi,
U can check out this page, it uses recursion to generate pemutations. I believe after u go through this tutorial u will have a better understanding....

http://personal.vsnl.com/erwin/magic.htm

[vegaseat]

I guess we can all google! Here is in interesting way for character permutations. Check the permutation after the original.

// This program finds permutations using a recursive method
// modified Dev C++ from a wonderful article at:
// http://www.codeproject.com/cpp/cppperm1.asp

#include<iostream>
#include<cstring>

using namespace std;

void char_permutation(char str[],char append[])
{
  int length = strlen(str);
  if (length)
  {
    for(int i=0;i<length;++i)
    {
      char* str1 = new char[length+1];
      int cnt;
      int cnt2;
      for(cnt=0,cnt2=0; cnt<length; ++cnt,++cnt2)
      {
        if (cnt == i)
        {
          str1[cnt] = str[++cnt2];
          continue; 
        }
        else
          str1[cnt] = str[cnt2];
      }  
      str1[cnt] = '\0';
      
      int alength = strlen(append);
      char* append1 = new char [alength+2];
      strncpy(append1,append,alength);
      append1[alength] = str[i];
      append1[alength+1] = '\0';
      
      char_permutation(str1,append1);
      
      delete []str1;
      delete []append1; 
    } 
  }
  else
  {
    cout << append << endl; 
  }  
}


int main()
{
  char str[] = "BUSH";  // shows a little humor
  char append[] = "\0";  

  cout << "Original = " << str << endl;  
  char_permutation(str,append);
	cout << "Done ........" << endl;
	
	cin.get();  // wait
  return 0;
}

There is also code in the C code snippets section on DaniWeb. Read Dave's comments first, bottom of snippet.

[varunrathi]

To Vegaseat,
I Heartily Thank You For The Troubles U Took To Get The Code For Me. It`s Working Fine, But The Only Hitch Is In Understanding It B`coz It`s Written For Dev C++, But Then Also I Have Nearly Understood What I Have To Do And Will Be Able To Do It In Turbo C++.

[varunrathi]

To Asif_nsu,
I Am Grateful To U For The Link U Provided To Me. It Has Improved And Cleared My Concept Of Permutation. I Never Knew That Recursive Functions Are So Powerful. Thank U Very Much.

[varunrathi]

To Asif_nsu And Vegaseat
I Wanna Thank U Once Again B`coz The Link Provided By U Have Proved To Be Extremely Helpful And For The First Time I Was Able To Use Recursive Function So Efficiently And At Last I Was Able To Write The Code To Generate The Permutaion Of A Character String Given By The User. I Am So Happy After Doing This That I Can`t Express It B`coz I Have Trying This Program For A Long Time.
I Know For Sure That Recursive Functions Are Going To Improve My Skills To A Great Extent In Future.

[anjaly grace]

//This is a copy of another answer. It works for Turbo c++ 1.


#include<iostream.h>
#include<string.h>
#include<conio.h>

int count=0;
void permut(char stra1[],char append[])
   {
     int length = strlen(stra1);
     if (length)
      {
      for(int i=0;i<length;++i)
       {
       char* str2 = new char[length+1];
       int count1;
       int count2;
        for(count1=0,count2=0; count1<length; ++count1,++count2)
         {
          if (count1 == i)
             {
              str2[count1] = stra1[++count2];
              continue;
             }
          else
             str2[count1] = stra1[count2];
          }
       str2[count1] = '\0';

       int alength = strlen(append);
       char* append1 = new char [alength+2];
       strncpy(append1,append,alength);
       append1[alength] = stra1[i];
       append1[alength+1] = '\0';

        permut(str2,append1);
       delete []str2;
       delete []append1;
       }
      }

  else
   {
         count=count+1;
         cout << append << endl;
    }
}


void main()
{
clrscr();
cout<<"Enter a word";
char stra1[25];
cin>>stra1;
char append[] = "\0";

cout << "Original = " << stra1;
cout<<"\nPermutations\n";
permut(stra1,append);
cout<<"\nCount="<<count;
cout << "\nTerminating Program";
getch();
}

[minas1]

You can do it your self if you know some math :)

w o r d = 4 letters which aren't the same
= 4!

s h e e p = 5! / 2! (the 2 ee)

[iamthwee]

Sounds like another fail, I dare people not to help you.

[haroonjamia]

//This is a copy of another answer. It works for Turbo c++ 1.


#include<iostream.h>
#include<string.h>
#include<conio.h>

int count=0;
void permut(char stra1[],char append[])
   {
     int length = strlen(stra1);
     if (length)
      {
      for(int i=0;i<length;++i)
       {
       char* str2 = new char[length+1];
       int count1;
       int count2;
        for(count1=0,count2=0; count1<length; ++count1,++count2)
         {
          if (count1 == i)
             {
              str2[count1] = stra1[++count2];
              continue;
             }
          else
             str2[count1] = stra1[count2];
          }
       str2[count1] = '\0';

       int alength = strlen(append);
       char* append1 = new char [alength+2];
       strncpy(append1,append,alength);
       append1[alength] = stra1[i];
       append1[alength+1] = '\0';

        permut(str2,append1);
       delete []str2;
       delete []append1;
       }
      }

  else
   {
         count=count+1;
         cout << append << endl;
    }
}


void main()
{
clrscr();
cout<<"Enter a word";
char stra1[25];
cin>>stra1;
char append[] = "\0";

cout << "Original = " << stra1;
cout<<"\nPermutations\n";
permut(stra1,append);
cout<<"\nCount="<<count;
cout << "\nTerminating Program";
getch();
}

There is loophole in this program.
whom so ever who has created it, so smartly
have forgotten to do something very important in this program.
shit huge blunder

wanna know then ask me for loophole
[e-mail]

[haroonjamia]

//This is a copy of another answer. It works for Turbo c++ 1.


#include<iostream.h>
#include<string.h>
#include<conio.h>

int count=0;
void permut(char stra1[],char append[])
   {
     int length = strlen(stra1);
     if (length)
      {
      for(int i=0;i<length;++i)
       {
       char* str2 = new char[length+1];
       int count1;
       int count2;
        for(count1=0,count2=0; count1<length; ++count1,++count2)
         {
          if (count1 == i)
             {
              str2[count1] = stra1[++count2];
              continue;
             }
          else
             str2[count1] = stra1[count2];
          }
       str2[count1] = '\0';

       int alength = strlen(append);
       char* append1 = new char [alength+2];
       strncpy(append1,append,alength);
       append1[alength] = stra1[i];
       append1[alength+1] = '\0';

        permut(str2,append1);
       delete []str2;
       delete []append1;
       }
      }

  else
   {
         count=count+1;
         cout << append << endl;
    }
}


void main()
{
clrscr();
cout<<"Enter a word";
char stra1[25];
cin>>stra1;
char append[] = "\0";

cout << "Original = " << stra1;
cout<<"\nPermutations\n";
permut(stra1,append);
cout<<"\nCount="<<count;
cout << "\nTerminating Program";
getch();
}

There is loophole in this program.
whom so ever who has created it, so smartly
have forgotten to do something very important in this program.
shit huge blunder

wanna know then ask me for loophole
SNIP

[Nick Evan]

Sounds like another fail, I dare people not to help you.

Why on earth did you dig up this thread to post such a reply? You do realize that it's quite save to assume no-one was going to reply after a year of silence right?

There is loophole in this program.
whom so ever who has created it, so smartly
have forgotten to do something very important in this program.
shit huge blunder

wanna know then ask me

Why won't you just post it here? No-one is going to email you for this problem and risk getting spam in return :icon_wink:

[haroonjamia]

Why on earth did you dig up this thread to post such a reply? You do realize that it's quite save to assume no-one was going to reply after a year of silence right?

Why won't you just post it here? No-one is going to email you for this problem and risk getting spam in return :icon_wink:

In that permutation program
what it does is that when the input string is say "uuuu"
then its permutation should be 1 acording to math

4! / 4! = 1

but gives
Enter a word uuuu
Original = uuuu
Permutations
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu
uuuu

Count=24

what is this output

or if input string is dduu

it must give

4! / ( 2!*2! ) = 6 permutations only

why it gives 24 like a fool, repeating the strings as below
Enter a word dduu
Original = dduu
Permutations
dduu
dduu
dudu
duud
dudu
duud
dduu
dduu
dudu
duud
dudu
duud
uddu
udud
uddu
udud
uudd
uudd
uddu
udud
uddu
udud
uudd
uudd

Count=24

[Wader Astra]

Can anybody help me with permutation in c++. say if the entered string is "stop" then there must be 24 (=4*3*2*1) different words made by the letters s,t,o,p. Similarly if the entered string is "abcde" then there will be 120 (=5*4*3*2*1) different words made using the letters a,b,c,d,e.
Please Help. It`s eating up my head.

no a code for permutaion >>>please

[richieking]

Recursion and loop make our life easier. Thats the logic of programming.