Recursive algorithm for substrings

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 4677 Views - Last Post: 07 November 2013 - 09:58 AM

#1 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Recursive algorithm for substrings

Posted 25 October 2013 - 08:52 AM

w.substring(natural i,natural j) returns the substring consisting consisting of the characters with the position k such that i<= kk < j

we already have valid recursive algorithm for these that we can use, below:

boolean isZero (natural x)
// Returns true if and only if x is zero

natural successor (natural x)
// Returns the successor of x

natural pred (natural x) 
// Returns the predecessor of x, if x is not zero
// Throws an exception if x is zero

pred(successor(x)) == x
if !isZero(x), successor(pred(x)) == x

public natural plus (natural x, natural y) {
 if (isZero(y)) return x;
 return successor (plus (x, pred(y));}

public natural minus (natural x, natural y) {
If(x>y) return 0;
// return y - x}

public natural times (natural x, natural y) {
 if (isZero(y) return 0;
 return plus( times(x, pred(y)), x);}

public static boolean isEmpty( ){...}

public static string append (string w, char a) {...}

public static char last (string w) {...}

public static string allButLast (string w) {...}

public static natural length (string w) {
 if (isEmpty(w)) return 0;
 return successor(length(allButLast(w)));}

public static string cat (string w, string x) {
 if (isEmpty(x)) return w;
 return append(cat(w, allButLast(x)), last(x));}

public static string rev (string w) {
 if (isEmpty(w)) return w;
 return cat(last(w), rev(allButLast(w)));}




After few (many) attempts, I have come up with this algorithm. Comments/suggestion? I am not allowed to answer this using Java program.

public static string substring(string w, natural i, natural j){
if(length(w) == minus(i,j)){ return w;}

else {
     if((i >= length(w)||(i >= length(w)){throw exception;}
     
     elseif (i>=j){throw exception;}

     else{ return substring(rev(substring(allButLast(w)), i, j), i, j)

     }
}

This post has been edited by Atli: 25 October 2013 - 09:02 AM
Reason for edit:: Replaced [b] tags around code with [code] tags.


Is This A Good Question/Topic? 0
  • +

Replies To: Recursive algorithm for substrings

#2 Peter O   User is offline

  • D.I.C Regular

Reputation: 131
  • View blog
  • Posts: 309
  • Joined: 19-October 13

Re: Recursive algorithm for substrings

Posted 25 October 2013 - 09:34 AM

On line 2, if length(w)=8, i=2 and j=10 then this will return w when I think it should return an error because j > length(w).

On line 5 you have repeated i >= length(w) twice.

On line 9, you have got the parentheses wrong, passing arguments to rev instead of substring.
Was This Post Helpful? 1
  • +
  • -

#3 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 25 October 2013 - 09:52 AM

Thank you for the correction! You are right about j > length(w).
I also changed i to j in the if-else. So does the base case
(length(w) == minus(i,j)){ return w;}
make sense?

public static string substring(string w, natural i, natural j){

if((i >= length(w)||(j >= length(w)){throw exception;}
elseif(length(w) == minus(i,j)){ return w;}
elseif (i>=j){return "";} //empty string
else {
     
      return substring(rev(substring(allButLast(w)), i, j)), i, j);

     }
}


hope i got the parenthesis right now
Also if i > j then it will return an empty string, this is what my professor told me.
So i added
elseif (i>=j){return "";}
with my other base cases.

This post has been edited by deprosun: 25 October 2013 - 09:57 AM

Was This Post Helpful? 0
  • +
  • -

#4 Peter O   User is offline

  • D.I.C Regular

Reputation: 131
  • View blog
  • Posts: 309
  • Joined: 19-October 13

Re: Recursive algorithm for substrings

Posted 25 October 2013 - 10:35 AM

Now you got 4 left parentheses and 5 right parentheses on line 8. I guess what you meant was this:
return substring(rev(substring(allButLast(w), i, j)), i, j);
But to be honest I don't really understand how you have thought about this line.

This post has been edited by Peter O: 25 October 2013 - 10:38 AM

Was This Post Helpful? 3
  • +
  • -

#5 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 25 October 2013 - 12:42 PM

yes, my algorithm will fail terribly because it's not doing what i thought it was.
I wanted the string to reverse right after it ran
(substring(allButLast(w), i, j)
,
but forgot that it goes back up and runs everything else.

I need to think more
Was This Post Helpful? 0
  • +
  • -

#6 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Recursive algorithm for substrings

Posted 25 October 2013 - 03:49 PM

I think I see what you are trying to do. I think it would be easier if you were to break the logic up into two helper functions
allButLastN(string w, natural n)  //return all but the last n characters
{ /*To be defined*/ }
allButFirstN(string w, natural n) //return all but the first n characters
{ return /*logic involving rev and allButLastN*/); }



then your main line would be something like return getAllButFirstN(getAllButLastN(w, j), i)

However, there is an easier way to write the substring function. let w="abcdefg", i=2, and j=4 so substring(w, i, j) -> "bcd". Initially, I can break the string into "abcdef" and 'g'. Typical recursion will perform tests on 'g' and based on the results of those tests, it may perform an operation between 'g' and the result of recursion on "abcdef". The recursion will do the same tests to "abcde" and 'f' and so on. Try and think about what tests you can do and operations you can perform to achieve the desired result.
Was This Post Helpful? 2
  • +
  • -

#7 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 11:06 AM

Interesting that you came with that helper function. First part of the question asked me to write a recursive method for substring(string w , natural i,) such that it returns a substring of w obtained by deleting first i characters. This is what i came up with:

public static string substring(string w, natural i){

if(isZero(i)){return w;}
else{
     if(i>= length(w)){
     throw exception;
     }
     else{
     return substring(rev(allButLast(rev(w))), pred(i));
     }

}

Hope this is right, this looked really right to me. -__-

View Postmojo666, on 25 October 2013 - 05:49 PM, said:

let w="abcdefg", i=2, and j=4 so substring(w, i, j) -> "bcd".


For this example, substring(w, i, j); if i = 0 then it would consider w[0] which is equal to "a".
So i and j refer to the position of the characters in this method. I thought exactly the same way you did, but
my professor said it follows the JAVA API of this method.
Was This Post Helpful? 0
  • +
  • -

#8 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 12:49 PM

Quote

Hope this is right, this looked really right to me. -__-


It looks pretty correct to me as well. The only problem is the exception is slightly off (if i is length(w), it should return an empty string). Here's how I would have done it. This may also give you a hint at how to handle substring(w, i, j)

public static string substring(string w, natural n){
	if(i > length(w)){throw exception;}
	else{return rsubstring(w, n);}
}
/*I prefer to handle validation in a seperate "shell" function so I don't have to worry about exception checks interfering with the recursive logic*/

public static string rsubstring(string w, natural n){
	if(isZero(length(w))){return w;}  //could alternatively be if(length(w)<=i){return /*Empty string*/;}
	else if(length(w)>n){
		return append(rsubstring(allButLast(w), n), last(w));
	}	
	else{
		return rsubstring(allButLast(w), n);
	}
}


Quote

For this example, substring(w, i, j); if i = 0 then it would consider w[0] which is equal to "a".
So i and j refer to the position of the characters in this method. I thought exactly the same way you did, but
my professor said it follows the JAVA API of this method.


Ok, so then in my example substring("abcdefg", 2, 4) needs to return "cde". It should still be the same code, just with some extra pred or successor functions. This can be kindof a pain to keep track of, especially since substring(w, n) uses a different convention, but actually in this case it is a bit easier. In "abcdefg", c is the third number, but its position "i" is 2. So, substring("abcdefg", i) should return "cdefg" which is what we want. You just have to add logic to get rid of everything beyond j. So, if you still wanted to go the helper method route, the main line in substring(w, i, j) will be
return substring(substring(w, i), /*fancy math*/)) //with rev functions inserted appropriately
.
Was This Post Helpful? 2
  • +
  • -

#9 readysoft   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 26-October 13

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 12:58 PM

very fasinating logic talk you guys got going. I'm new to thsi stuff, Can someone tell me what language is being used?
Was This Post Helpful? 0
  • +
  • -

#10 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 01:13 PM

View Postreadysoft, on 26 October 2013 - 02:58 PM, said:

very fasinating logic talk you guys got going. I'm new to thsi stuff, Can someone tell me what language is being used?


The language, you can say, we're talking about is JAVA. But the point is to learn recursive definitions using pre-existing recursive definitions. Sorry if that is very discrete. You can't blame me, as this is discrete math. :P

This post has been edited by deprosun: 26 October 2013 - 01:14 PM

Was This Post Helpful? 0
  • +
  • -

#11 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 01:20 PM

View Postmojo666, on 26 October 2013 - 02:49 PM, said:

Quote

Hope this is right, this looked really right to me. -__-


It looks pretty correct to me as well. The only problem is the exception is slightly off (if i is length(w), it should return an empty string). Here's how I would have done it. This may also give you a hint at how to handle substring(w, i, j)


You are correct, however according to exercise it should throw an exception if i >= to the length. And yes, I will try to use substring(string w, natural i) to delete character that is in "j" and "j" plus position. Then reverse the string and delete "i-1" and before positions. (not
i -1 position: since the string will be reversed
i = length(w)-i
)

This post has been edited by deprosun: 26 October 2013 - 01:22 PM

Was This Post Helpful? 0
  • +
  • -

#12 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Recursive algorithm for substrings

Posted 26 October 2013 - 02:04 PM

Quote

very fasinating logic talk you guys got going. I'm new to thsi stuff, Can someone tell me what language is being used?


I don't think this is a particular language. The style you see being used is prevalent in functional programming languages such as lisp and scala, however you can still use simple arithmetic commands in those languages. I have only seen concepts like predecessor and successor used in theory such as lambda calculus.
Was This Post Helpful? 1
  • +
  • -

#13 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 28 October 2013 - 11:17 AM

I am trying to use this:

rev(substring(rev(substring(w,i)), (length(w)-j)))

but the length of w changes when substring(w,i) runs....ugh
Was This Post Helpful? 0
  • +
  • -

#14 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Recursive algorithm for substrings

Posted 28 October 2013 - 03:22 PM

Really?!? That would be incredibly bizarre behavior for any language.

Are you sure your math just isn't off a bit? Use the example substring("abcdefg", 2, 4) -> "cde". The length is 7, so 7-4 leaves 3. What happens when you trim the last 3 letters off?

If it is actually modifying the length, you could adjust it so it takes off everything past j first and then trim off everything before i.
Was This Post Helpful? 1
  • +
  • -

#15 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: Recursive algorithm for substrings

Posted 28 October 2013 - 06:29 PM

View Postmojo666, on 28 October 2013 - 05:22 PM, said:

Are you sure your math just isn't off a bit? Use the example substring("abcdefg", 2, 4) -> "cde". The length is 7, so 7-4 leaves 3. What happens when you trim the last 3 letters off?

If it is actually modifying the length, you could adjust it so it takes off everything past j first and then trim off everything before i.



substring("abcdefg", 2, 4) should give me "cd" as the definition.
I want to try my algorithm once more, so:
w = "abcdefg"
To find: substring(w, 2, 4)
Desrired: "cd"
This is what i am going to use to see if correct: rev(substring(rev(substring(w,i)), j))

Lets work on the inside:
substring(w,i) --> substring("abcdefg",2)--> "cdefg"

Now put that into rev()method:
rev("cdefg")--> "gfedc"

----Here I would have to make sure the original length of the w is stored into a variable----
----int actualJ = w.lentgh - j;

Now running another substring(w, actualJ)
substring(w, 3)-->"dc"

Now run the last rev() method:
rev("dc")--> "cd"
-------------------------------------------------------
This method seems to work only if I store the original length in the method. (then tweaking j as length(w)-j)
Wrong?

This post has been edited by deprosun: 28 October 2013 - 06:31 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2