permutation¶
ソースコード¶
from titan_pylib.algorithm.permutation import Permutation
展開済みコード¶
1# from titan_pylib.algorithm.permutation import Permutation
2from typing import Any
3
4
5class Permutation:
6 """順列のライブラリです。"""
7
8 @staticmethod
9 def next_permutation(a: list[Any], l: int = 0, r: int = -1) -> bool:
10 """列 ``a[l, r)`` を辞書順で次の順列にします。
11
12 Args:
13 a (list[Any])
14 l (int, optional)
15 r (int, optional)
16
17 Returns:
18 bool: 辞書順で次の順列が存在する場合は ``True`` 、存在しない場合は ``False`` を返します。
19 """
20 if r == -1:
21 r = len(a)
22 for i in range(r - 2, l - 1, -1):
23 if a[i] < a[i + 1]:
24 for j in range(r - 1, i, -1):
25 if a[i] < a[j]:
26 a[i], a[j] = a[j], a[i]
27 p = i + 1
28 q = r - 1
29 while p < q:
30 a[p], a[q] = a[q], a[p]
31 p += 1
32 q -= 1
33 return True
34 return False
35
36 @staticmethod
37 def prev_permutation(a: list[Any]) -> bool:
38 """列 ``a`` を辞書順で後の順列にします。
39
40 Args:
41 a (list[Any])
42
43 Returns:
44 bool: 辞書順で後の順列が存在する場合は ``True`` 、存在しない場合は ``False`` を返します。
45 """
46 l = 0
47 r = len(a)
48 for i in range(r - 2, l - 1, -1):
49 if a[i] > a[i + 1]:
50 for j in range(r - 1, i, -1):
51 if a[i] > a[j]:
52 a[i], a[j] = a[j], a[i]
53 p = i + 1
54 q = r - 1
55 while p < q:
56 a[p], a[q] = a[q], a[p]
57 p += 1
58 q -= 1
59 return True
60 return False