Skip to content

Commit

Permalink
added permutations functions, better tests
Browse files Browse the repository at this point in the history
blinkybool committed Feb 5, 2020
1 parent 07b9669 commit 168884d
Showing 6 changed files with 195 additions and 32 deletions.
4 changes: 2 additions & 2 deletions magma/__init__.py
Original file line number Diff line number Diff line change
@@ -18,7 +18,7 @@
from .motzkin_families.motzkinPaths import *

for Catalan_Family in Catalan.iter_families():
Catalan_Family.init_norm_cache()
Catalan_Family.init_caches()

for Motzkin_Family in Motzkin.iter_families():
Motzkin_Family.init_norm_cache()
Motzkin_Family.init_caches()
51 changes: 51 additions & 0 deletions magma/__main__.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,51 @@
from magma import RS115, RS1, TwoThreeOneAvoiding
# m = 5
# for perm in RS115.products(m):
# print('--------------------------')
# print(perm)
# # print(RS115.to_ascii(perm))
# if m > 1:
# fst, snd = RS115.exhaustive_factorise(perm)
# # print('exhaustve')
# # print('fst:')
# print(fst)
# # print(RS115.to_ascii(fst))
# # print('snd:')
# print(snd)
# # print(RS115.to_ascii(snd))

# fst, snd = RS115.factorise(perm)
# # print('factorise')
# # print('fst:')
# print(fst)
# # print(RS115.to_ascii(fst))
# # print('snd:')
# print(snd)
# # print(RS115.to_ascii(snd))

# perm = (2,1,3,5,4)
# print(RS115.to_ascii(perm))
# fst, snd = RS115.exhaustive_factorise(perm)
# print('exhaustive')
# print('fst:')
# print(RS115.to_ascii(fst))
# print('snd:')
# print(RS115.to_ascii(snd))

# fst, snd = RS115.factorise(perm)
# print('factorise')
# print('fst:')
# print(RS115.to_ascii(fst))
# print('snd:')
# print(RS115.to_ascii(snd))

perm1 = ()
perm2 = (2,1,3)

perm = TwoThreeOneAvoiding.product(perm1, perm2)
fact_perm = TwoThreeOneAvoiding.factorise(perm)

print(perm1)
print(perm2)
print(perm)
print(fact_perm)
40 changes: 36 additions & 4 deletions magma/catalan.py
Original file line number Diff line number Diff line change
@@ -51,17 +51,49 @@ def identity(cls):
def products(cls, norm):
if norm in cls.norm_cache: return cls.norm_cache[norm]

cls.norm_cache[norm] = list(
cls.product(fst, snd)
cls.norm_cache[norm] = [
cls.cache_product(fst, snd, cls.product(fst, snd))
for i in range(1,norm)
for fst in cls.products(i)
for snd in cls.products(norm - i)
)
]
return cls.norm_cache[norm]

@classmethod
def init_norm_cache(cls):
def cache_product(cls, fst, snd, prod):
cls.prod_cache[fst, snd] = prod
cls.fact_cache[prod] = (fst, snd)
return prod

@classmethod
def init_caches(cls):
cls.norm_cache = {1: [cls.generator()]}
cls.fact_cache = {}
cls.prod_cache = {}

@classmethod
def exhaustive_factorise(cls, obj):
assert obj != cls.generator()

if obj in cls.fact_cache:
return cls.fact_cache[obj]

try:
norm = cls.direct_norm(obj)

for prod in cls.products(norm):
if cls.normalise(prod) == cls.normalise(obj):
return cls.fact_cache[prod]
else:
raise Error(f'No matching object of norm {norm} found')

except NotImplementedError:
norm = 2
while True:
for prod in cls.products(norm):
if cls.normalise(prod) == cls.normalise(obj):
return cls.fact_cache[prod]
norm += 1

@classmethod
def verify(cls, obj):
125 changes: 101 additions & 24 deletions magma/catalan_families/permutations.py
Original file line number Diff line number Diff line change
@@ -1,7 +1,22 @@
from magma import Catalan

# TODO inherit from Catalan once factorise implemented
class RS115:
def rothe_diagram(permutation):
if len(permutation)==0:
return '+'
perm_indices = range(1, len(permutation)+1)
rows = ((' * ' if permutation[i-1]==j else ' ' for j in perm_indices) for i in perm_indices)

line_sep = '+---' * len(permutation) + '+'

rothe_diagram = (line_sep
+ '\n'
+ ('\n' + line_sep + '\n').join('|' + '|'.join(row) + '|' for row in rows)
+ '\n'
+ line_sep)

return rothe_diagram

class RS115(Catalan):
"""
Permutations a1 a2 ... am-1 of [m-1] with longest decreasing subsequence of
length at most 2 (no integers i < j < k such that ai > aj > ak)
@@ -19,35 +34,65 @@ class RS115:

ID = 'RS115'
names = ['321 Avoiding Permutations']
keywords = {'permutations', 'sequence', 'avoiding', '321', 'three', 'two', 'one'}
keywords = {'permutation', 'sequence', 'avoiding', '321', 'three', 'two', 'one'}

generator = lambda: ()

@classmethod
def product(cls, fst, snd):
# TODO implement permutations product
# new_snd = [None] + list(snd)

# last_white = 0
# for i, snd_i in enumerate(snd, start=1):
# if snd_i > i:
# new_snd[last_white] = snd_i
# last_white = i

# new_snd[-1] = len(snd) + 1
new_snd = [None] + list(snd)

last_white = 0
for i, snd_i in enumerate(snd, start=1):
if snd_i > i:
new_snd[last_white] = snd_i
last_white = i

new_snd[last_white] = len(snd) + 1

return fst + tuple(x + len(fst) for x in new_snd)

@classmethod
def factorise(cls, permutation):
# TODO implement permutations factorise
pass
def factorise(cls, perm):
# recognise right multiplication by generator
if perm[-1] == len(perm):
return (perm[:-1], ())

# convert perm to list to shift the white dots
# add dumby item at index 0 to make shift_perm[i] the same as perm_i
shift_perm = [None] + list(perm)

# index of the rightmost white dot (above the diagonal)
white_index = shift_perm.index(len(perm))

# undo the cascading of white dots from the right until one passes the diagonal
for i in reversed(range(1,white_index)):
# test if there is a white dot here
if shift_perm[i] > i:
# shift the last white dot to this column as long as it doesn't pass
# the diagonal
if shift_perm[i] >= white_index:
shift_perm[white_index] = shift_perm[i]
white_index = i
else:
# this dot is the extra dot added by the product function
break

# slice up to the critical white dot (-1 to account for different indexing)
fst = perm[:white_index-1]
snd = tuple(x-white_index+1 for x in shift_perm[white_index+1:])

return (fst, snd)

@classmethod
def direct_norm(cls, permutation):
return len(permutation) + 1

class RS116(Catalan):
@classmethod
def to_ascii(cls, permutation):
return rothe_diagram(permutation)

class RS116(RS115):
"""
Permutations a1 a2 ... am-1 of [m-1] with longest decreasing subsequence of
length at most 2 (no integers i < j < k such that aj < ak < ai)
@@ -60,24 +105,56 @@ class RS116(Catalan):
Generator:
()
Example: (m=5)
(3,1,2,4)
(3,2,4,1)
"""

ID = 'RS116'
names = ['312 Avoiding Permutations']
keywords = {'permutations', 'sequence', 'avoiding', '312', 'three', 'one', 'two'}
keywords = {'permutation', 'sequence', 'avoiding', '312', 'three', 'one', 'two'}

generator = lambda: ()

@classmethod
def product(cls, fst, snd):
return fst + (len(fst) + len(snd) + 1,) + tuple(x+len(fst) for x in snd)
return fst + tuple(x+len(fst)+1 for x in snd) + (len(fst)+1,)

@classmethod
def factorise(cls, permutation):
# TODO implement permutations factorise
pass
split = permutation[-1]

fst = tuple(x for x in permutation if x < split)
snd = tuple(x-len(fst)-1 for x in permutation if x > split)

return (fst, snd)

class TwoThreeOneAvoiding(RS115):
"""
Permutations a1 a2 ... am-1 of [m-1] with longest decreasing subsequence of
length at most 2 (no integers i < j < k such that ak < ai < aj)
Data Type:
tuple(int)
Format:
sequences of integers in the set [1,m-1]. [0] is considered the empty
set, and [1] = {1}
Generator:
()
Example: (m=5)
(3,1,2,4)
"""

ID = 'MA??'
names = ['231 Avoiding Permutations']
keywords = {'permutation', 'sequence', 'avoiding', '231', 'two', 'three', 'one'}

generator = lambda: ()
product = lambda fst, snd: fst + (len(fst) + len(snd) + 1,) + tuple(x+len(fst) for x in snd)

@classmethod
def direct_norm(cls, permutation):
return len(permutation) + 1
def factorise(cls, perm):
split = perm.index(len(perm))
fst = perm[:split]
snd = tuple(x-len(fst) for x in perm[split+1:])

return (fst, snd)

2 changes: 1 addition & 1 deletion magma/motzkin.py
Original file line number Diff line number Diff line change
@@ -57,7 +57,7 @@ def products(cls, norm):
return cls.norm_cache[norm]

@classmethod
def init_norm_cache(cls):
def init_caches(cls):
cls.norm_cache = {1: [cls.generator()], 2: [cls.unary(cls.generator())]}

@classmethod
5 changes: 4 additions & 1 deletion magma/tests/test_catalan.py
Original file line number Diff line number Diff line change
@@ -13,4 +13,7 @@ def test_identities(self):
identity = Catalan_Family.identity()
for m in range(1,self.MAX_NORM+1):
for obj in Catalan_Family.products(m):
self.assertEqual(identity(obj), obj)
self.assertEqual(identity(obj), obj)
if m > 1:
same_obj = Catalan_Family.product(*Catalan_Family.factorise(obj))
self.assertEqual(Catalan_Family.normalise(same_obj), Catalan_Family.normalise(obj))

0 comments on commit 168884d

Please sign in to comment.