Programming Forums > Application Development > C++

Mcoy · Mar 14th, 2006, 7:13 PM

Im back with another char problem. :mad:
I wrote a program that takes a string that the user inputs in a console, and finds all the permutations for it. The thinking is if I move one letter from the end of the string down through to the begining, printing the new word each time, starting over with the next letter at end of the string, until I reach the original word again, I should have great success! ->

The word goes into a string called 'word'. Then all the letters go into a char array for easy manipulation. I assign the char array (with two values switched) to a string called permutation. Keep doing this until permutation == word.

The problem is that permutation never equals word... Given the example word = "abc" , permutation will end up with the 'c' being '1/2'. I dont really know I to use chars properly I guess, but I can't figure this one out:

(Toggle Plain Text)

#include <iostream>
#include <string>

using namespace std;

int main() {
    string word;
    string permutation;
    char* pchar;
    
    cout << "Enter word for permutationalization!\n\n";
    cin >> word;
    
    pchar = new char[word.length()];
    
    for(int i = 0; i <(word.length()); i++){
            *(pchar + i) = word[i];
            cout << *(pchar + i);
            }
    
    
    int counter(0);
    do{
                        
            if(counter==(word.length())){
                                       counter=0;
                                       }
            
            int temp1((word.length())-counter);
            int temp2(temp1 - 1);
            char box1(*(pchar+temp1));
            char box2(*(pchar+temp2));
            *(pchar+temp2) = box1;
            *(pchar+temp1) = box2;
           
            for(int i=0; i < (word.length()); i++){
                    permutation += *(pchar + i);
                    cout << permutation << endl;
                    }
            
            counter++;
                
}while(permutation!=word);
    
    
    
    cin >> word;
    return 0;
}

I know there is another, easier way using recursion, but I only thought of it after I wrote this code, and I want to find out what is wrong with it.

DaWei · Mar 14th, 2006, 7:21 PM

Maybe this breaks your code: permutationalization. It broke my dictionary.

Seriously, your question isn't quite clear enough, I don't understand this: 'c' being '1/2'. What does that mean? Do you have a debugger? Have you tried sprinkling variable output statements throughout the code, if not? Information is key to debugging and also highlights algorithmic faults.

Mcoy · Mar 14th, 2006, 7:35 PM

(Toggle Plain Text)

for(int i=0; i < (word.length()); i++){
                    permutation += *(pchar + i);
                    cout << permutation << endl;
                    }

This loop asigns the new values to the string 'permutation'. To test the value of permutation I put that cout statement underneath. Just before the loop finishes 'permutation' couts "ab1/2"

...Oh wait I just found a bug( arn't these forums great! )... I forgot to reset permutation each time through the do-while loop. (I honestly did use a debugger for quite some time, I dont know how that one got by :o ).

Still doesn't work though, random spaces appear now when I output 'permutation' (sample output):

(Toggle Plain Text)

abc
abca
ab 
ab
a
a
a b

 a

  a
.
.
.
c a
.
.
.
abc

DaWei · Mar 14th, 2006, 8:06 PM

Personally, I suggest you rethink the problem and redesign. One way. No warranty (there was, but it expired this morning, early, while I wasn't shaving).

(Toggle Plain Text)

#include <iostream>
#include <string>

using namespace std;

int main (int argc, char *argv [])
{
    string theThangy = "abcde";
    // The algorithm seems to presume that all characters in
    // the target are unique.  We'll go with that.
    // Why decide to end when the result equals the original?
    // That requires a comparison, which, in this case is a waste of time.
    // Part one:  move the final character to successively lower positions
    // until it reaches the front.
    // Part two:  do Part one for each character in the string.  Done.

    // This is Part Two
    for (int i = 0; i < theThangy.size (); i++)
    {
        // This is Part One
        unsigned charPos = theThangy.size () - 1;
        char temp;
        while (charPos > 0)
        {
            temp = theThangy [charPos];
            theThangy [charPos] = theThangy [charPos - 1];
            theThangy [charPos - 1] = temp;
            cout << theThangy << endl;
            charPos--;
        }
    }

    cout << "Press ENTER to terminate program" << endl;    
    cin.get ();
    return 0;
}

Quote:

Originally Posted by Output

abced
abecd
aebcd
eabcd
eabdc
eadbc
edabc
deabc
deacb
decab
dceab
cdeab
cdeba
cdbea
cbdea
bcdea
bcdae
bcade
bacde
abcde
Press ENTER to terminate program

The Dark · Mar 14th, 2006, 9:24 PM

In your original code:

(Toggle Plain Text)

            int temp1((word.length())-counter);
            int temp2(temp1 - 1);
            char box1(*(pchar+temp1));
            char box2(*(pchar+temp2));

If counter is zero, then this will swap the last character in the pchar array with the one that is one past the last character in the pchar array (i.e. out of bounds). You would need to stick a -1 in there somewhere.

One other (major) problem is that this algorithm doesn't find all permutations. e.g. from Dawei's output, there is no "adbce". A recursive algorithm could be used here. e.g.:

(Toggle Plain Text)

#include <iostream>
#include <string>

using namespace std;

void printPermutations(string theThangy, int startPos)
{
  if (startPos == theThangy.size())
  {
    cout << theThangy << endl;
  }
  else
  {
    // Recurse down without swapping this char
    printPermutations(theThangy, startPos+1);
    // Recurse down swapping this char with each other one in the string
    for (int i = startPos + 1; i < theThangy.size (); i++)
    {
      char temp = theThangy [i];
      theThangy [i] = theThangy [startPos];
      theThangy [startPos] = temp;
      printPermutations(theThangy, startPos+1);
    }
  }
}

int main (int argc, char *argv [])
{
    string theThangy = "abcde";

    printPermutations(theThangy, 0);

    cout << "Press ENTER to terminate program" << endl;    
    cin.get ();
    return 0;
}

Note that this recursion has a string copy at each level, so it is not that efficient either in memory or cpu.

PS. That is the most times i have ever typed theThangy!

Cache · Mar 15th, 2006, 3:22 AM

Unless this is just some kind of exercise, you might as well use the tools C++ already provides.

(Error checking omitted)

(Toggle Plain Text)

#include <algorithm>
#include <iostream>
#include <string>

int main(int argc, char *argv[])
{
	std::string strWord;
	std::cin >> strWord;
	
	sort( strWord.begin(), strWord.end() );
	while ( next_permutation(strWord.begin(), strWord.end()) )
	{
		std::cout << strWord << "\n";
	}
	
	return 0;
}

Mar 14th, 2006, 7:13 PM	#1
Mcoy Newbie Join Date: Mar 2006 Posts: 20 Rep Power: 0	Permutation Im back with another char problem. :mad: I wrote a program that takes a string that the user inputs in a console, and finds all the permutations for it. The thinking is if I move one letter from the end of the string down through to the begining, printing the new word each time, starting over with the next letter at end of the string, until I reach the original word again, I should have great success! -> The word goes into a string called 'word'. Then all the letters go into a char array for easy manipulation. I assign the char array (with two values switched) to a string called permutation. Keep doing this until permutation == word. The problem is that permutation never equals word... Given the example word = "abc" , permutation will end up with the 'c' being '1/2'. I dont really know I to use chars properly I guess, but I can't figure this one out: (Toggle Plain Text) #include <iostream> #include <string> using namespace std; int main() { string word; string permutation; char* pchar; cout << "Enter word for permutationalization!\n\n"; cin >> word; pchar = new char[word.length()]; for(int i = 0; i <(word.length()); i++){ (pchar + i) = word[i]; cout << (pchar + i); } int counter(0); do{ if(counter==(word.length())){ counter=0; } int temp1((word.length())-counter); int temp2(temp1 - 1); char box1((pchar+temp1)); char box2((pchar+temp2)); (pchar+temp2) = box1; (pchar+temp1) = box2; for(int i=0; i < (word.length()); i++){ permutation += (pchar + i); cout << permutation << endl; } counter++; }while(permutation!=word); cin >> word; return 0; } #include <iostream> #include <string> using namespace std; int main() { string word; string permutation; char pchar; cout << "Enter word for permutationalization!\n\n"; cin >> word; pchar = new char[word.length()]; for(int i = 0; i <(word.length()); i++){ (pchar + i) = word[i]; cout << (pchar + i); } int counter(0); do{ if(counter==(word.length())){ counter=0; } int temp1((word.length())-counter); int temp2(temp1 - 1); char box1((pchar+temp1)); char box2((pchar+temp2)); (pchar+temp2) = box1; (pchar+temp1) = box2; for(int i=0; i < (word.length()); i++){ permutation += *(pchar + i); cout << permutation << endl; } counter++; }while(permutation!=word); cin >> word; return 0; } I know there is another, easier way using recursion, but I only thought of it after I wrote this code, and I want to find out what is wrong with it.

Mar 14th, 2006, 7:21 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Maybe this breaks your code: permutationalization. It broke my dictionary. Seriously, your question isn't quite clear enough, I don't understand this: 'c' being '1/2'. What does that mean? Do you have a debugger? Have you tried sprinkling variable output statements throughout the code, if not? Information is key to debugging and also highlights algorithmic faults. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Mar 14th, 2006, 7:35 PM	#3
Mcoy Newbie Join Date: Mar 2006 Posts: 20 Rep Power: 0	(Toggle Plain Text) for(int i=0; i < (word.length()); i++){ permutation += (pchar + i); cout << permutation << endl; } for(int i=0; i < (word.length()); i++){ permutation += (pchar + i); cout << permutation << endl; } This loop asigns the new values to the string 'permutation'. To test the value of permutation I put that cout statement underneath. Just before the loop finishes 'permutation' couts "ab1/2" ...Oh wait I just found a bug( arn't these forums great! )... I forgot to reset permutation each time through the do-while loop. (I honestly did use a debugger for quite some time, I dont know how that one got by :o ). Still doesn't work though, random spaces appear now when I output 'permutation' (sample output): (Toggle Plain Text) abc abca ab ab a a a b a a . . . c a . . . abc abc abca ab ab a a a b a a . . . c a . . . abc

Mar 14th, 2006, 9:24 PM	#5
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	In your original code: (Toggle Plain Text) int temp1((word.length())-counter); int temp2(temp1 - 1); char box1((pchar+temp1)); char box2((pchar+temp2)); int temp1((word.length())-counter); int temp2(temp1 - 1); char box1((pchar+temp1)); char box2((pchar+temp2)); If counter is zero, then this will swap the last character in the pchar array with the one that is one past the last character in the pchar array (i.e. out of bounds). You would need to stick a -1 in there somewhere. One other (major) problem is that this algorithm doesn't find all permutations. e.g. from Dawei's output, there is no "adbce". A recursive algorithm could be used here. e.g.: (Toggle Plain Text) #include <iostream> #include <string> using namespace std; void printPermutations(string theThangy, int startPos) { if (startPos == theThangy.size()) { cout << theThangy << endl; } else { // Recurse down without swapping this char printPermutations(theThangy, startPos+1); // Recurse down swapping this char with each other one in the string for (int i = startPos + 1; i < theThangy.size (); i++) { char temp = theThangy [i]; theThangy [i] = theThangy [startPos]; theThangy [startPos] = temp; printPermutations(theThangy, startPos+1); } } } int main (int argc, char argv []) { string theThangy = "abcde"; printPermutations(theThangy, 0); cout << "Press ENTER to terminate program" << endl; cin.get (); return 0; } #include <iostream> #include <string> using namespace std; void printPermutations(string theThangy, int startPos) { if (startPos == theThangy.size()) { cout << theThangy << endl; } else { // Recurse down without swapping this char printPermutations(theThangy, startPos+1); // Recurse down swapping this char with each other one in the string for (int i = startPos + 1; i < theThangy.size (); i++) { char temp = theThangy [i]; theThangy [i] = theThangy [startPos]; theThangy [startPos] = temp; printPermutations(theThangy, startPos+1); } } } int main (int argc, char argv []) { string theThangy = "abcde"; printPermutations(theThangy, 0); cout << "Press ENTER to terminate program" << endl; cin.get (); return 0; } Note that this recursion has a string copy at each level, so it is not that efficient either in memory or cpu. PS. That is the most times i have ever typed theThangy!

Mar 15th, 2006, 3:22 AM	#6
Cache Hobbyist Join Date: Sep 2005 Posts: 261 Rep Power: 4	Unless this is just some kind of exercise, you might as well use the tools C++ already provides. (Error checking omitted) (Toggle Plain Text) #include <algorithm> #include <iostream> #include <string> int main(int argc, char argv[]) { std::string strWord; std::cin >> strWord; sort( strWord.begin(), strWord.end() ); while ( next_permutation(strWord.begin(), strWord.end()) ) { std::cout << strWord << "\n"; } return 0; } #include <algorithm> #include <iostream> #include <string> int main(int argc, char argv[]) { std::string strWord; std::cin >> strWord; sort( strWord.begin(), strWord.end() ); while ( next_permutation(strWord.begin(), strWord.end()) ) { std::cout << strWord << "\n"; } return 0; }

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode