Question: I'm trying to create a program that prints permutations of a string (in lexicographical order) given a number of permutations but my program does not
I'm trying to create a program that prints permutations of a string (in lexicographical order) given a number of permutations but my program does not seem to be working correctly, I need some help in debugging. This program uses John trotter algorithm which is required for the assignment.
#include "csce310hw01pt02.h"
#include
#include
using namespace std;
bool LEFT_TO_RIGHT = true;
bool RIGHT_TO_LEFT = false;
//utility function to find the largest k element.
int getMobile(string word, bool direction[]) {
int k = 0;
for(int i = 0; i < word.length(); i++) {
//if direction of arrow is pointing to the left and an element is larger than last element and that element is larger than what k was last, k becomes that new larger element. Thus, we found largest k.
if(direction[word[i]] == RIGHT_TO_LEFT) {
if(word[i] > word[i-1] && word[i] > k) {
k = word[i];
}
}
//same idea with arrow pointing opposite direction
if(direction[word[i]] == LEFT_TO_RIGHT) {
if(word[i] > word[i+1] && word[i] > k) {
k = word[i];
}
}
}
return k;
}
//function to find position of k in the string
int mobilePosition(string word, int k) {
int r = 0;
for(int i = 0; i < word.length(); i++) {
if(word[i] == k) {
r = i;
}
}
return r;
}
void printPermutations(string word, int permutations) {
//store current direction
bool direction[word.length()];
for(int i = 0; i< word.length(); i++) {
cout << word[i];
}
cout << endl;
//set initial arrow direction from right to left
for(int i = 0; i < word.length(); i++) {
direction[i] = RIGHT_TO_LEFT;
}
for(int j = 1; j < permutations; j++) {
int k = getMobile(word, direction);
int positionK = mobilePosition(word, k);
if(direction[positionK] == RIGHT_TO_LEFT) {
swap(word[positionK], word[positionK - 1]);
swap(direction[positionK], direction[positionK - 1]);
} else if(direction[positionK] == LEFT_TO_RIGHT) {
swap(word[positionK + 1], word[positionK]);
swap(direction[positionK + 1], direction[positionK]);
}
// swapping elements based on the direction of arrow
for(int m = 0; m < word.length(); m++) {
if(word[m] > k) {
if(direction[word[m] - 1] == LEFT_TO_RIGHT) {
direction[word[m] - 1] = RIGHT_TO_LEFT;
} else if(direction[word[m] - 1] == RIGHT_TO_LEFT) {
direction[word[m] - 1] = LEFT_TO_RIGHT;
}
}
}
cout << word << endl;
}
}
int main( int argc , char* argv[] ){
int num;
cin >> num;
string word;
cin >> word;
try{
cout << "permutations" << endl;
printPermutations( word , num );
}
catch( exception e ){
cerr << "An error occurred." << endl;
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help