nekolib/algo/
tortoise_hare.rs

1//! 周期検出。
2
3/// 周期検出を行う。
4///
5/// 与えられた $x\_0$ と $f$ を用いて $x\_i = f(x\_{i-1})$ ($i > 0$) として
6/// 定義される列 $\\{x\_i\\}\_{i=0}\^\\infty$ の周期検出を行う。
7/// $x\_{\\mu} = x\_{\\mu+\\lambda}$ なる最小の $(\\mu, \\lambda)$ を返す。
8///
9/// # Requirements
10/// $f$ は参照透過である。
11///
12/// # Notes
13/// 共通の $f$ に対して、異なる複数の $x\_0$ から周期検出を行いたい場合は、
14/// この関数を複数回呼ぶよりも高速なアルゴリズムがあると思われる。
15/// ある $x\_0$ での出力が $(\\mu, \\lambda)$ であれば、
16/// $x\_i$ ($1\\le i\< \\mu$) での出力は $(\\mu-i, \\lambda)$、
17/// $x\_i$ ($\\mu\\le i<\\mu+\\lambda$) での出力は $(0, \\lambda)$ とわかる。
18/// さらに、これら $\\mu+\\lambda$ 個以外の $x\'$ についても、
19/// $f\^i(x\')$ がこれらのいずれかと等しくなる $i$ が存在すれば、
20/// $\\Theta(\\mu)$ 回の $f$ の呼び出しで $x\', f(x\'), \\dots, f\^{i-1}(x\')$ の出力もわかるはず。
21///
22/// # Complexity
23/// $\\Theta(\\mu+\\lambda)$ 回の $f$ の呼び出しを行う。
24///
25/// # Examples
26/// ```
27/// use nekolib::algo::cycle_mu_lambda;
28///
29/// // 3, 9, 11, 9, 11, ...
30/// assert_eq!(cycle_mu_lambda(3, |x| x * x % 14), (1, 2));
31/// // 2, 6, 4, 5, 1, 3, 2, ...
32/// assert_eq!(cycle_mu_lambda(2, |x| x * 3 % 7), (0, 6));
33/// ```
34///
35/// ```
36/// use nekolib::algo::cycle_mu_lambda;
37///
38/// assert_eq!(cycle_mu_lambda(0, |x| x), (0, 1));
39/// ```
40pub fn cycle_mu_lambda<T, F>(x0: T, f: F) -> (usize, usize)
41where
42    T: Eq + Clone,
43    F: Fn(T) -> T,
44{
45    let mut tor = f(x0.clone());
46    let mut har = f(tor.clone());
47
48    while tor != har {
49        tor = f(tor);
50        har = f(f(har));
51    }
52
53    let mut tor = x0;
54    let mut mu = 0;
55    while tor != har {
56        tor = f(tor);
57        har = f(har);
58        mu += 1;
59    }
60
61    let mut lambda = 1;
62    har = f(tor.clone());
63    while tor != har {
64        har = f(har);
65        lambda += 1;
66    }
67
68    (mu, lambda)
69}
70
71/// $n$ 項目を求める。
72///
73/// 与えられた $x\_0$ と $f$ を用いて $x\_i = f(x\_{i-1})$ ($i > 0$) として
74/// 定義される列 $\\{x\_i\\}\_{i=0}\^\\infty$ の $n$ 項目を求める。
75///
76/// # Requirements
77/// $f$ は参照透過である。
78///
79/// # Complexuty
80/// $x\_{\\mu} = x\_{\\mu+\\lambda}$ なる最小の $(\\mu, \\lambda)$
81/// に対し、$O(\\min\\{n, \\mu+\\lambda\\})$ time.
82///
83/// # Examples
84/// ```
85/// use nekolib::algo::cycle_nth;
86///
87/// let x0 = 0;
88/// let f = |x| (x + 1) % 100; // (mu, lambda) = (0, 100)
89/// assert_eq!(cycle_nth(x0, f, 0), 0);
90/// assert_eq!(cycle_nth(x0, f, 99), 99);
91/// assert_eq!(cycle_nth(x0, f, 100), 0);
92/// assert_eq!(cycle_nth(x0, f, 1000), 0);
93/// assert_eq!(cycle_nth(x0, f, 10_usize.pow(9)), 0);
94///
95/// let x0 = -10;
96/// let f = |x| (x + 1) % 100; // (mu, lambda) = (10, 100)
97/// assert_eq!(cycle_nth(x0, f, 0), -10);
98/// assert_eq!(cycle_nth(x0, f, 99), 89);
99/// assert_eq!(cycle_nth(x0, f, 100), 90);
100/// assert_eq!(cycle_nth(x0, f, 1000), 90);
101/// assert_eq!(cycle_nth(x0, f, 10_usize.pow(9)), 90);
102/// ```
103pub fn cycle_nth<T, F>(x0: T, f: F, n: usize) -> T
104where
105    T: Eq + Clone,
106    F: Fn(T) -> T,
107{
108    if n == 0 {
109        return x0;
110    }
111    if n == 1 {
112        return f(x0);
113    }
114
115    let mut tor = f(x0.clone());
116    let mut har = f(tor.clone());
117    let mut i = 2;
118    while i + 2 <= n && tor != har {
119        tor = f(tor);
120        har = f(f(har));
121        i += 2;
122    }
123    if i == n {
124        return har;
125    }
126    if i + 1 == n {
127        return f(har);
128    }
129
130    let mut tor = x0.clone();
131    let mut mu = 0;
132    while tor != har {
133        tor = f(tor);
134        har = f(har);
135        mu += 1;
136    }
137
138    let mut lambda = 1;
139    har = f(tor.clone());
140    while tor != har {
141        har = f(har);
142        lambda += 1;
143    }
144
145    let n = if n <= mu { n } else { mu + (n - mu) % lambda };
146    let mut x = x0;
147    for _ in 0..n {
148        x = f(x);
149    }
150    x
151}
nekolib/algo/tortoise_hare.rs

nekolib/algo/
tortoise_hare.rs
