fork download
copy 
  1. import numpy as np
  2.  
  3. def get_3ap_counts(n):
  4.     """
  5.     計算 1 到 n 之間，每個數字參與了多少個 3-AP (x, y, z)
  6.     其中 x, y, z 都在 1~n 範圍內，且 x + z = 2y
  7.     """
  8.     counts = {i: 0 for i in range(1, n + 1)}
  9.  
  10.     # 我們遍歷所有可能的「中間項」y
  11.     for y in range(1, n + 1):
  12.         # 計算最大的公差 step (受限於邊界)
  13.         max_step = min(y - 1, n - y)
  14.  
  15.         for step in range(1, max_step + 1):
  16.             x = y - step # 第一項
  17.             z = y + step # 第三項
  18.  
  19.             # 找到一組 AP (x, y, z)，將這三個數的計數都 +1
  20.             counts[x] += 1
  21.             counts[y] += 1
  22.             counts[z] += 1
  23.  
  24.     return counts
  25.  
  26. def heuristic(n, rng=None):
  27.     if rng is None or isinstance(rng, int):
  28.         rng = np.random.default_rng(rng)
  29.  
  30.     S = set()
  31.     candidates = list(range(1, n+1))
  32.  
  33.     # 1. 先取得每個數字的 AP 參與次數 Dictionary
  34.     ap_counts_dict = get_3ap_counts(n)
  35.  
  36.     # 2. 印出你要求的 Dictionary
  37.  
  38.  
  39.     # 3. 根據這個 count 來排序 candidates
  40.     # 參與 AP 次數越少的數字 (通常是邊界數字)，越不容易造成衝突，排在前面優先選取
  41.     candidates.sort(key=lambda x: ap_counts_dict[x])
  42.     print(f"每個數字參與 3-AP 的次數 (前20個範例): {dict(list(ap_counts_dict.items()))} ...")
  43.     # print(f"Sorted candidates (pby AP involvement): {candidates}")
  44.  
  45.     for x in candidates:
  46.         # 檢查 x 加入後是否會形成 3-AP
  47.         # 條件：是否存在 y 在 S 中，使得 (y, x) 能組成 AP 的兩端，且第三點也在 S 中
  48.         # 因為 x 是新加入的，它可能是第一項(x, y, 2y-x)、中間項(y, x, 2x-y) 或第三項(2y-x, y, x)
  49.  
  50.         conflict = False
  51.         for y in S:
  52.             # Case 1: x 是中間項 -> x, y 已知，檢查 2x-y 是否在 S
  53.             if 2*x - y in S:
  54.                 conflict = True
  55.                 break
  56.             # Case 2: x 是端點 -> x, y 已知，檢查 2y-x (另一端) 是否在 S
  57.             if 2*y - x in S:
  58.                 conflict = True
  59.                 break
  60.             # Case 3: x, y 是兩端 -> 檢查 (x+y)/2 (中間) 是否在 S
  61.             if (x + y) % 2 == 0:
  62.                 if (x + y) // 2 in S:
  63.                     conflict = True
  64.                     break
  65.  
  66.         if not conflict:
  67.             S.add(x)
  68.  
  69.     return S
  70.  
  71. # 執行並印出結果
  72. result_set = heuristic(500)
  73. print(f"Size of subset: {len(result_set)}")
Success #stdin #stdout 1.12s 41092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
每個數字參與 3-AP 的次數 (前20個範例): {1: 249, 2: 250, 3: 251, 4: 252, 5: 253, 6: 254, 7: 255, 8: 256, 9: 257, 10: 258, 11: 259, 12: 260, 13: 261, 14: 262, 15: 263, 16: 264, 17: 265, 18: 266, 19: 267, 20: 268, 21: 269, 22: 270, 23: 271, 24: 272, 25: 273, 26: 274, 27: 275, 28: 276, 29: 277, 30: 278, 31: 279, 32: 280, 33: 281, 34: 282, 35: 283, 36: 284, 37: 285, 38: 286, 39: 287, 40: 288, 41: 289, 42: 290, 43: 291, 44: 292, 45: 293, 46: 294, 47: 295, 48: 296, 49: 297, 50: 298, 51: 299, 52: 300, 53: 301, 54: 302, 55: 303, 56: 304, 57: 305, 58: 306, 59: 307, 60: 308, 61: 309, 62: 310, 63: 311, 64: 312, 65: 313, 66: 314, 67: 315, 68: 316, 69: 317, 70: 318, 71: 319, 72: 320, 73: 321, 74: 322, 75: 323, 76: 324, 77: 325, 78: 326, 79: 327, 80: 328, 81: 329, 82: 330, 83: 331, 84: 332, 85: 333, 86: 334, 87: 335, 88: 336, 89: 337, 90: 338, 91: 339, 92: 340, 93: 341, 94: 342, 95: 343, 96: 344, 97: 345, 98: 346, 99: 347, 100: 348, 101: 349, 102: 350, 103: 351, 104: 352, 105: 353, 106: 354, 107: 355, 108: 356, 109: 357, 110: 358, 111: 359, 112: 360, 113: 361, 114: 362, 115: 363, 116: 364, 117: 365, 118: 366, 119: 367, 120: 368, 121: 369, 122: 370, 123: 371, 124: 372, 125: 373, 126: 374, 127: 375, 128: 376, 129: 377, 130: 378, 131: 379, 132: 380, 133: 381, 134: 382, 135: 383, 136: 384, 137: 385, 138: 386, 139: 387, 140: 388, 141: 389, 142: 390, 143: 391, 144: 392, 145: 393, 146: 394, 147: 395, 148: 396, 149: 397, 150: 398, 151: 399, 152: 400, 153: 401, 154: 402, 155: 403, 156: 404, 157: 405, 158: 406, 159: 407, 160: 408, 161: 409, 162: 410, 163: 411, 164: 412, 165: 413, 166: 414, 167: 415, 168: 416, 169: 417, 170: 418, 171: 419, 172: 420, 173: 421, 174: 422, 175: 423, 176: 424, 177: 425, 178: 426, 179: 427, 180: 428, 181: 429, 182: 430, 183: 431, 184: 432, 185: 433, 186: 434, 187: 435, 188: 436, 189: 437, 190: 438, 191: 439, 192: 440, 193: 441, 194: 442, 195: 443, 196: 444, 197: 445, 198: 446, 199: 447, 200: 448, 201: 449, 202: 450, 203: 451, 204: 452, 205: 453, 206: 454, 207: 455, 208: 456, 209: 457, 210: 458, 211: 459, 212: 460, 213: 461, 214: 462, 215: 463, 216: 464, 217: 465, 218: 466, 219: 467, 220: 468, 221: 469, 222: 470, 223: 471, 224: 472, 225: 473, 226: 474, 227: 475, 228: 476, 229: 477, 230: 478, 231: 479, 232: 480, 233: 481, 234: 482, 235: 483, 236: 484, 237: 485, 238: 486, 239: 487, 240: 488, 241: 489, 242: 490, 243: 491, 244: 492, 245: 493, 246: 494, 247: 495, 248: 496, 249: 497, 250: 498, 251: 498, 252: 497, 253: 496, 254: 495, 255: 494, 256: 493, 257: 492, 258: 491, 259: 490, 260: 489, 261: 488, 262: 487, 263: 486, 264: 485, 265: 484, 266: 483, 267: 482, 268: 481, 269: 480, 270: 479, 271: 478, 272: 477, 273: 476, 274: 475, 275: 474, 276: 473, 277: 472, 278: 471, 279: 470, 280: 469, 281: 468, 282: 467, 283: 466, 284: 465, 285: 464, 286: 463, 287: 462, 288: 461, 289: 460, 290: 459, 291: 458, 292: 457, 293: 456, 294: 455, 295: 454, 296: 453, 297: 452, 298: 451, 299: 450, 300: 449, 301: 448, 302: 447, 303: 446, 304: 445, 305: 444, 306: 443, 307: 442, 308: 441, 309: 440, 310: 439, 311: 438, 312: 437, 313: 436, 314: 435, 315: 434, 316: 433, 317: 432, 318: 431, 319: 430, 320: 429, 321: 428, 322: 427, 323: 426, 324: 425, 325: 424, 326: 423, 327: 422, 328: 421, 329: 420, 330: 419, 331: 418, 332: 417, 333: 416, 334: 415, 335: 414, 336: 413, 337: 412, 338: 411, 339: 410, 340: 409, 341: 408, 342: 407, 343: 406, 344: 405, 345: 404, 346: 403, 347: 402, 348: 401, 349: 400, 350: 399, 351: 398, 352: 397, 353: 396, 354: 395, 355: 394, 356: 393, 357: 392, 358: 391, 359: 390, 360: 389, 361: 388, 362: 387, 363: 386, 364: 385, 365: 384, 366: 383, 367: 382, 368: 381, 369: 380, 370: 379, 371: 378, 372: 377, 373: 376, 374: 375, 375: 374, 376: 373, 377: 372, 378: 371, 379: 370, 380: 369, 381: 368, 382: 367, 383: 366, 384: 365, 385: 364, 386: 363, 387: 362, 388: 361, 389: 360, 390: 359, 391: 358, 392: 357, 393: 356, 394: 355, 395: 354, 396: 353, 397: 352, 398: 351, 399: 350, 400: 349, 401: 348, 402: 347, 403: 346, 404: 345, 405: 344, 406: 343, 407: 342, 408: 341, 409: 340, 410: 339, 411: 338, 412: 337, 413: 336, 414: 335, 415: 334, 416: 333, 417: 332, 418: 331, 419: 330, 420: 329, 421: 328, 422: 327, 423: 326, 424: 325, 425: 324, 426: 323, 427: 322, 428: 321, 429: 320, 430: 319, 431: 318, 432: 317, 433: 316, 434: 315, 435: 314, 436: 313, 437: 312, 438: 311, 439: 310, 440: 309, 441: 308, 442: 307, 443: 306, 444: 305, 445: 304, 446: 303, 447: 302, 448: 301, 449: 300, 450: 299, 451: 298, 452: 297, 453: 296, 454: 295, 455: 294, 456: 293, 457: 292, 458: 291, 459: 290, 460: 289, 461: 288, 462: 287, 463: 286, 464: 285, 465: 284, 466: 283, 467: 282, 468: 281, 469: 280, 470: 279, 471: 278, 472: 277, 473: 276, 474: 275, 475: 274, 476: 273, 477: 272, 478: 271, 479: 270, 480: 269, 481: 268, 482: 267, 483: 266, 484: 265, 485: 264, 486: 263, 487: 262, 488: 261, 489: 260, 490: 259, 491: 258, 492: 257, 493: 256, 494: 255, 495: 254, 496: 253, 497: 252, 498: 251, 499: 250, 500: 249} ...
Size of subset: 64
https://ideone.com/cvPQD6
language:
Python 3 (python  3.12)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!