Convert some Python code to C++

[meyousikmann]

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[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1,
j-1)])
else:
R = set()
if C[i][j-1] >= C[i-1][j]:
R.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
R.update(backTrackAll(C, X, Y, i-1, j))
return R

Thanks!

[kyosohma]

On Nov 13, 9:28 am, [e-mail] 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[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1,
j-1)])
else:
R = set()
if C[i][j-1] >= C[i-1][j]:
R.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
R.update(backTrackAll(C, X, Y, i-1, 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

[Neil Cerutti]

On 2007-11-13, ky******@gmail.com <ky******@gmail.comwrote:

On Nov 13, 9:28 am, [e-mail] 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[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1,
j-1)])
else:
R = set()
if C[i][j-1] >= C[i-1][j]:
R.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
R.update(backTrackAll(C, X, Y, i-1, 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

[kyosohma]

On Nov 13, 12:51 pm, Neil Cerutti <[e-mail]:

On 2007-11-13, [e-mail] <[e-mail]:

On Nov 13, 9:28 am, [e-mail] 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[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1,
j-1)])
else:
R = set()
if C[i][j-1] >= C[i-1][j]:
R.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
R.update(backTrackAll(C, X, Y, i-1, 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

[Loic Mahe]

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[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1,
j-1)])
else:
R = set()
if C[i][j-1] >= C[i-1][j]:
R.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
R.update(backTrackAll(C, X, Y, i-1, 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!