Problem in C++ Permutation(recursive) program

[ron_jay]

I have a serious problem which i am not being able to figure. This program finds all the permutations of a given string using recursion. The diagnostic outputs show that the values of the 'choice' and 'final' character arrays is not maintained at a position (I don't know why). Please help.

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

class Permutation
{
  private:
    static char s[20];
    int width,l;
  public: 
    void input();
    void compute();
    void recur(char choice[],char final[],int);
};
char Permutation::s[20];

void Permutation::input()                                 
{
  cout<<"Enter the string:";
  gets(s);
  cout<<"Places to arrange:";
  cin>>width;
};

void Permutation::compute()
{
  l=strlen(s);
  char s1[20];
  cout<<" \n              DIAGNOSTIC CHECK"<<endl; 
  cout<<"\n action \tchoice final \tp+1   i+1 c \n ";
  cout<<"______________________________________________\n \n";
  recur(s,s1,0);
}

void Permutation::recur(char choice[],char final[],int p)
{
   int i,j,chk,c=0;
   if(p==width){//base condition
     cout<<"OUT: "<<final;
	 cout<<endl;
	 return;
   }	  
   //setting choice variables
   for(i=0;i<l;i++){
   	   chk=0;							
       for(j=0;j<strlen(final);j++){
         
	     	 if(s[i]==final[j])
		       chk=1;
       }
	   if(chk==0){choice[c++]=s[i];}
   }
   choice[c]='\0';
    	  
  //traversing recursion	  
  for(i=0;i<c-1;i++){
                     
	final[p]=choice[i];
	final[p+1]='\0';cout<<"Beforein:\t "<<choice<<" -\t "<<final<<" -\t "<<p+1<<" -\t"<<i+1<<" "<<c<<endl<<endl;
	recur(choice,final,p+1);
	
	cout<<"Returned: \t"<<choice<<" - \t"<<final<<" - \t"<<p+1<<"-\t"<<i+1<<" "<<c<<endl<<endl;
  }	    
}

int main()
{
   Permutation arrange;
   arrange.input();
   arrange.compute();
   getch();
   return 0;
}

[ron_jay]

I would like to state my problems very clearly with the code I wrote.The crux of the problem is my inability to understand why the recursion procedure is not following the pattern it was supposed to:

class Permutation
{
  private:
    static char s[20];
    int width,l;
  public: 
    void input();
    void compute();
    void recur(char choice[],char final[],int);
};
char Permutation::s[20];

the above is the class definition, easy enough.

void Permutation::input()                                 
{
  cout<<"Enter the string:";
  gets(s);
  cout<<"Places to arrange:";
  cin>>width;
};

function to enter the values.

void Permutation::compute()
{
  l=strlen(s);
  char s1[20]; 
  recur(s,s1,0);
}

this is the function which calls the recursive function

RECURSIVE PART:

1)

void Permutation::recur(char choice[],char final[],int p)

choice[]: contains all possible letters which can take the position
eg. care - for the first position > c,a,r,e is stored as 'care' when the first is set to 'c' then for the second position is 'a,r,e' and so on..

final[]: stores the string to be printed..when all the spaces are filled , it is printed

p: holds the position where a character has to be inserted from the choice[] to final[]

2)

   int i,j,chk,c=0;
   if(p==width){//base condition
     cout<<"OUT: "<<final;
     cout<<endl;
     return;
   }  

this is the base conditon: if the width is reached it prints the string

3)

   //setting choice variables
   for(i=0;i<l;i++){>
       chk=0;                           
       for(j=0;j<strlen(final);j++){>

             if(s[i]==final[j])
               chk=1;
       }
       if(chk==0){choice[c++]=s[i];}
   }
   choice[c]='\0';

This is the part in the recursive function which finds all the possible characters which can be put into a space...it checks the initial string and compares it to final[] ...the choice[] are the ones which aren't present in final.

4)

  //traversing recursion      
  for(i=0;i<c-1;i++){>

    final[p]=choice[i];
    final[p+1]='\0';cout<<"Beforein:\t "<<choice<<" -\t "<<final<<" -\t "<<p+1<<" -\t"<<i+1<<" "<<c<<endl<<endl;
    recur(choice,final,p+1);

    cout<<"Returned: \t"<<choice<<" - \t"<<final<<" - \t"<<p+1<<"-\t"<<i+1<<" "<<c<<endl<<endl;
  }     
}

The chart of the recursive function is shown here:
http://i452.photobucket.com/albums/qq241/ronjay_2008/Misc/chart.jpg

the characters assigned for a position on final[] are taken from choice[]

5)

int main()
{
   Permutation arrange;
   arrange.input();
   arrange.compute();
   getch();
   return 0;
} 

Simple class construction

6) What I did not understand:

Since I wasn't getting the output, I added diagnostic check in the recursive function to check how the values were changing on each step. I knew that in the stack for each recursive iteration a separate instance of the array is created (choice[], final[] and p),but the output did not conform.

check this:
http://i452.photobucket.com/albums/qq241/ronjay_2008/Misc/OUTPUT.jpg

The part in yellow shows the state at an earlier iteration. Therefore, when 'recur' return to that state later, it should have printed the same values of choice[] and final[] which is not so. Only p,i and c are consistent. Whatever happened to choice[] and final[]? They should have retained their original values which according to the ouput it hasn't.

Maybe, there is minor error which i have overlooked. Please sort this.

If you want the .exe file its here:

http://www.filefactory.com/file/46f03a/n/output_permutation_exe

[Sky Diploma]

Well i would have loved to help , But i find myself stuck.

I get only 22 different 3 letter permutations with my recrusive function and i am still working on to see what went wrong?

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

class permutation
{
public:
    string inval;
    string output;
    int spaces,a;
    void input();
    int compute(int place);
    bool flar;

};

void permutation::input()
{
    cout<<"Welcome to The Permutation Calculater";
    cout<<"\nEnter a string (Without Spaces)";
    cin>>inval;
    cout<<"\nEnter the number of spaces to be filled ::";
    cin>>spaces;
    cout <<"Thank You, Computing......\n ";
    output="          ";
    a=1;
    compute(0);

};

int permutation::compute(int place)
{
    if (place==(spaces))
    {
        cout<<"Permutation:"<<a<<":"<<output<<"\n";
        a++;
        return 0;
    }
    else
    {

    for (int a=0; a<inval.size();a++)
    {
        for (int b=0;b<=(place);b++)
        {
            if(inval[a]!=output[b])
            {
                flar=true;
            }
            else
            {
                flar=false;
                break;
            }
        }
        if(flar==true)
        {
        output[place]=inval[a];
        compute(place+1);
        }
    }

     }
};

int main()
{
permutation test;
test.input();
}

I am missing some permutations in the middle and i dont know why.

[ron_jay]

What i actually want to know is how to preserve the state of an array at each iterative step in a recursive function. Because the way I have defined that array it will be referenced back to the original one. So I need to know how the state of the array at each depth?

[Sky Diploma]

Preserve the state of the array?, I am sorry but i donot seem to understand.

[ron_jay]

suppose I have a an array a[5]={1,2,3,4,5};

func(int b[])
{
   
   if(b[0]<6){
    return;
   }
   else
  {
     for(int i=0;i<5;i++)
         b[i]+=1;
     func(b);
     // at this point A
  }
}

so when the array has been reached the base condition i.e. 5,6,7,8,9,10
and starts to return back to the function that called it, the value of b[] remains what it had been before going into the function. Unfortunately, we can't pass arrays that way as only the pointer to that array is passed;above example is flawed. So I wanted to know how to implement this design using arrays?

[VernonDozier]

suppose I have a an array a[5]={1,2,3,4,5};

func(int b[])
{
   
   if(b[0]<6){
    return;
   }
   else
  {
     for(int i=0;i<5;i++)
         b[i]+=1;
     func(b);
     // at this point A
  }
}

so when the array has been reached the base condition i.e. 5,6,7,8,9,10
and starts to return back to the function that called it, the value of b[] remains what it had been before going into the function. Unfortunately, we can't pass arrays that way as only the pointer to that array is passed;above example is flawed. So I wanted to know how to implement this design using arrays?

I assume you simply forgot to put the word void in front of func . The above function will return immediately when passed {1, 2, 3, 4, 5}, so this line doesn't make sense to me:

so when the array has been reached the base condition i.e. 5,6,7,8,9,10

I don't know what the above line means with respect to your example {1, 2, 3, 4, 5}. func will return immediately since the base condition is immediately fulfilled. b[0] will never get to 5, 6, 7, etc.. Is this the whole array or b[0]?

5,6,7,8,9,10

This has six numbers; the array has 5 elements.

if(b[0]<6){
    return;
   }

I'm confused by what you are trying to do here. You are simply passing an array to a function that returns immediately.

[ron_jay]

My bad.

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

void func(int b[5]);
int l=1;

int main()
{

int a[5]={1,2,3,4,5};
func(a);
getch();
return 0;
}

void func(int b[5])
{
   
   if(l==5){
    return;
   }
   else{
     l++;
     for(int i=0;i<5;i++){//incrementing
         b[i]+=1;
     }
     cout<<"entering "<<l<<endl;
     for(int i=0;i<5;i++)//printing
       cout<<b[i]<<" ";
     cout<<endl;
     
     func(b);//recursive call
     // at this point A
     cout<<"return "<<l<<endl;
     for(int i=0;i<5;i++)
       cout<<b[i]<<" ";
     cout<<endl;
  }
}

Ok what my point is that when the array a{1, 2, 3, 4, 5} starts returning I would want the initial values that were prevalent on entering to be retained which is not the case here. How could I do that?

[Sky Diploma]

Well then you can try copying an array into a different array and then sending it as an argument to the function.

That way the increments are in another array And your array is still safe.

for example.

int main()
{

int a[5]={1,2,3,4,5};//Initial variable doesnt change
int b[5];//This gets changed after func(b)
for (i=0;i<5;i++)
{
b[i]=a[i];//Copying Array.
}
func(b);
getch();
return 0;
}

would do the trick i suppose.