-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathramsey_5_5.py
145 lines (143 loc) · 3.65 KB
/
ramsey_5_5.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#!/usr/bin/env python
###
#
# @Name : RamseyNumberGraph/ramsey_5_5.py
# @Version : 1.0
# @Programmer : Max
# @Date : 2019-07-15
# @Released under : https://github.com/BaseMax/RamseyNumberGraph/blob/master/LICENSE
# @Repository : https://github.com/RamseyNumberGraph/RamseyNumber
#
###
import math
import random
import sys
limitc=0
sys.setrecursionlimit(15000)
def R(art, *shapes):
print("R(" + ", ".join(map(str,shapes)) + ") ?= " + str(art))
vertices=list()
lenShapes=len(shapes)
for i in range(1, art+1):
vertices.append(i)
print("Art: " + str(art) + "k" )
print("Shapes: " + "k, ".join(map(str,shapes)) + ("k" if lenShapes > 0 else "") + " (" + str(lenShapes) +
")")
print("Vertices of the graph: " + str(vertices))
e=list()
edgesSize=math.factorial(art) / ( math.factorial(art-lenShapes) * math.factorial(lenShapes) )
print(edgesSize)
edges=list()
l=0
for i in range(art):
for j in range(i+1, art):
edges.append( [i+1, j+1, None] )
l+=1
print("Edges of the graph: " + str(edges))
# while True:
#limit=20
#limitc=0
def check():
#global limit
global limitc
limitc+=1
if limitc == 10000:
print("\nLimit.....")
sys.exit()
for edge in edges:
edge[2]=random.randint(0, lenShapes-1)
print("\n")
print("Colorize edges of the graph: " + str(edges))
# for shape in shapes:
# print(shape)
def found(i, j):
# for edge in edges:
for index, edge in enumerate(edges):
# if edge[0] == i and edge[1] == j:
if (edge[0] == i and edge[1] == j) or (edge[0] == j and edge[1] == i):
# print(edge[0])
return edge[2]
# return index
return None
# print( found(1, 2) )
q=0
items=list()
print("start...\n")
for i in range(art):
for j in range(i+1, art):
for l in range(j+1, art):
for w in range(l+1, art):
for e in range(w+1, art):
items.append( list() )
items[q].append( (i+1, j+1) )
items[q].append( (i+1, l+1) )
items[q].append( (i+1, w+1) )
items[q].append( (i+1, e+1) )
items[q].append( (j+1, l+1) )
items[q].append( (j+1, w+1) )
items[q].append( (j+1, e+1) )
items[q].append( (l+1, w+1) )
items[q].append( (l+1, e+1) )
items[q].append( (w+1, e+1) )
q+=1
'''
items.append( list() )
# e.g: shapes[0] is 3 1 / 3
items[q].append( (i+1, j+1) )
# 2 / 3
items[q].append( (i+1, l+1) )
# 3 / 3
items[q].append( (j+1, l+1) )
q+=1
'''
# print(items) print("\n")
print(".....\n")
sameColor=0
for item in items:
print(item)
checkContinue=True
result=True
color=None
for item_child in item:
# print(item_child)
if color is None:
color=found(item_child[0], item_child[1])
# print(color)
sys.stdout.write(str(color))
continue
else:
tcolor=found(item_child[0], item_child[1])
sys.stdout.write(" " + str(tcolor))
# print(" " + str(tcolor))
if tcolor is not color:
# print(str(color) + " => Break")
sys.stdout.write(" Break")
checkContinue=False
break
# We has some edges with a (one) color.
if checkContinue is True:
sys.stdout.write(" OK")
sameColor+=1
check()
return
print("")
# return break
#else:
#print("Colorize edges of the graph: " + str(edges)) check() break
# return continue check() print(item[0]) print(item[1]) print(item[2])
print("===> " + str(sameColor))
# while True: break
if sameColor is 0:
print("Done")
print("Colorize edges of the graph: " + str(edges))
sys.exit()
return False
#limitCurrent+=1
#if limitCurrent >= limit:
# print("Limit...")
# sys.exit()
check()
check()
r=R(10, 5, 5)
#r=R(43, 5, 5)
print(r)