Update the permutation algorithm from the text to generate the correct list of p

Question

Update the permutation algorithm from the text to generate the correct list of permutations even if the string contains repealed letters. For example, if you call List Permutations on the string "AABB", your program should not generate as many permutations as it does for the string "ABCD" because some of the strings generated by the standard algorithm would be indistinguishable from others. Your program should instead generate the following six: ABBA ABAB ABBA BAAB BABA BBAA Write a new implementation of List Permutations that works correctly even if the string contains duplicated letters. In writing this implementation. you should not merely keep a list of permutations that have already be encountered and avoid generating duplicates. Instead, you should think carefully about the recursive structure of the problem and find a way to avoid generating the duplicates in the first place. You may assume the string contains only upper ease sellers from A to Z.

Explanation / Answer

#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<<"               DIAGNOSTIC CHECK"<<endl;
cout<<" action choice final p+1   i+1 c ";
cout<<"______________________________________________ ";
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]='';
      
//traversing recursion  
for(i=0;i<c-1;i++){
                    
final[p]=choice[i];
final[p+1]='';cout<<"Beforein: "<<choice<<" - "<<final<<" - "<<p+1<<" - "<<i+1<<" "<<c<<endl<<endl;
recur(choice,final,p+1);

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

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

OR

#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] = '';

int alength = strlen(append);

char* append1 = new char [alength+2];

strncpy(append1,append,alength);

append1[alength] = str[i];

append1[alength+1] = '';

char_permutation(str1,append1);

delete []str1;

delete []append1;

}

}

else

{

cout << append << endl;

}

}

int main()

{

char str[] = "BUSH"; // shows a little humor

char append[] = "";

cout << "Original = " << str << endl;

char_permutation(str,append);

cout << "Done ........" << endl;

cin.get(); // wait

return 0;

}

OR

#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: ";

copy(iV.begin(),iV.end(),ostream_iterator<int>(cout,""));

cout << endl;

cout << "permutations: ";

// 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;

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.