stau.space
My omnium-gatherom of scripts and source code.
1from sage.all import *
2
3
4def F(a, b):
5 sequence = [2 * a, b]
6 while sequence[-1] > 1:
7 sequence.append(-sequence[-2] % sequence[-1])
8 sequence[0] /= 2
9 if sequence[-1] == 0:
10 sequence = sequence[:-1]
11 return sequence
12
13
14def sliding_window_sum(vals: list[int]) -> list[int]:
15 ret = []
16 for idx, i in enumerate(vals[1:]):
17 if idx == len(vals) - 2:
18 ret.append(i + vals[0])
19 else:
20 ret.append(i + vals[idx + 2])
21 return ret
22
23
24def subdivide_at(struct: list[int], i: int) -> list[int]:
25 x = 0
26 if i >= len(struct) - 1:
27 x = struct[-1] + struct[0]
28 else:
29 x = struct[i] + struct[i + 1]
30 return insert_at(list(struct), i + 2, x)
31
32
33def subdivide_everywhere(struct: tuple) -> list[tuple]:
34 ret = []
35 for i in range(1, len(struct)):
36 ret.append(tuple(subdivide_at(struct, i)))
37 return ret
38
39
40def find_all_subdivisions(struct: tuple, until: int) -> list[tuple]:
41 lst: list[tuple] = [struct]
42 for i in range(len(struct), until):
43 s = set()
44 for a in lst:
45 for variation in subdivide_everywhere(a):
46 s.add(variation)
47 lst = list(s)
48 return lst
49
50
51def find_all_subdivisions(struct: tuple, until: int) -> list[tuple]:
52 lst: list[tuple] = [struct]
53 for i in range(len(struct), until):
54 s = set()
55 for a in lst:
56 for variation in subdivide_everywhere(a):
57 s.add(variation)
58 lst = list(s)
59 return lst
60
61
62def divides(a: int, b: int) -> bool:
63 return a % b == 0
64
65
66def choose(n: int, k: int) -> int:
67 if k > n: return 0
68 if k == 0: return 1
69 if k == 1: return n
70 return factorial(n) / (factorial(n - k) * factorial(k))
71
72
73def ballot(k: int, l: int) -> int:
74 return (k - l + 1) / (k + 1) * binomial(k + l, k)
75
76
77def callot(n: int, k: int) -> int:
78 return ballot(n - 1, n - k)
79
80
81def insert_at(arr: list, i: int, x) -> list:
82
83 return arr[0:i] + [x] + arr[i:]
84
85
86def bident(a: int, b: int) -> list[int]:
87 f_seq = [a, b]
88 while f_seq[-2] != f_seq[-1] and f_seq[-1] != 1:
89 f_seq.append(-f_seq[-2] % f_seq[-1])
90 return f_seq
91
92
93def catalan(n: int) -> int:
94 return factorial(2 * n) / (factorial(n + 1) * factorial(n))
95
96
97def mset_cardinality(n: int, l: int) -> int:
98 return choose(n + l - 1, l)
99
100
101def is_arithmetical_graph(struct) -> bool:
102 G = struct[0].adjacency_matrix()
103 r = struct[1]
104 er = enumerate(r)
105
106 def is_divisible(i):
107 return sum(map(lambda j: j[1] * G[i[0]][j[0]], er)) % i[1] == 0
108
109 return gcd(r) == 1 and all(is_divisible(i) for i in er)
110
111
112def pairwise_sum(v1, v2):
113 return list(map(lambda x: x[0] + x[1], zip(v1, v2)))
114
115
116def create_hasse(x):
117 divs = divisors(x)[::-1]
118 s = defaultdict(list)
119 for i in range(len(divs)):
120 curr = divs[i]
121 for j in divs[i + 1:]:
122 if curr % j == 0:
123 s[curr].append(j)
124
125 def helper(div, cons):
126 for c in cons:
127 num = c[0]
128 lst = c[1]
129 full = c[2]
130 if full or div == num:
131 continue
132 else:
133 if div % num == 0:
134 lst.append(div)
135 full = len(lst) >= 3
136 return cons
137
138 consideration = []
139 for div in divs[::-1]:
140 consideration.append((div, [], False))
141 consideration = helper(div, consideration)
142
143 def index_ocurrences(elems, lst):
144 indexes = []
145 for elem in elems:
146 if elem in lst:
147 indexes.append(lst.index(elem))
148 return indexes
149
150 G = Graph()
151 for idx, i in enumerate(consideration):
152 lst = i[1][:len(factor(x))]
153 indexes = []
154 for index in index_ocurrences(lst, divs[::-1]):
155 indexes.append((idx, index))
156
157 G.add_vertex(idx)
158 G.add_edges(indexes)
159 return G
160
161
162def characteristic(n: int, i: int) -> list[int]:
163 ret = [0] * n
164 ret[i] = 1
165 return ret
166
167
168def W(G: Graph, u: int, r: list[int]) -> set[int]:
169 V = G.vertices()
170 s = set()
171
172 for w in V:
173 for path in G.all_paths(u, w):
174 if r[path[-1]] != 0 and all(r[vertex] == 0
175 for vertex in path[1:-1]):
176 s.add(w)
177
178 return s
179
180
181def algorithm_1(G: Graph, r: int, order: list[int]):
182 r = vector(r)
183
184 for i, u in enumerate(order, 1):
185 e_u = vector(characteristic(len(r), u))
186 r = r + sum(e_u * r[w] for w in W(G, u, r))
187
188 return r
189
190
191def cycle(n: int) -> Graph:
192 if n == 2:
193 G = Graph(multiedges=True)
194 G.vertices(0, 1)
195 G.add_edges([[0, 1], [0, 1], [0, 1]])
196 return G
197 G = Graph(multiedges=True)
198 length = range(n)
199 G.vertices(length)
200 G.add_cycle(list(length))
201 return G
202
203
204def doubled_edge_cycle(n: int) -> Graph:
205 assert n > 1
206 G = cycle(n)
207 G.add_edge(0, 1)
208 return G