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
| from sympy import *
from sympy.geometry import *
from sympy.plotting import *
from operator import itemgetter
import sys
from itertools import groupby
import itertools
from itertools import *
from sympy.matrices import *
import time
sys.setrecursionlimit(1000000)
avant = time.clock()
#p = [Point(45489772381, -736449623108), Point(45489772381, -736136770248), Point(455065875115, -736292552948), Point(454927507396, -736292552948), Point(454956086125, -736292552948), Point(454956086125, -736344480515), Point(454956086125, -736240625381), Point(454974435912, -736363148689), Point(454974435912, -736221957207), Point(454990378684, -736274957657), Point(454990378684, -736310148239)]
p = [Point(0,0), Point(8,0), Point(8,8), Point(5,2), Point(0,8), Point(12,7), Point(14,6)]
#p = [Point(0,0), Point(8,0), Point(8,8)]
seg = []
tri = []
merge = []
perm = []
def f2(seq):
checked = []
for e in seq:
if e not in checked:
checked.append(e)
return checked
combi_seg = list(itertools.combinations(range(0, len(p)), 2))
for result in combi_seg:
(i, j) = result
seg.extend([Segment(p[i] , p[j])])
combi_tria = list(itertools.combinations(range(0, len(p)), 3))
for result in combi_tria:
(i, j, k) = result
if Triangle(p[i], p[j], p[k]) == Segment(p[i], p[j]) or Triangle(p[i], p[j], p[k]) == Segment(p[i], p[k]) or Triangle(p[i], p[j], p[k]) == Segment(p[j], p[k]):
print "Similar"
else:
tri.extend([Triangle(p[i], p[j], p[k])])
merge.extend(p)
merge.extend(seg)
merge.extend(tri)
def creatematrix(i,j):
if (i == 0 and j == 0):
return "ensemb"
if (i == 0):
return j
if (j == 0):
return i
if (j<i):
return "0"
if i == j :
return "1"
for element in intersection(tri[i-1], tri[j-1]):
if element not in merge:
return "0"
return "1"
Matrice = Matrix(len(tri)+1, len(tri)+1, creatematrix)
print Matrice
def NewMatr2(matr):
mat = matr[:,:]
OP = 0
nbr = 0
puiss = int(round(matr.shape[1]/4))
power = -1
group = []
while puiss in range(0,matr.shape[1]):
results = []
power += 1
if group == []:
results.extend(list(itertools.combinations(range(1, matr.shape[1]), 2+puiss)))
else:
results.extend(list(itertools.combinations(group, 2+puiss)))
counter1 = 1
if results != []:
mat = mat.col_insert(mat.shape[1], 2*ones(mat.shape[0],1))
mat[0,mat.shape[1]-1] = "ind_" + str(puiss+2)
group = []
for result in results:
OP += 1
prod = []
prod.extend(list(itertools.combinations(result, 2)))
vall0 = 1
for elem in prod:
(x, y) = elem
vall0 = vall0 * mat[x,y]
print str(nbr) + " ensembles trouves sur " + str(OP) + " operations."
if (vall0 == 1):
if group == []:
group = list(result)
else:
group.extend(list(result))
vall1 = "t_" + str(result)
vall1 = vall1.replace("(", "")
vall1 = vall1.replace(", ", "_")
vall1 = vall1.replace(")", "")
try:
mat[counter1,mat.shape[1]-1] = vall1
except LookupError:
mat = mat.row_insert(mat.shape[1], zeros(1,mat.shape[1]))
mat[counter1,mat.shape[1]-1] = vall1
counter1 += 1
nbr += 1
group = f2(group)
group = sorted(group)
if mat[1,mat.shape[1]-1] == 2:
if (mat[1,mat.shape[1]-2] == 1) or (mat[1,mat.shape[1]-2] == 0):
mat.col_del(-1)
puiss = int(round(puiss/2))
else:
mat.col_del(-1)
return mat
else:
puiss += 1
return mat
M2 = NewMatr2(Matrice)
print M2
print M2.col(-1)
print 'Time execution : ',time.clock() - avant |
