stau.space
My omnium-gatherom of scripts and source code.
1{
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 4,
6 "id": "480599a9-9f15-4d40-ba36-cddfac8cd436",
7 "metadata": {},
8 "outputs": [],
9 "source": [
10 "def SumDQ(A, p, r):\n",
11 " if (p == r):\n",
12 " return A[p - 1]\n",
13 " q = (p + r) // 2\n",
14 " s_l = SumDQ(A, p, q)\n",
15 " s_r = SumDQ(A, q + 1, r)\n",
16 " return s_l + s_r"
17 ]
18 },
19 {
20 "cell_type": "code",
21 "execution_count": 6,
22 "id": "fffc8fce-95ac-4741-bbd2-0f428eea8c14",
23 "metadata": {},
24 "outputs": [],
25 "source": [
26 "def permutations(iterable, r=None):\n",
27 " # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC\n",
28 " # permutations(range(3)) → 012 021 102 120 201 210\n",
29 "\n",
30 " pool = tuple(iterable)\n",
31 " n = len(pool)\n",
32 " r = n if r is None else r\n",
33 " if r > n:\n",
34 " return\n",
35 "\n",
36 " indices = list(range(n))\n",
37 " cycles = list(range(n, n-r, -1))\n",
38 " yield tuple(pool[i] for i in indices[:r])\n",
39 "\n",
40 " while n:\n",
41 " for i in reversed(range(r)):\n",
42 " cycles[i] -= 1\n",
43 " if cycles[i] == 0:\n",
44 " indices[i:] = indices[i+1:] + indices[i:i+1]\n",
45 " cycles[i] = n - i\n",
46 " else:\n",
47 " j = cycles[i]\n",
48 " indices[i], indices[-j] = indices[-j], indices[i]\n",
49 " yield tuple(pool[i] for i in indices[:r])\n",
50 " break\n",
51 " else:\n",
52 " return"
53 ]
54 },
55 {
56 "cell_type": "code",
57 "execution_count": 22,
58 "id": "e68027af-3256-452d-911c-85d8c3b35bf7",
59 "metadata": {},
60 "outputs": [],
61 "source": [
62 "def id(x): return x"
63 ]
64 },
65 {
66 "cell_type": "code",
67 "execution_count": null,
68 "id": "a0299a59-3de4-4701-9296-e07988f8df61",
69 "metadata": {},
70 "outputs": [],
71 "source": [
72 "import collections\n",
73 "\n",
74 "def is_costas(lst: collections.deque[int]) -> bool:\n",
75 " if len(set(lst)) != len(lst):\n",
76 " return False\n",
77 "\n",
78 " l = len(lst)\n",
79 " for h in range(1,l):\n",
80 " diffs = []\n",
81 " for i in range(h - 1, l - 1):\n",
82 " diffs.append(lst[(h + i) % l] - lst[i])\n",
83 " if len(diffs) != len(set(diffs)):\n",
84 " return False\n",
85 " return True"
86 ]
87 },
88 {
89 "cell_type": "code",
90 "execution_count": 4,
91 "id": "3aaf8ac1-3511-4c20-934c-916245dd8d25",
92 "metadata": {},
93 "outputs": [
94 {
95 "name": "stdout",
96 "output_type": "stream",
97 "text": [
98 "False\n"
99 ]
100 }
101 ],
102 "source": [
103 "print(is_costas([1,2,3]))"
104 ]
105 },
106 {
107 "cell_type": "code",
108 "execution_count": 56,
109 "id": "89241374-c3d9-4006-a84c-0d8e98f71a82",
110 "metadata": {},
111 "outputs": [],
112 "source": [
113 "def costas_nxn(i: int) -> list[tuple[list[int], bool]]:\n",
114 " return list(filter(lambda x: x[1], [(lst, is_costas(lst)) for lst in permutations(range(1, i + 1))]))"
115 ]
116 },
117 {
118 "cell_type": "code",
119 "execution_count": null,
120 "id": "374fa23d-62fe-4932-9839-a56c329e1347",
121 "metadata": {},
122 "outputs": [
123 {
124 "name": "stdout",
125 "output_type": "stream",
126 "text": [
127 "1.0\n",
128 "2.0\n",
129 "4.0\n",
130 "16.0\n",
131 "41.0\n",
132 "104.0\n",
133 "93.0\n",
134 "159.0\n",
135 "342.0\n",
136 "655.0\n"
137 ]
138 }
139 ],
140 "source": [
141 "for i in range(2, 20):\n",
142 " print(len(costas_nxn(i)) / 2.0)"
143 ]
144 },
145 {
146 "cell_type": "code",
147 "execution_count": 31,
148 "id": "5234cde1-e0d4-4fda-9ee8-199f93cef470",
149 "metadata": {},
150 "outputs": [
151 {
152 "data": {
153 "text/plain": [
154 "[True, True]"
155 ]
156 },
157 "execution_count": 31,
158 "metadata": {},
159 "output_type": "execute_result"
160 }
161 ],
162 "source": [
163 "list(filter(id, [True,False,True]))"
164 ]
165 },
166 {
167 "cell_type": "code",
168 "execution_count": 49,
169 "id": "5ee066a1-199e-48ca-abc1-db53e1c6080c",
170 "metadata": {},
171 "outputs": [],
172 "source": [
173 "import collections\n",
174 "\n",
175 "def is_costas(lst: list[int]) -> bool:\n",
176 " if len(set(lst)) != len(lst):\n",
177 " return False\n",
178 " \n",
179 " n = len(lst)\n",
180 " for k in range(1, n):\n",
181 " diffs = []\n",
182 " for i in range(0, n - k):\n",
183 " a = lst[(i + k) % n]\n",
184 " b = lst[i]\n",
185 " result = a - b\n",
186 " diffs.append(result)\n",
187 " if len(diffs) != len(set(diffs)):\n",
188 " return False\n",
189 " return True"
190 ]
191 },
192 {
193 "cell_type": "code",
194 "execution_count": 50,
195 "id": "e3bc84ac-a4d0-43b2-b25b-1bff3e48c4af",
196 "metadata": {},
197 "outputs": [
198 {
199 "name": "stdout",
200 "output_type": "stream",
201 "text": [
202 "True\n"
203 ]
204 }
205 ],
206 "source": [
207 "print(is_costas([1,3,2]))"
208 ]
209 },
210 {
211 "cell_type": "code",
212 "execution_count": 2,
213 "id": "0d87444b-8c2a-40d7-9269-e31b4b6947d3",
214 "metadata": {},
215 "outputs": [],
216 "source": [
217 "def is_costas(lst: list[int]) -> bool:\n",
218 " if len(set(lst)) != len(lst):\n",
219 " return False\n",
220 " \n",
221 " n = len(lst)\n",
222 " flag = False\n",
223 " for k in range(1, n):\n",
224 " diffs = [False] * (2 * n)\n",
225 " if flag:\n",
226 " continue\n",
227 " for i in range(0, n - k):\n",
228 " a = lst[(i + k) % n]\n",
229 " b = lst[i]\n",
230 " result = a - b + n\n",
231 " if diffs[result]:\n",
232 " return False\n",
233 " else:\n",
234 " diffs[result] = True\n",
235 "\n",
236 " flag = diffs[result]\n",
237 " return flag"
238 ]
239 },
240 {
241 "cell_type": "code",
242 "execution_count": 3,
243 "id": "1da9d034-be34-4810-a3bc-ca2d0ff277be",
244 "metadata": {},
245 "outputs": [
246 {
247 "name": "stdout",
248 "output_type": "stream",
249 "text": [
250 "False\n"
251 ]
252 }
253 ],
254 "source": [
255 "print(is_costas([1, 2, 3,4]))"
256 ]
257 },
258 {
259 "cell_type": "code",
260 "execution_count": 3,
261 "id": "b6bea522-2054-42bc-a449-0040cbad6d20",
262 "metadata": {},
263 "outputs": [],
264 "source": [
265 "def build_all_naive(lst: list[int], x: int) -> list[int]:\n",
266 " out = []\n",
267 " for i in range(len(lst) + 1):\n",
268 " lst2 = list(lst).copy()\n",
269 " lst2.insert(i, x)\n",
270 " if is_costas(lst2):\n",
271 " out.append(lst2)\n",
272 " return out\n",
273 " "
274 ]
275 },
276 {
277 "cell_type": "code",
278 "execution_count": 89,
279 "id": "7bbbbf79-0ee1-4e7e-b781-871afd330d63",
280 "metadata": {},
281 "outputs": [
282 {
283 "name": "stdout",
284 "output_type": "stream",
285 "text": [
286 "[1, 2]\n",
287 "2 [3, 1, 2]\n",
288 "1 [4, 3, 1, 2]\n",
289 "2 [4, 3, 5, 1, 2]\n",
290 "1 [6, 4, 3, 5, 1, 2]\n",
291 "1 [6, 4, 3, 5, 1, 7, 2]\n",
292 "3 [6, 4, 3, 8, 5, 1, 7, 2]\n",
293 "2 [6, 4, 3, 8, 5, 9, 1, 7, 2]\n",
294 "2 [10, 6, 4, 3, 8, 5, 9, 1, 7, 2]\n",
295 "2 [10, 6, 4, 3, 8, 11, 5, 9, 1, 7, 2]\n",
296 "3 [10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
297 "3 [13, 10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
298 "4 [14, 13, 10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
299 "2 [14, 13, 10, 6, 15, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
300 "4 [16, 14, 13, 10, 6, 15, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
301 "3 [16, 14, 13, 10, 6, 15, 17, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
302 "5 [16, 14, 13, 10, 6, 15, 17, 18, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
303 "7 [16, 14, 13, 10, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
304 "6 [16, 14, 13, 20, 10, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
305 "6 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
306 "5 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
307 "5 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
308 "7 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
309 "6 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
310 "7 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
311 "5 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
312 "8 [16, 14, 24, 13, 20, 28, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
313 "7 [29, 16, 14, 24, 13, 20, 28, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n"
314 ]
315 }
316 ],
317 "source": [
318 "lst = [1, 2]\n",
319 "print(lst)\n",
320 "for i in range(3, 30):\n",
321 " lsts = build_all(lst, i)\n",
322 " print(len(lsts), lsts[0])\n",
323 " lst = lsts[0]"
324 ]
325 },
326 {
327 "cell_type": "code",
328 "execution_count": 30,
329 "id": "0d6e7633-4e64-4ab9-8668-3c50e0179c59",
330 "metadata": {},
331 "outputs": [
332 {
333 "name": "stdout",
334 "output_type": "stream",
335 "text": [
336 "2 2\n",
337 "3 4\n",
338 "4 8\n",
339 "5 20\n",
340 "6 50\n",
341 "7 130\n",
342 "8 362\n",
343 "9 1104\n",
344 "10 3614\n"
345 ]
346 }
347 ],
348 "source": [
349 "prev = set([(1,2), (2,1)])\n",
350 "counts2 = []\n",
351 "for i in range(2, 11):\n",
352 " print(i, len(prev))\n",
353 " counts2.append(prev)\n",
354 " nxt = [build_all_naive(lst, i + 1) for lst in prev]\n",
355 " prev = set()\n",
356 " for lsts in nxt:\n",
357 " for lst in lsts:\n",
358 " prev.add(tuple(lst))"
359 ]
360 },
361 {
362 "cell_type": "code",
363 "execution_count": 35,
364 "id": "dbf6794e-1237-476b-a733-611cf5ce9107",
365 "metadata": {},
366 "outputs": [
367 {
368 "data": {
369 "text/plain": [
370 "[[[4, 5, 2, 1, 3], [4, 2, 5, 1, 3]],\n",
371 " [[5, 1, 3, 4, 2], [1, 3, 4, 2, 5]],\n",
372 " [[5, 2, 3, 1, 4], [2, 3, 5, 1, 4], [2, 3, 1, 5, 4]],\n",
373 " [[4, 3, 5, 1, 2], [4, 3, 1, 5, 2], [4, 3, 1, 2, 5]],\n",
374 " [[3, 1, 5, 2, 4], [3, 1, 2, 5, 4]],\n",
375 " [[5, 2, 4, 3, 1], [2, 4, 3, 1, 5]],\n",
376 " [[5, 2, 1, 3, 4], [2, 5, 1, 3, 4], [2, 1, 5, 3, 4]],\n",
377 " [[4, 5, 1, 3, 2], [4, 1, 5, 3, 2], [4, 1, 3, 2, 5]]]"
378 ]
379 },
380 "execution_count": 35,
381 "metadata": {},
382 "output_type": "execute_result"
383 }
384 ],
385 "source": [
386 "nxt"
387 ]
388 },
389 {
390 "cell_type": "code",
391 "execution_count": 37,
392 "id": "d551e2cb-0a40-479e-b72b-95fbc13571be",
393 "metadata": {},
394 "outputs": [
395 {
396 "name": "stdout",
397 "output_type": "stream",
398 "text": [
399 "20\n",
400 "{(2, 1, 5, 3, 4), (4, 3, 1, 5, 2), (4, 2, 5, 1, 3), (5, 1, 3, 4, 2), (2, 5, 1, 3, 4), (4, 5, 1, 3, 2), (2, 4, 3, 1, 5), (4, 1, 5, 3, 2), (3, 1, 5, 2, 4), (2, 3, 5, 1, 4), (4, 3, 1, 2, 5), (4, 3, 5, 1, 2), (5, 2, 4, 3, 1), (1, 3, 4, 2, 5), (3, 1, 2, 5, 4), (4, 1, 3, 2, 5), (5, 2, 3, 1, 4), (5, 2, 1, 3, 4), (4, 5, 2, 1, 3), (2, 3, 1, 5, 4)}\n"
401 ]
402 }
403 ],
404 "source": [
405 "print(len(prev))\n",
406 "print(prev)"
407 ]
408 },
409 {
410 "cell_type": "code",
411 "execution_count": 12,
412 "id": "e480bc98-5188-44e1-a9db-940d42cc5c11",
413 "metadata": {},
414 "outputs": [
415 {
416 "name": "stdout",
417 "output_type": "stream",
418 "text": [
419 "2 2\n",
420 "3 4\n",
421 "4 12\n",
422 "5 44\n",
423 "6 176\n",
424 "7 788\n",
425 "8 3936\n",
426 "9 23264\n",
427 "10 152112\n"
428 ]
429 }
430 ],
431 "source": [
432 "counts = []\n",
433 "for i in range(2, 11):\n",
434 " s = set()\n",
435 " for lst in permutations(range(1, i + 1)):\n",
436 " if is_costas(lst):\n",
437 " s.add(lst)\n",
438 " counts.append(s)\n",
439 " print(i, len(s))"
440 ]
441 },
442 {
443 "cell_type": "code",
444 "execution_count": 8,
445 "id": "0d74a5bc-226e-419e-8261-afe7984404d7",
446 "metadata": {},
447 "outputs": [
448 {
449 "name": "stderr",
450 "output_type": "stream",
451 "text": [
452 "IOPub data rate exceeded.\n",
453 "The Jupyter server will temporarily stop sending output\n",
454 "to the client in order to avoid crashing it.\n",
455 "To change this limit, set the config variable\n",
456 "`--ServerApp.iopub_data_rate_limit`.\n",
457 "\n",
458 "Current values:\n",
459 "ServerApp.iopub_data_rate_limit=1000000.0 (bytes/sec)\n",
460 "ServerApp.rate_limit_window=3.0 (secs)\n",
461 "\n"
462 ]
463 },
464 {
465 "ename": "IndexError",
466 "evalue": "list index out of range",
467 "output_type": "error",
468 "traceback": [
469 "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
470 "\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)",
471 "Cell \u001b[0;32mIn[8], line 2\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m10\u001b[39m):\n\u001b[0;32m----> 2\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43mcounts\u001b[49m\u001b[43m[\u001b[49m\u001b[43mi\u001b[49m\u001b[43m]\u001b[49m \u001b[38;5;241m-\u001b[39m counts2[i])\n",
472 "\u001b[0;31mIndexError\u001b[0m: list index out of range"
473 ]
474 }
475 ],
476 "source": [
477 "for i in range(10):\n",
478 " print(counts[i] - counts2[i])"
479 ]
480 },
481 {
482 "cell_type": "code",
483 "execution_count": 32,
484 "id": "506d6572-2cdb-4a5d-a262-154a673917b2",
485 "metadata": {},
486 "outputs": [
487 {
488 "data": {
489 "text/plain": [
490 "{(1, 3, 4, 2),\n",
491 " (2, 1, 3, 4),\n",
492 " (2, 3, 1, 4),\n",
493 " (2, 4, 3, 1),\n",
494 " (3, 1, 2, 4),\n",
495 " (4, 1, 3, 2),\n",
496 " (4, 2, 1, 3),\n",
497 " (4, 3, 1, 2)}"
498 ]
499 },
500 "execution_count": 32,
501 "metadata": {},
502 "output_type": "execute_result"
503 }
504 ],
505 "source": [
506 "counts2[2]"
507 ]
508 },
509 {
510 "cell_type": "code",
511 "execution_count": 31,
512 "id": "2d5537f2-d7a6-4873-b679-568ff3409f88",
513 "metadata": {},
514 "outputs": [
515 {
516 "data": {
517 "text/plain": [
518 "{(1, 2, 4, 3),\n",
519 " (1, 3, 4, 2),\n",
520 " (1, 4, 2, 3),\n",
521 " (2, 1, 3, 4),\n",
522 " (2, 3, 1, 4),\n",
523 " (2, 4, 3, 1),\n",
524 " (3, 1, 2, 4),\n",
525 " (3, 2, 4, 1),\n",
526 " (3, 4, 2, 1),\n",
527 " (4, 1, 3, 2),\n",
528 " (4, 2, 1, 3),\n",
529 " (4, 3, 1, 2)}"
530 ]
531 },
532 "execution_count": 31,
533 "metadata": {},
534 "output_type": "execute_result"
535 }
536 ],
537 "source": [
538 "counts[2]"
539 ]
540 },
541 {
542 "cell_type": "code",
543 "execution_count": 16,
544 "id": "b0560c92-81d3-415f-a92a-0f629dd251f8",
545 "metadata": {},
546 "outputs": [
547 {
548 "data": {
549 "text/plain": [
550 "{(1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)}"
551 ]
552 },
553 "execution_count": 16,
554 "metadata": {},
555 "output_type": "execute_result"
556 }
557 ],
558 "source": [
559 "counts2[1]"
560 ]
561 },
562 {
563 "cell_type": "code",
564 "execution_count": 19,
565 "id": "ad91bac9-6641-46ce-8d5c-8f96242ad611",
566 "metadata": {},
567 "outputs": [
568 {
569 "name": "stdout",
570 "output_type": "stream",
571 "text": [
572 "[1, 'a', 'b', 'c']\n",
573 "['a', 1, 'b', 'c']\n",
574 "['a', 'b', 1, 'c']\n",
575 "['a', 'b', 'c', 1]\n"
576 ]
577 }
578 ],
579 "source": [
580 "for i in range(4):\n",
581 " lst = ['a','b','c']\n",
582 " lst.insert(i, 1)\n",
583 " print(lst)"
584 ]
585 },
586 {
587 "cell_type": "code",
588 "execution_count": 26,
589 "id": "7d6705e6-380a-45ed-b486-032fa5d39dcb",
590 "metadata": {},
591 "outputs": [
592 {
593 "data": {
594 "text/plain": [
595 "[[4, 1, 3, 2], [1, 3, 4, 2]]"
596 ]
597 },
598 "execution_count": 26,
599 "metadata": {},
600 "output_type": "execute_result"
601 }
602 ],
603 "source": [
604 "build_all_naive((1,3,2), 4)"
605 ]
606 },
607 {
608 "cell_type": "code",
609 "execution_count": null,
610 "id": "53f40627-5ba1-4acd-aa63-2125e8a47455",
611 "metadata": {},
612 "outputs": [],
613 "source": []
614 }
615 ],
616 "metadata": {
617 "kernelspec": {
618 "display_name": "Python 3 (ipykernel)",
619 "language": "python",
620 "name": "python3"
621 },
622 "language_info": {
623 "codemirror_mode": {
624 "name": "ipython",
625 "version": 3
626 },
627 "file_extension": ".py",
628 "mimetype": "text/x-python",
629 "name": "python",
630 "nbconvert_exporter": "python",
631 "pygments_lexer": "ipython3",
632 "version": "3.12.3"
633 }
634 },
635 "nbformat": 4,
636 "nbformat_minor": 5
637}