By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,768 Members | 2,004 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,768 IT Pros & Developers. It's quick & easy.

Convert some Python code to C++

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[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!

Nov 13 '07 #1
Share this Question
Share on Google+
4 Replies


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[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

Nov 13 '07 #2

P: n/a
On 2007-11-13, 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[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
Nov 13 '07 #3

P: n/a
On Nov 13, 12:51 pm, Neil Cerutti <horp...@yahoo.comwrote:
On 2007-11-13, 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[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

Nov 13 '07 #4

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[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!
Nov 14 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.