recursive remove duplicates from a string

This is a discussion on recursive remove duplicates from a string within the C Programming forums, part of the General Programming Boards category; i need to build: void remove_duplicates(char string[], int index) which removes chars that already appeared in the string before. for ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    recursive remove duplicates from a string

    i need to build:
    void remove_duplicates(char string[], int index)

    which removes chars that already appeared in the string before.

    for example:
    "aatbacedbc" ==> "atbced"

    i am not allowed to use pointers , malloc , loops,external math functions.
    i am allowed to use external recursive function.

    i cant figure out an algorithm to do this.

    i tried this
    but its only a blind shot

    how to build it

    ??
    Code:
    void remove_duplicates(char string[], int index)
    {
    	char ch;
        if (string[index]=='\0')
        {
          return 1;
        }
        if(string[index]!=string[index+1])
    	{
          remove_duplicates( string,index+1);
    	}
    	else
    	{
    		return 0;
    	}
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You can use a recursive function to make a sort of infinite loop, which is probably the point since you can't use a loop otherwise:

    Code:
    #include <stdio.h>
    #include <string.h>
    
    char output[64]={'\0'};
    
    void recurse (char *string, int count, int len) {
    	static int i=-1, found=0; 
    	if (i==-1) {i++;recurse(string, 0, len); return;}
    	if (len==i) return;
    	if (output[count]==string[i]) { i++;
    		recurse(string,0,len);
    		return;}
    	if (count==found) {output[found]=string[i];
    		found++; i++;
    		recurse(string,0,len);
    		return;}
    	recurse(string,count+1,len);
    }
    
    int main (int argc, char *argv[]) {
    	int len;
    	if ((argc<2) || ((len=strlen(argv[1]))>63)) return 0;
    	recurse(argv[1],0,len);
    	printf("%s\n",output);	
    }
    Input: aaajddasweswffvadv
    Output: ajdswefv
    Last edited by MK27; 01-12-2009 at 03:13 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i cant add a length ass parameter
    only
    (char string[], int index)

    how to substitute it?

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    can i substitute
    Code:
     if (len==i) return;
    with
    Code:
     if (string[i]=='\0') return;
    and to remove the len parameter
    ??

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by transgalactic2 View Post
    i cant add a length ass parameter
    only
    (char string[], int index)

    how to substitute it?
    You could make len a global int, which would simplify the code.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by transgalactic2 View Post
    can i substitute

    Code:
     if (string[i]=='\0') return;
    I wouldn't do that unless you also make sure to add a \0 somewhere, since there are no string functions called so no auto line terminating...which suddenly makes me realize I got lucky because the output from that post wasn't null terminated! I will have to go back and change that...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    char string[] is a pointer, its just a non-standard way of writing char* string. If you cant use pointers, you are SOL, since there is no way to refernce the data pointed to by a pointer without actually using the pointer.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i tried to run it
    i cant use global variables

    i get an error because there is no array called output.


    Code:
    #include <stdio.h>
    #include <string.h>
    
    
     
    void recurse (char *string, int count, int len);
    int main() {
        char input[255];
        char input2[255];
        char result[510];
        int index,flag,ch;
        printf("enter the first string \n");
     for (index = 0; index < 254 && (ch = getchar()) != '\n' && ch >=0; ++index)
        {
            input[index] = ch;
        }
    
        input[index] = '\0';
    
          recurse (input, 0, index);
    
    return 0;
    }
    
    void recurse (char *string, int count, int len) {
    	static int i=-1, found=0; 
    	if (i==-1) {i++;recurse(string, 0, len); return;}
    	if (len==i) return;
    	if (output[count]==string[i]) { i++;
    		recurse(string,0,len);
    		return;}
    	if (count==found) {output[found]=string[i];
    		found++; i++;
    		recurse(string,0,len);
    		return;}
    	recurse(string,count+1,len);
    }

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by transgalactic2 View Post
    i cant use global variables
    Then you could either:
    • put strlen into the recurse function, or
    • look for the '\0' at the end of the string

    The 2nd option is much more efficient.

    To avoid the "output string", print the output from within recurse() one character at a time rather than putting it into output.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    how to replace this output[count] expression

    Code:
    #include <stdio.h>
    #include <string.h>
    
    
     
    void recurse (char *string, int count);
    int main() {
        char input[255];
        char input2[255];
        char result[510];
        int index,flag,ch;
        printf("enter the first string \n");
     for (index = 0; index < 254 && (ch = getchar()) != '\n' && ch >=0; ++index)
        {
            input[index] = ch;
        }
    
        input[index] = '\0';
    
          recurse (input, 0);
    
    return 0;
    }
    
    void recurse (char *string, int count) {
    	static int i=-1, found=0; 
    	if (i==-1) {i++;recurse(string, 0); return;}
    	if (string[i]=='\0') return;
    	if (output[count]==string[i]) { i++;  //how to replace this output[count] expression 
    		recurse(string,0);
    		return;}
    	if (count==found) {printf("%c",string[i]);
    		found++; i++;
    		recurse(string,0);
    		return;}
    	recurse(string,count+1);
    }

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    this program doesnt let me input a string
    it just say
    "press any key to continue"
    and exits
    ??

    Code:
    #include <stdio.h>
    #include <string.h>
    
    char output[64]={'\0'};
    
    void recurse (char *string, int count, int len) {
    	static int i=-1, found=0; 
    	if (i==-1) {i++;recurse(string, 0, len); return;}
    	if (len==i) return;
    	if (output[count]==string[i]) { i++;
    		recurse(string,0,len);
    		return;}
    	if (count==found) {output[found]=string[i];
    		found++; i++;
    		recurse(string,0,len);
    		return;}
    	recurse(string,count+1,len);
    }
    
    int main (int argc, char *argv[]) {
    	int len;
    	if ((argc<2) || ((len=strlen(argv[1]))>63)) return 0;
    	
    	recurse(argv[1],0,len);
    	printf("%s\n",output);	
    }

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    how to fix it

    where do i put a string in there?

  13. #13
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    it doesnt let me input

  14. #14
    Registered User TriTon's Avatar
    Join Date
    Dec 2008
    Posts
    5
    if you're not allowed to use pointers, why do you use them?

    before i'll try to write something, let me make sure i understand, your assignment is to use only pure recursive functions and nothing else?

  15. #15
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i am trying to get it running and then when ill get a working version

    ill change the pointers

    yes pure recurtion
    no pointers
    no malloc
    no global variable

    but external help functions are alowed
    Last edited by transgalactic2; 01-12-2009 at 07:50 AM.

Page 1 of 4 1234 LastLast
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, 05:05 AM
  2. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  3. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 01:56 PM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  5. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM

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