fork download
copy 
  1. import numpy as np
  2. from typing import List, Set, Tuple, Union
  3.  
  4. def _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:
  5.     """Return a deterministic Generator from seed/int/Generator."""
  6.     if isinstance(rng, np.random.Generator):
  7.         return rng
  8.     return np.random.default_rng(0 if rng is None else int(rng))
  9.  
  10.  
  11. def _has_no_digit_two(x: int) -> bool:
  12.     """True iff the base‑3 representation of x contains no digit 2."""
  13.     while x:
  14.         if x % 3 == 2:
  15.             return False
  16.         x //= 3
  17.     return True
  18.  
  19.  
  20. def _conflict_sets(val: int, cur: Set[int]) -> Tuple[Set[int], Set[int]]:
  21.     """
  22.     Return two sets of conflicts with `val` against the current set `cur`:
  23.       outer – members that together with `val` would be the two outer terms
  24.                of a 3‑AP whose middle is already in `cur`.
  25.       middle – members that would be the middle term of a 3‑AP with `val`
  26.                as one outer term.
  27.     """
  28.     outer = set()
  29.     middle = set()
  30.     for y in cur:
  31.         s = val + y
  32.         if s % 2 == 0 and (s // 2) in cur:
  33.             outer.add(y)                 # y is the other outer term
  34.         if (2 * val - y) in cur:
  35.             middle.add(y)                # y is the other outer term, val middle
  36.         if (2 * y - val) in cur:
  37.             outer.add(y)                 # y is middle, val outer
  38.     return outer, middle
  39.  
  40.  
  41. def _weighted_score(val: int, cur: Set[int],
  42.                     w_outer: int = 1, w_mid: int = 2) -> int:
  43.     """Score = w_outer·|outer| + w_mid·|middle|; lower is better."""
  44.     outer, middle = _conflict_sets(val, cur)
  45.     return w_outer * len(outer) + w_mid * len(middle)
  46.  
  47.  
  48. def heuristic(n: int,
  49.               rng: Union[None, int, np.random.Generator] = None) -> List[int]:
  50.     """
  51.     Build a large 3‑AP‑free subset of {1,…,n}.
  52.     1. Initialise with the “Cantor” set (no ternary digit 2).
  53.     2. Perform a bounded local search that swaps out up to three conflicting
  54.        elements for a missing element, using a score that penalises middle‑role
  55.        conflicts twice as much as outer‑role conflicts.
  56.     Returns the final set as a sorted list.
  57.     """
  58.     if n <= 0:
  59.         return []
  60.  
  61.     rng = _make_rng(rng)
  62.  
  63.     # -----------------------------------------------------------------
  64.     # 1. Base Cantor construction
  65.     # -----------------------------------------------------------------
  66.     S: Set[int] = {i for i in range(1, n + 1) if _has_no_digit_two(i)}
  67.     missing: List[int] = [i for i in range(1, n + 1) if i not in S]
  68.     rng.shuffle(missing)                     # deterministic tie‑breaker
  69.  
  70.     # -----------------------------------------------------------------
  71.     # 2. Local improvement (swap &le;3 conflicting members for one missing)
  72.     # -----------------------------------------------------------------
  73.     budget = int(4 * np.sqrt(n)) + 200        # number of attempts
  74.     attempts = 0
  75.     idx = 0
  76.  
  77.     while attempts < budget and missing:
  78.         x = missing[idx % len(missing)]
  79.         idx += 1
  80.         attempts += 1
  81.  
  82.         # compute conflicts of x with current set
  83.         outer, middle = _conflict_sets(x, S)
  84.         all_conf = outer | middle
  85.  
  86.         if not all_conf:
  87.             # x fits for free &ndash; just add it
  88.             S.add(x)
  89.             missing.remove(x)
  90.             attempts = 0
  91.             continue
  92.  
  93.         # limit to at most three conflicting elements; otherwise skip
  94.         if len(all_conf) > 3:
  95.             continue
  96.  
  97.         # enumerate all non‑empty subsets of size &le;3 of the conflicting set
  98.         conf_list = list(all_conf)
  99.         best_combo = None
  100.         for r in range(1, min(3, len(conf_list)) + 1):
  101.             # small numbers &rarr; simple bit‑mask enumeration
  102.             for mask in range(1 << len(conf_list)):
  103.                 if bin(mask).count("1") != r:
  104.                     continue
  105.                 combo = tuple(conf_list[i] for i in range(len(conf_list))
  106.                                if (mask >> i) & 1)
  107.                 temp = S.difference(combo)
  108.                 if not _conflict_sets(x, temp)[0] and not _conflict_sets(x, temp)[1]:
  109.                     best_combo = combo
  110.                     break
  111.             if best_combo is not None:
  112.                 break
  113.  
  114.         if best_combo is None:
  115.             continue
  116.  
  117.         # perform the swap
  118.         for y in best_combo:
  119.             S.remove(y)
  120.             missing.append(y)
  121.         S.add(x)
  122.         missing.remove(x)
  123.         attempts = 0
  124.  
  125.         # after a successful swap, greedily insert any newly free numbers
  126.         filler = True
  127.         while filler:
  128.             filler = False
  129.             for y in list(missing):
  130.                 if not _conflict_sets(y, S)[0] and not _conflict_sets(y, S)[1]:
  131.                     S.add(y)
  132.                     missing.remove(y)
  133.                     filler = True
  134.                     attempts = 0
  135.  
  136.     # final deterministic ordering
  137.     return S
  138.  
  139. x = heuristic(82)
  140. print(x)
  141. print(len(x))
Success #stdin #stdout 0.86s 41440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{1, 3, 6, 7, 10, 12, 22, 25, 27, 30, 31, 36, 39, 46, 58, 63, 64, 73, 74, 78, 79, 81}
22
https://ideone.com/ESFseu
language:
Python 3 (python  3.12)
created:
2 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!