P: n/a

I am working on an implementation of the Longest Common Subsequence
problem (as I understand it, this problem can be used in spell
checking type activities) and have used this site to understand the
problem and its solution: http://en.wikibooks.org/wiki/Algorit...on_subsequence
For those that understand algorithms and can talk Python, I want to
convert the Python code in the section "Reading out all LCSs" into C++
code but I don't understand some of the syntax. Can anyone give me a
hand?
Here is the code from that section, but is probably of little use
without understanding the entire problem setup given at the site
above:
def backTrackAll(C, X, Y, i, j):
if i == 0 or j == 0:
return set([""])
elif X[i1] == Y[j1]:
return set([Z + X[i1] for Z in backTrackAll(C, X, Y, i1,
j1)])
else:
R = set()
if C[i][j1] >= C[i1][j]:
R.update(backTrackAll(C, X, Y, i, j1))
if C[i1][j] >= C[i][j1]:
R.update(backTrackAll(C, X, Y, i1, j))
return R
Thanks!  
Share this Question
P: n/a

On Nov 13, 9:28 am, meyousikm...@yahoo.com wrote:
I am working on an implementation of the Longest Common Subsequence
problem (as I understand it, this problem can be used in spell
checking type activities) and have used this site to understand the
problem and its solution:
http://en.wikibooks.org/wiki/Algorit...trings/Longest...
For those that understand algorithms and can talk Python, I want to
convert the Python code in the section "Reading out all LCSs" into C++
code but I don't understand some of the syntax. Can anyone give me a
hand?
Here is the code from that section, but is probably of little use
without understanding the entire problem setup given at the site
above:
def backTrackAll(C, X, Y, i, j):
if i == 0 or j == 0:
return set([""])
elif X[i1] == Y[j1]:
return set([Z + X[i1] for Z in backTrackAll(C, X, Y, i1,
j1)])
else:
R = set()
if C[i][j1] >= C[i1][j]:
R.update(backTrackAll(C, X, Y, i, j1))
if C[i1][j] >= C[i][j1]:
R.update(backTrackAll(C, X, Y, i1, j))
return R
Thanks!
You might try Shed Skin: http://sourceforge.net/projects/shedskin/
It's been a while since I did C++. I would recommend going through a
basic C++ tutorial. I'm pretty sure the equivalence operators are
almost the same. You'll likely need to declare the types for the
arguments passed into the function as well.
I think lists are called arrays in C++. I don't know what the "set"
equivalent is though.
Mike  
P: n/a

On 20071113, ky******@gmail.com <ky******@gmail.comwrote:
On Nov 13, 9:28 am, meyousikm...@yahoo.com wrote:
>I am working on an implementation of the Longest Common Subsequence problem (as I understand it, this problem can be used in spell checking type activities) and have used this site to understand the problem and its solution:
http://en.wikibooks.org/wiki/Algorit...trings/Longest...
For those that understand algorithms and can talk Python, I want to convert the Python code in the section "Reading out all LCSs" into C++ code but I don't understand some of the syntax. Can anyone give me a hand?
Here is the code from that section, but is probably of little use without understanding the entire problem setup given at the site above:
def backTrackAll(C, X, Y, i, j): if i == 0 or j == 0: return set([""]) elif X[i1] == Y[j1]: return set([Z + X[i1] for Z in backTrackAll(C, X, Y, i1, j1)]) else: R = set() if C[i][j1] >= C[i1][j]: R.update(backTrackAll(C, X, Y, i, j1)) if C[i1][j] >= C[i][j1]: R.update(backTrackAll(C, X, Y, i1, j)) return R
Thanks!
You might try Shed Skin:
http://sourceforge.net/projects/shedskin/
It's been a while since I did C++. I would recommend going
through a basic C++ tutorial. I'm pretty sure the equivalence
operators are almost the same. You'll likely need to declare
the types for the arguments passed into the function as well.
I think lists are called arrays in C++. I don't know what the
"set" equivalent is though.
It is called set, oddly enough. ;)
There's an overload of the set::insert function that takes a
couple of iterators that will serve for Python's update method.

Neil Cerutti  
P: n/a

On Nov 13, 12:51 pm, Neil Cerutti <horp...@yahoo.comwrote:
On 20071113, kyoso...@gmail.com <kyoso...@gmail.comwrote:
On Nov 13, 9:28 am, meyousikm...@yahoo.com wrote:
I am working on an implementation of the Longest Common
Subsequence problem (as I understand it, this problem can be
used in spell checking type activities) and have used this
site to understand the problem and its solution:
>http://en.wikibooks.org/wiki/Algorit...trings/Longest...
For those that understand algorithms and can talk Python, I
want to convert the Python code in the section "Reading out
all LCSs" into C++ code but I don't understand some of the
syntax. Can anyone give me a hand?
Here is the code from that section, but is probably of little
use without understanding the entire problem setup given at
the site above:
def backTrackAll(C, X, Y, i, j):
if i == 0 or j == 0:
return set([""])
elif X[i1] == Y[j1]:
return set([Z + X[i1] for Z in backTrackAll(C, X, Y, i1,
j1)])
else:
R = set()
if C[i][j1] >= C[i1][j]:
R.update(backTrackAll(C, X, Y, i, j1))
if C[i1][j] >= C[i][j1]:
R.update(backTrackAll(C, X, Y, i1, j))
return R
Thanks!
You might try Shed Skin:
http://sourceforge.net/projects/shedskin/
It's been a while since I did C++. I would recommend going
through a basic C++ tutorial. I'm pretty sure the equivalence
operators are almost the same. You'll likely need to declare
the types for the arguments passed into the function as well.
I think lists are called arrays in C++. I don't know what the
"set" equivalent is though.
It is called set, oddly enough. ;)
There's an overload of the set::insert function that takes a
couple of iterators that will serve for Python's update method.

Neil Cerutti
I suspected as much, but I don't think they ever got that far into C++
in the classes I took. I'll have to file that little nugget for future
reference. Hopefully the OP is getting something out of this as well.
Mike  
P: n/a
 me**********@yahoo.com a écrit :
For those that understand algorithms and can talk Python, I want to
convert the Python code in the section "Reading out all LCSs" into C++
code but I don't understand some of the syntax. Can anyone give me a
hand?
def backTrackAll(C, X, Y, i, j):
if i == 0 or j == 0:
return set([""])
elif X[i1] == Y[j1]:
return set([Z + X[i1] for Z in backTrackAll(C, X, Y, i1,
j1)])
else:
R = set()
if C[i][j1] >= C[i1][j]:
R.update(backTrackAll(C, X, Y, i, j1))
if C[i1][j] >= C[i][j1]:
R.update(backTrackAll(C, X, Y, i1, j))
return R
Thanks!
just have a look at this tutorial: and look for Lists and Sets http://docs.python.org/tut/tut.html
and look in the reference index for set() and list() in http://docs.python.org/lib/genindex.html
or just pick the algo in another language in the url you give
or tell us precisely what part of the python algo you do not understant!   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1888
 replies: 4
 date asked: Nov 13 '07
