Changeset 253 for liacs/TPFL2010/assignment3/cyk.py

Timestamp:

Dec 15, 2010, 4:42:17 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Implementation of the algoritm

File:

• liacs/TPFL2010/assignment3/cyk.py (modified) (5 diffs)

liacs/TPFL2010/assignment3/cyk.py

@@ -3 +3 @@
 # Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm.
 #
+from pprint import pprint
 
 
@@ -22 +23 @@
 n = len(w)
 r = [[[]]*(n+1) for x in irange(0,n)]
+cyk = dict();
 
 
+for k in cnf.keys():
+  for i in irange(1,n):
+    for j in irange(1,n):
+      cyk[(k,i,j)] = []
 
 
-def printr():
+def print_r():
+  print '''
+\\begin{table}[htbp] 
+\\center
+\\begin{tabular}{|c||%s}
+\\hline
+''' % ('c|'*n)
   print 'i\\textbackslash j &',
   for i in irange(1,n):
-    print "%-10s &" % i,
+    print "%-10s" % i,
+    if i != n:
+      print "&",
   print "\\\\ \\hline \\hline"
   
@@ -37 +51 @@
     for j in irange(1,n):
       if r[i][j] == [None]:
-        item = "@"
-      else:
-        item = ",".join(r[i][j]),
-      print "%-10s &" % item,
+        item = "$\\emptyset$",
+      else: 
+        item = ''
+        for k in r[i][j]:
+           c =  from_cyk(k,i,j)
+           if c:
+             item += "%s: %s \\\\" % (k, c)
+           else:
+             item += "%s \\\\" % k
+             
+      print "\\begin{tabular}{l}",
+      print "%-10s \\end{tabular}" % item,
+      if j != n:
+        print "&",
     print "\\\\ \\hline"
+  print '''
+\\end{tabular}
+\\label{tb:cyk}
+\\caption{$CYK(L(G),babbbab)$. Algoritme in \cite{JS2009}[pg.~142]}
+\\end{table}
+'''
+
 
 def to_r(i,j,k):
@@ -52 +83 @@
 def from_r(i,j):
   return r[i][j]
+
+def to_cyk(A,i,j,B):
+  cyk[(A,i,j)] += [B]
+
+def from_cyk(A,i,j):
+  r = cyk[(A,i,j)]
+  if not r:
+    return None 
+  else:
+    return ",".join([str(x) for x in r])
+
 
 def letter(i):
@@ -74 +116 @@
           if x[0] in from_r(i,k) and x[1] in from_r(k+1,j):
             to_r(i,j,y)
+            to_cyk(y,i,j,(x[0],x[1],k))
 
 
-printr()
+print_r()
+#pprint(cyk)