Thread: recursive remove duplicates from a string

Oh transgalactic2!

Code:

#include <stdio.h>

void recurse (char *string, int count) {
	static int i=0, found=0;
	static char output[128]={'\0'};            // all the printable characters and then some
	
	if (output[count]==string[i]) { i++;
		recurse(string,0);
		return;}
	if (count==found) {output[found]=string[i];
		found++; i++;
		recurse(string,0);
		return;}
        if (string[i]=='\0') {puts(output);return;}
	recurse(string,count+1);
}

int main (int argc, char *argv[]) {
	if (argc<2) return 0;
	recurse(argv[1],0);
        return 0;
}

If you cannot use a global but you can use a recursive function, you must pass the *string. Otherwise the exercise would say not to use a function either, which would make it either impossible or extremely tedious.

Originally Posted by abachler

char string[] is a pointer, its just a non-standard way of writing char* string.

Perhaps "uncommon" would be a better term, since the syntax certainly is standard. Of course, the statement only holds true in this case because this is a parameter.

Originally Posted by transgalactic2

but external help functions are alowed

Wonderful. The way that I would implement it (and have implemented it) would be to write two helper functions:

Code:

/* Returns 0 if index is negative.
 * Returns 1 if any character from positions 0 to index matches ch
 */
int has_duplicate(char string[], int index, char ch);

/* Copies the substring from positions index + 1 to the end
 * to positions index to the end - 1. For example, given the string "abcde",
 * overwrite(string, 2) will result in string becoming "abde".
 */
void overwrite(char string[], int index);

Can you understand my idea in implementing these two helper functions?

EDIT:

Originally Posted by MK27

To avoid the "output string", print the output from within recurse() one character at a time rather than putting it into output.

Since remove_duplicates() is supposed to remove duplicates, not print a string without duplicates, that would be the wrong approach. Although it is not stated in the requirements, it is reasonable to expect that this function should be reusable, so static variables are likely to be the wrong approach as well.

Originally Posted by transgalactic2

c(19) : warning C4101: 'len' : unreferenced local variable

That's because I left int len in by accident (now it's gone). You have to enter the input string on the command line, eg.

Code:

./a.out  aaajddasweswffvadv
ajdswefv

Originally Posted by transgalactic2

in the overwrite function for the given example
you want it to copy from index+1 till end ==>"de"
to the places of "abcd"

Nope. Copy "de" (including the '\0') to "cd".

The idea is that suppose you have this string: aat
You want to make it: at
When you discover that the char at index 1 is a duplicate, you then "shift" the string left by one place. In this case this means that the 't' overwrites the second 'a', and the '\0' overwrites the 't'.

Originally Posted by transgalactic2

i tried it that command prompt way
it worked
but i cant get an input in that way
i have to input the string directly from the VS

Just change main() to use fgets() and a string of some maximum size instead of a command line argument. That said, I pointed out that MK27's implementation is fatally flawed since it does not actually remove duplicates from the string argument but prints a version of the string without duplicates instead, and a lesser flaw is that it can only be used once.

Originally Posted by laserlight

Just change main() to use fgets() That said, I pointed out that MK27's implementation is fatally flawed since it does not actually remove duplicates from the string argument but prints a version of the string without duplicates instead

Since you could always just copy the one into the other this seems a flawed criticism
B/T/W It seemed to me earlier that the OP can only used one string and one integer in the function parameters.

Originally Posted by MK27

Since you could always just copy the one into the other this seems a flawed criticism

That is true. I must admit that I was rather upset at the use of static variables here, and that clouded my thinking. It seems wrong to be teaching transgalactic2 to write a function that can be used once only, just for the sake of solving an assignment. If that really is the "model answer", then the assignment is wrong.

Originally Posted by MK27

B/T/W It seemed to me earlier that the OP can only used one string and one integer in the function parameters.

Only for remove_duplicates(), it seems, since transgalactic2 neglected to correct me on that point. Incidentally, why did you rename the remove_duplicates() function to "recurse"? That seems as bad a name as "do_something".

EDIT:
On second thought, it would be possible to reuse the function by resetting the static variables after copying over. In that case I would be satisfied that the solution is reasonable to use, even though its implementation would not be satisfactory.

this is the external functions:

i wrote the over write function so it writes the next current function to the previous place.
if "baac\0"=> "bac\0"
am i correct?

how to write the main remove_duplicates function??

Code:

#include <stdio.h>
void overwrite(char string[], int index);
int has_duplicate(char string[], int index, char ch);


int main()
{
   return 0;
}

int has_duplicate(char string[], int index, char ch)
{
    int count=-1;
	int check;
	if (string[index]=='\0')
	{
           if (count<0)
            {
               return 0;
            }
             else
             {
                return 1;
             }
	}
    if (ch==string[index])
    {
      count++;
    }
	
   check=has_duplicate(string,index+1,ch);
}//end func


void overwrite(char string[], int index)
{
     string[index-1]=string[index];
     if( string[index]!='\0')
	 {
	     overwrite(string,index+1);
	 }
	 if ( string[index]=='\0')
	 {
      string[index-1]=string[index];
	 }
}

Originally Posted by transgalactic2

i wrote the over write function so it writes the next current function to the previous place.
am i correct?

Nope. Instead of copying the current character to the previous character, copy the next character to the current character, if the current character is not '\0'. After copying, call overwrite() for the next character(). The base case is when the current character is '\0', in which you do nothing and return.

Your has_duplicate() function is also flawed. What I suggest is to check backwards. That is, you check if the current character is equal to the given character ch. If it is, return 1, else you call has_duplicate() for the previous character and return the return value of that recursive call. The base case is when the index is less than 0, in which case you return 0 since there are no duplicates.

Originally Posted by transgalactic2

how to write the main remove_duplicates function??

If the current character is a duplicate, you overwrite it and call remove_duplicates() with the same index since the "next character" is now the current character, otherwise you do not overwrite it and call remove_duplicates() for the next character. The base case is when the current character is '\0', in which case you do nothing and return.

Originally Posted by whiteflags

This will maintain the last occurance of any characters. To maintain the first occurance of any characters, instead of overwriting, you would copy the unique to a destination string. Check for uniqueness by searching in the destination string. The rest of the process is unchanged, I think.

hmm... if you did not understand what has_duplicate() was supposed to do, then perhaps transgalactic2 might not have understood it either. Maybe is_duplicate is a better name

The first occurrence is maintained since the duplicate check is only concerned with the portion of the string before the current character. That is, if there is a duplicate found, then the current character is the actual duplicate that should be removed.