cycle_memo

ソースコード

from titan_pylib.algorithm.cycle_memo import CycleMemo

view on github

展開済みコード

 1# from titan_pylib.algorithm.cycle_memo import CycleMemo
 2from typing import Callable, TypeVar, Generic, Hashable
 3
 4T = TypeVar("T", bound=Hashable)
 5
 6
 7class CycleMemo(Generic[T]):
 8
 9    def __init__(self, initial: T, move_to: Callable[[T], T]) -> None:
10        history: list[T] = []
11        memo: set[T] = set()
12        now: T = initial
13        while now not in memo:
14            history.append(now)
15            memo.add(now)
16            now = move_to(now)
17        cycle_start = history.index(now)
18        cycle_len = len(history) - cycle_start
19        pre = history[:cycle_start]
20        cycle = history[cycle_start:]
21        self.cycle_start = cycle_start
22        self.cycle_len = cycle_len
23        self.pre = pre
24        self.cycle = cycle
25
26    def kth(self, k: int) -> T:
27        if k < self.cycle_start:
28            return self.pre[k]
29        k -= self.cycle_start
30        k %= self.cycle_len
31        return self.cycle[k]

仕様

class CycleMemo(initial: T, move_to: Callable[[T], T])[source]

Bases: Generic[T]

kth(k: int) → T[source]