String permutation not working

This is a discussion on String permutation not working within the C Programming forums, part of the General Programming Boards category; I have bee trying to work this out for a couple of hours now, I am getting nowhere and its ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    String permutation not working

    I have bee trying to work this out for a couple of hours now, I am getting nowhere and its annoying.

    Here is some working code to display string permutations in C++:
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    
    string swtch(string topermute, int x, int y)
    {
        string newstring = topermute;
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x]; //avoids temp variable
    	return newstring;
    }
    
    void permute(string topermute, int place)
    {
    	if(place == topermute.length() - 1)
    	{
        	cout<<topermute<<endl;
        }
        for(int nextchar = place; nextchar < topermute.length(); nextchar++)
    	{
    		permute(swtch(topermute, place, nextchar), place+1);
    	}
    }
    
    int main()
    {
        permute("love", 0);
    	system("PAUSE");
    }
    I tried to convert this to C. Here is what I got:
    Code:
    #include <stdio.h>
    #include <string.h>
    
    char *CharSwap(char *word, int x, int y)
    {
        char temp = word[x];
        word[x] = word[y];
        word[y] = temp;
    	return word;
    }
    
    void Permute(char *word, int pos)
    {
    	int len=strlen(word);
    	int next;
    	
        if(pos == len-1)
    		printf("%s\n", word);
    		
    	for(next=pos; next<len; next++)
    		Permute(CharSwap(word, pos, next), pos+1);
    }
    
    int main()
    {
        char word[]="love";
        Permute(word, 0);
        system("PAUSE");
    }
    If someone could please explain why the second version in C does not work correctly it would be much appreciated by me. Thanks.

  2. #2
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    In your C++ version, you are passing around copies of the string, so each call to Permute using CharSwap provides a fresh copy, whereas in the C version, you are using just a single copy ("word"), which is being altered every pass through Permute, and when the functions finally reach their base cases and terminate, the string being printed (word) will always be the version that was last edited by the last non-terminating call of Permute using CharSwap.

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Thanks for pointing that out @nthony, It seems obvious now I know. Anyway I got a working version now. Its a lot more code, but at least it works. Cheers.
    Code:
    #include <stdio.h>
    #include <string.h>
    
    struct perm
    {
        char mutate[20];
    };
    typedef struct perm perm; 
    
    void Permute(char *word, int pos, perm *p)
    {
    	int len=strlen(word);
    	int next;
        char temp; 
           
        //First time run: Allocate space, and copy word to first address
        if(pos == 0)
        {
            int permutations=1;   
            for(next=2; next<=len; next++)
                permutations*=next;
            p = malloc(permutations*10);// *10 to be safe for duplicates
            strcpy(p->mutate, word);
        }
        //Use 'word' as temp. Move to next address. Put copy to new address
        else
        {
            strcpy(word, p->mutate); 
            p++;                     
            strcpy(p->mutate, word); 
        }
            
        if(pos == len-1)
    		printf("%s\n", p->mutate);
    		
    	for(next=pos; next<len; next++)
        {
            temp = p->mutate[pos];
            p->mutate[pos] = p->mutate[next];
            p->mutate[next] = temp;    
            Permute(word, pos+1, p);      	
        }
        
        //When all recursions complete free allocated memory
        if(pos==0)free(p); 
    }
    
    int main()
    {
        char word[10]; 
        int len;
        printf("Enter a word up to 8 characters in length: ");
        fgets(word, 10, stdin); len=strlen(word)-1; word[len]='\0'; 
        Permute(word, 0, NULL);
        system("PAUSE");
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 10:03 PM
  2. Replies: 4
    Last Post: 03-03-2006, 01:11 AM
  3. can anyone see anything wrong with this code
    By occ0708 in forum C++ Programming
    Replies: 6
    Last Post: 12-07-2004, 11:47 AM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  5. Another overloading "<<" problem
    By alphaoide in forum C++ Programming
    Replies: 18
    Last Post: 09-30-2003, 10:32 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21