String permutations help

This is a discussion on String permutations help within the C Programming forums, part of the General Programming Boards category; I'm pretty new to c, so please excuse the basic question. I'm trying to make a program for string permutations, ...

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    11

    String permutations help

    I'm pretty new to c, so please excuse the basic question. I'm trying to make a program for string permutations, I couldint do it, so I looked at the solution at http://www.cprogramming.com/challenges/permutesol.html . Now even after using this code, and trying to change it to c (from c++), it still doesnt work Here is my code, what could be the problem?

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    void switch(char topermute[], int x, int y);
    void permute(char topermute[], int place);
    
    int main(int argc, char* argv[])
    {
    	if(argc!=2)
    	{
    		printf("Usage: ./permute string");
    	}
    	else
    	{
    		permute(argv[1], 0);
    	}
    	return 0;
    }
    
    void switch(char topermute[], int x, int y)
    {
    	char newstring[] = topermute[];
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x];
    	return newstring;
    }
    
    void permute(char topermute[], int place)
    {
    	if(place == strlen(topermute) -1)
    	{
    		printf("%s", topermute);
    	}
    	for(int nextchar = place; nextchar < strlen(topermute); nextchar++)
    	{
    		permute(switch(topermute, place, nextchar),place+1);
    	}
    }

  2. #2
    Registered User loopy's Avatar
    Join Date
    Mar 2002
    Posts
    172
    Code:
    void switch(char topermute[], int x, int y)
    {
    	char newstring[] = topermute[];
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x];
    	return newstring;
    }
    I don't think you can declaire a array of indeterment size within a function....

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    char *swich(char topermute[], int x, int y);
    void permute(char topermute[], int place);
    
    int main(int argc, char* argv[])
    {
    	if(argc!=2)
    	{
    		printf("Usage: ./permute string");
    	}
    	else
    	{
    		permute(argv[1], 0);
    	}
    	return 0;
    }
    
    char *swich(char *topermute, int x, int y)
    {
    	char *newstring;
            newstring = (char *) malloc (sizeof(*topermute));
            topermute = newstring; 
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x];
    	return topermute;
    }
    
    void permute(char topermute[], int place)
    {
    	int nextchar;
    	if(place == strlen(topermute) -1)
    	{
    		printf("%s", topermute);
    	}
    	nextchar = place;
    	while (nextchar < strlen(topermute))
    	{
    		permute(swich(topermute, place, nextchar),place+1);
    		nextchar++;
    	}
    }
    'switch' has special meaning, as for a "switch case".
    I wasnt able to find out why the for loop was giving errors.

    Hope that helps! : )
    WorkStation(new, a month ago):

    Sony Vaio i686 Desktop
    2.60 GIGhz Intel Pentium 4(HT)
    512Mb DDR RAM
    800MHz Front Side Bus!
    120 GIG IDE HardDrive
    Matrox G400 Dual-Head
    Linux kernel 2.6.3
    Modified Slackware 9.1
    GCC/GDB

    Multi-mon
    Simultaneous Multiple Processes

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    There are some problems with
    Code:
    char *swich(char *topermute, int x, int y)
    {
    	char *newstring;
            newstring = (char *) malloc (sizeof(*topermute));
            topermute = newstring; 
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x];
    	return topermute;
    }

    First: the size of array newstring should be strlen(topermute)+1, so that it can hold all its characters and also the terminating '\0'.

    (Note that sizeof(*topermute) is the size of a char.)

    Second: Copy topermute into newstring.

    Third: perform the character switch in newstring.

    Fourth: return the pointer to the permuted string.

    so, it could be something like:

    Code:
    char *swich(char *topermute, int x, int y)
    {
    	char *newstring;
            newstring = (char *) malloc (strlen(topermute)+1);
            strcpy(newstring, topermute);
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x];
    	return newstring;
    }
    Now, this function is called many times, and allocates new storage every time. It is your responsibility to deallocate all memory before your program exits. So, function permute() should free() the memory after the call to swich().

    Something like this should work:

    Code:
    void permute(char *topermute, int place)
    {
      int nextchar;
      char *switched_string;
    
      if(place == strlen(topermute) -1)
      {
        printf("%s\n", topermute);
      }
      for(nextchar = place; nextchar < strlen(topermute); nextchar++)
      {
        switched_string = swich(topermute, place, nextchar);
        permute(switched_string, place+1);
        free(switched_string);
      }
    }
    Dave

  4. #4
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by loopy
    I wasnt able to find out why the for loop was giving errors.
    Some C compilers still complain if you don't put all variable declarations and initialization at the beginning of the function, so the original for loop statement:

    Code:
     for(int nextchar = place; nextchar < strlen(topermute); nextchar++)
    could give problems.

    I just declared nextchar at the beginning, to show that for part would work OK once we get beyond compiler quirks.

    I would probably write it a little differently (to keep from calling strlen() every time), but this way works, and elegance is meaningless unless and until a basic understanding is in place.


    Dave
    Last edited by Dave Evans; 05-15-2004 at 01:20 PM.

  5. #5
    Registered User loopy's Avatar
    Join Date
    Mar 2002
    Posts
    172
    I have the program bookmarked, I want to try to write my own. ; )
    WorkStation(new, a month ago):

    Sony Vaio i686 Desktop
    2.60 GIGhz Intel Pentium 4(HT)
    512Mb DDR RAM
    800MHz Front Side Bus!
    120 GIG IDE HardDrive
    Matrox G400 Dual-Head
    Linux kernel 2.6.3
    Modified Slackware 9.1
    GCC/GDB

    Multi-mon
    Simultaneous Multiple Processes

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. char Handling, probably typical newbie stuff
    By Neolyth in forum C Programming
    Replies: 16
    Last Post: 06-21-2009, 04:05 AM
  2. Inheritance Hierarchy for a Package class
    By twickre in forum C++ Programming
    Replies: 7
    Last Post: 12-08-2007, 03:13 PM
  3. RicBot
    By John_ in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2006, 06:52 PM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 02:23 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM

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