SM-7-Matching -- Sage

#INTERIOR FUNCTIONS def order(R1): L = [] for part in range(R1.cardinality()): P = R1[part] Q = [] for i in range(len(P)): Q.append(P[i]) Q.sort() L.append(Q) L.sort() return L def add(L1,L2): #returns the element-wise sum of L1 and L2 (which are assumed to be of equal size) L3 = [] for i in range(len(L1)): L3.append(L1[i]+L2[i]) return L3 def covers(P1,P2): #This function takes two partitions, P1 and P2, as inputs and #determines whether or not P1 covers P2. #First, we make copies of the two inputted partitions. Pa = [] for idx in range(len(P1)): Pa.append(P1[idx]) Pb = [] for idx in range(len(P2)): Pb.append(P2[idx]) size = len(Pa) matchcount = 0 for index in range(size): if Pa[index] in Pb: matchcount = matchcount + 1 Pb.remove(Pa[index]) if (matchcount+1)==size: return 1 return 0 def edgelist(R1,R2): #This function takes two sets of partitions, R1 and R2, as inputs and returns a list #ordered pairs [i,j] such that R1[i] and R2[j] form an edge according to the covering relation. edgelist = [] for index1 in range(R1.cardinality()): for index2 in range(R2.cardinality()): if covers(R1[index1],R2[index2]): edgelist.append([index1,index2]) return edgelist def edgelist2(R1,R2): #Does edgelist, but does it for lists rather than the goofy proprietary data structure edgelist = [] for index1 in range(len(R1)): for index2 in range(len(R2)): if covers(R1[index1],R2[index2]): edgelist.append([index1,index2]) return edgelist def contains(List,element,idx): #This function determines if any of the elements of List contain element at position idx. for i in range(len(List)): if List[i][idx]==element: return 1 return 0 def degree(R1,R2): degreelist = [[],[]] for i in range(len(R1)): degreelist[0].append(0) for i in range(len(R2)): degreelist[1].append(0) for index1 in range(len(R1)): for index2 in range(len(R2)): if covers(R1[index1],R2[index2]): degreelist[0][index1] += 1 degreelist[1][index2] += 1 return degreelist def incidenceMatrix(R1,R2): length1 = R1.cardinality() length2 = R2.cardinality() numVertices = length1+length2 listofedges = edgelist(R1,R2) M = matrix(GF(2),length1+length2,len(listofedges)) for i in range(len(listofedges)): M[listofedges[i][0],i]=1 M[listofedges[i][1]+length1,i]=1 return [M,numVertices]

def matchingByRank(n,k): #This determines if there is a maximum matching between the kth level set of P_n and the (k+1)st R1 = Partitions(n,length=k) R2 = Partitions(n,length=k+1) L = incidenceMatrix(R1,R2) if rank(L[0])==L[1]-1: return True False

import random def dana2(R1,R2,B,numtimes): #This function conducts a random walk along matchings of two inputted #consecutive level sets with each step determined as follows - # 1) A random edge is selected # 2) If the edge can be added to the graph of the two level sets, it is added. # 3) If the edge can be removed, it is removed with probability 1/B # 4) If the edge can be neither added nor removed, a new edge is selected and the process is repeated # 5) If the resulting graph is a maximal matching, the counter of each included edge is incremented #Steps are taken until numtimes maximum matchings are encountered, #and the list of edgecounts is returned. listofedges = edgelist2(R1,R2) edgecount = [] for i in range(len(listofedges)): edgecount.append(0) currentedgecount = copy(edgecount) numedges = len(listofedges) edges = [] maximumnum = min(len(R1),len(R2)) nummatchingsfound = 0 while (nummatchingsfound<numtimes): newedge = listofedges[random.randint(0,numedges-1)] if newedge in edges: if (current_randstate().c_rand_double() < (1/B)): edges.remove(newedge) else: vertex1 = newedge[0] vertex2 = newedge[1] if (contains(edges,vertex1,0)==0): if (contains(edges,vertex2,1)==0): edges.append(newedge) if (len(edges)==maximumnum): for i in range(len(currentedgecount)): currentedgecount[i]=0 for edgeindex in range(len(edges)): for edge2index in range(len(listofedges)): if edges[edgeindex]==listofedges[edge2index]: currentedgecount[edge2index] = 1 break edgecount = add(edgecount,currentedgecount) nummatchingsfound = nummatchingsfound + 1 return edgecount

def matchingdata(start,finish,B,numtimes): #This function uses numtimes steps in dana2 to approximate the relative frequencies of each edge #for consecutive pair of level sets for each value of n in [start,finish] for n in range(start,finish+1): print '********************************n =',n,'********************************' for levelset in range(n-1): print '*********k =',levelset+1,'to k =',levelset+2,'*********' L1 = Partitions(n,length=levelset+1) R1 = order(L1) L2 = Partitions(n,length=levelset+2) R2 = order(L2) listofedges = edgelist2(R1,R2) degreelist = degree(R1,R2) M = dana2(R1,R2,B,numtimes) for i in range(len(listofedges)): print R1[listofedges[i][0]],'(',degreelist[0][listofedges[i][0]],')','to',R2[listofedges[i][1]],'(',degreelist[1][listofedges[i][1]],')',':', (M[i]/numtimes).n(digits=3)

#Test matching By Rank function, which determines if there is a matching by using the rank of the incidence matrix print "Is there a matching for n=8 between levels 3 and 4?" print matchingByRank(8,3) #Define 2 partitions for n=8 for level sets 3 and 4 print "Level set 3" R1 = order(Partitions(8,length=3)) print R1 print "Level set 4" R2 = order(Partitions(8,length=4)) print R2 #Perform a random walk print "The list of edges between level set 3 and level set 4" print edgelist2(R1,R2) print "The number of times each edge appeared in a random walk" print dana2(R1,R2,3,100) #Find the data for how many times each edge appears print "For n=8, the matching data from our random walk is" matchingdata(8,8,3,100)

Is there a matching for n=8 between levels 3 and 4?
True
Level set 3
[[1, 1, 6], [1, 2, 5], [1, 3, 4], [2, 2, 4], [2, 3, 3]]
Level set 4
[[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
The list of edges between level set 3 and level set 4
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 3], [2, 1], [2, 2], [2, 3],
[3, 1], [3, 3], [3, 4], [4, 2], [4, 3]]
The number of times each edge appeared in a random walk
[100, 0, 0, 0, 100, 0, 0, 73, 27, 0, 0, 100, 27, 73]
For n=8, the matching data from our random walk is
********************************n = 8 ********************************
*********k = 1 to k = 2 *********
[8] ( 4 ) to [1, 7] ( 1 ) : 0.380
[8] ( 4 ) to [2, 6] ( 1 ) : 0.240
[8] ( 4 ) to [3, 5] ( 1 ) : 0.360
[8] ( 4 ) to [4, 4] ( 1 ) : 0.0200
*********k = 2 to k = 3 *********
[1, 7] ( 3 ) to [1, 1, 6] ( 2 ) : 0.650
[1, 7] ( 3 ) to [1, 2, 5] ( 3 ) : 0.350
[1, 7] ( 3 ) to [1, 3, 4] ( 3 ) : 0.000
[2, 6] ( 4 ) to [1, 1, 6] ( 2 ) : 0.000
[2, 6] ( 4 ) to [1, 2, 5] ( 3 ) : 0.000
[2, 6] ( 4 ) to [2, 2, 4] ( 2 ) : 0.790
[2, 6] ( 4 ) to [2, 3, 3] ( 2 ) : 0.210
[3, 5] ( 3 ) to [1, 2, 5] ( 3 ) : 0.000
[3, 5] ( 3 ) to [1, 3, 4] ( 3 ) : 0.210
[3, 5] ( 3 ) to [2, 3, 3] ( 2 ) : 0.790
[4, 4] ( 2 ) to [1, 3, 4] ( 3 ) : 0.790
[4, 4] ( 2 ) to [2, 2, 4] ( 2 ) : 0.210
*********k = 3 to k = 4 *********
[1, 1, 6] ( 3 ) to [1, 1, 1, 5] ( 2 ) : 0.540
[1, 1, 6] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.420
[1, 1, 6] ( 3 ) to [1, 1, 3, 3] ( 3 ) : 0.0400
[1, 2, 5] ( 3 ) to [1, 1, 1, 5] ( 2 ) : 0.460
[1, 2, 5] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.300
[1, 2, 5] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.240
[1, 3, 4] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.280
[1, 3, 4] ( 3 ) to [1, 1, 3, 3] ( 3 ) : 0.380
[1, 3, 4] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.340
[2, 2, 4] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.000
[2, 2, 4] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.000
[2, 2, 4] ( 3 ) to [2, 2, 2, 2] ( 1 ) : 1.00
[2, 3, 3] ( 2 ) to [1, 1, 3, 3] ( 3 ) : 0.580
[2, 3, 3] ( 2 ) to [1, 2, 2, 3] ( 4 ) : 0.420
*********k = 4 to k = 5 *********
[1, 1, 1, 5] ( 2 ) to [1, 1, 1, 1, 4] ( 2 ) : 0.670
[1, 1, 1, 5] ( 2 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.330
[1, 1, 2, 4] ( 3 ) to [1, 1, 1, 1, 4] ( 2 ) : 0.330
[1, 1, 2, 4] ( 3 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.0600
[1, 1, 2, 4] ( 3 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.190
[1, 1, 3, 3] ( 1 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.610
[1, 2, 2, 3] ( 2 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.000
[1, 2, 2, 3] ( 2 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.290
[2, 2, 2, 2] ( 1 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.520
*********k = 5 to k = 6 *********
[1, 1, 1, 1, 4] ( 2 ) to [1, 1, 1, 1, 1, 3] ( 2 ) : 0.000
[1, 1, 1, 1, 4] ( 2 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.0100
[1, 1, 1, 2, 3] ( 2 ) to [1, 1, 1, 1, 1, 3] ( 2 ) : 1.00
[1, 1, 1, 2, 3] ( 2 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.000
[1, 1, 2, 2, 2] ( 1 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.990
*********k = 6 to k = 7 *********
[1, 1, 1, 1, 1, 3] ( 1 ) to [1, 1, 1, 1, 1, 1, 2] ( 2 ) : 0.660
[1, 1, 1, 1, 2, 2] ( 1 ) to [1, 1, 1, 1, 1, 1, 2] ( 2 ) : 0.340
*********k = 7 to k = 8 *********
[1, 1, 1, 1, 1, 1, 2] ( 1 ) to [1, 1, 1, 1, 1, 1, 1, 1] ( 1 ) : 1.00

Is there a matching for n=8 between levels 3 and 4?
True
Level set 3
[[1, 1, 6], [1, 2, 5], [1, 3, 4], [2, 2, 4], [2, 3, 3]]
Level set 4
[[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
The list of edges between level set 3 and level set 4
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 3], [3, 4], [4, 2], [4, 3]]
The number of times each edge appeared in a random walk
[100, 0, 0, 0, 100, 0, 0, 73, 27, 0, 0, 100, 27, 73]
For n=8, the matching data from our random walk is
********************************n = 8 ********************************
*********k = 1 to k = 2 *********
[8] ( 4 ) to [1, 7] ( 1 ) : 0.380
[8] ( 4 ) to [2, 6] ( 1 ) : 0.240
[8] ( 4 ) to [3, 5] ( 1 ) : 0.360
[8] ( 4 ) to [4, 4] ( 1 ) : 0.0200
*********k = 2 to k = 3 *********
[1, 7] ( 3 ) to [1, 1, 6] ( 2 ) : 0.650
[1, 7] ( 3 ) to [1, 2, 5] ( 3 ) : 0.350
[1, 7] ( 3 ) to [1, 3, 4] ( 3 ) : 0.000
[2, 6] ( 4 ) to [1, 1, 6] ( 2 ) : 0.000
[2, 6] ( 4 ) to [1, 2, 5] ( 3 ) : 0.000
[2, 6] ( 4 ) to [2, 2, 4] ( 2 ) : 0.790
[2, 6] ( 4 ) to [2, 3, 3] ( 2 ) : 0.210
[3, 5] ( 3 ) to [1, 2, 5] ( 3 ) : 0.000
[3, 5] ( 3 ) to [1, 3, 4] ( 3 ) : 0.210
[3, 5] ( 3 ) to [2, 3, 3] ( 2 ) : 0.790
[4, 4] ( 2 ) to [1, 3, 4] ( 3 ) : 0.790
[4, 4] ( 2 ) to [2, 2, 4] ( 2 ) : 0.210
*********k = 3 to k = 4 *********
[1, 1, 6] ( 3 ) to [1, 1, 1, 5] ( 2 ) : 0.540
[1, 1, 6] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.420
[1, 1, 6] ( 3 ) to [1, 1, 3, 3] ( 3 ) : 0.0400
[1, 2, 5] ( 3 ) to [1, 1, 1, 5] ( 2 ) : 0.460
[1, 2, 5] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.300
[1, 2, 5] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.240
[1, 3, 4] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.280
[1, 3, 4] ( 3 ) to [1, 1, 3, 3] ( 3 ) : 0.380
[1, 3, 4] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.340
[2, 2, 4] ( 3 ) to [1, 1, 2, 4] ( 4 ) : 0.000
[2, 2, 4] ( 3 ) to [1, 2, 2, 3] ( 4 ) : 0.000
[2, 2, 4] ( 3 ) to [2, 2, 2, 2] ( 1 ) : 1.00
[2, 3, 3] ( 2 ) to [1, 1, 3, 3] ( 3 ) : 0.580
[2, 3, 3] ( 2 ) to [1, 2, 2, 3] ( 4 ) : 0.420
*********k = 4 to k = 5 *********
[1, 1, 1, 5] ( 2 ) to [1, 1, 1, 1, 4] ( 2 ) : 0.670
[1, 1, 1, 5] ( 2 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.330
[1, 1, 2, 4] ( 3 ) to [1, 1, 1, 1, 4] ( 2 ) : 0.330
[1, 1, 2, 4] ( 3 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.0600
[1, 1, 2, 4] ( 3 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.190
[1, 1, 3, 3] ( 1 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.610
[1, 2, 2, 3] ( 2 ) to [1, 1, 1, 2, 3] ( 4 ) : 0.000
[1, 2, 2, 3] ( 2 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.290
[2, 2, 2, 2] ( 1 ) to [1, 1, 2, 2, 2] ( 3 ) : 0.520
*********k = 5 to k = 6 *********
[1, 1, 1, 1, 4] ( 2 ) to [1, 1, 1, 1, 1, 3] ( 2 ) : 0.000
[1, 1, 1, 1, 4] ( 2 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.0100
[1, 1, 1, 2, 3] ( 2 ) to [1, 1, 1, 1, 1, 3] ( 2 ) : 1.00
[1, 1, 1, 2, 3] ( 2 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.000
[1, 1, 2, 2, 2] ( 1 ) to [1, 1, 1, 1, 2, 2] ( 3 ) : 0.990
*********k = 6 to k = 7 *********
[1, 1, 1, 1, 1, 3] ( 1 ) to [1, 1, 1, 1, 1, 1, 2] ( 2 ) : 0.660
[1, 1, 1, 1, 2, 2] ( 1 ) to [1, 1, 1, 1, 1, 1, 2] ( 2 ) : 0.340
*********k = 7 to k = 8 *********
[1, 1, 1, 1, 1, 1, 2] ( 1 ) to [1, 1, 1, 1, 1, 1, 1, 1] ( 1 ) : 1.00

SM-7-Matching

4314 days ago by MathFest