Source code for titan_pylib.algorithm.permutation

 1from typing import Any
 2
 3

[docs]
 4class Permutation:
 5    """順列のライブラリです。"""
 6

[docs]
 7    @staticmethod
 8    def next_permutation(a: list[Any], l: int = 0, r: int = -1) -> bool:
 9        """列 ``a[l, r)`` を辞書順で次の順列にします。
10
11        Args:
12            a (list[Any])
13            l (int, optional)
14            r (int, optional)
15
16        Returns:
17            bool: 辞書順で次の順列が存在する場合は ``True`` 、存在しない場合は ``False`` を返します。
18        """
19        if r == -1:
20            r = len(a)
21        for i in range(r - 2, l - 1, -1):
22            if a[i] < a[i + 1]:
23                for j in range(r - 1, i, -1):
24                    if a[i] < a[j]:
25                        a[i], a[j] = a[j], a[i]
26                        p = i + 1
27                        q = r - 1
28                        while p < q:
29                            a[p], a[q] = a[q], a[p]
30                            p += 1
31                            q -= 1
32                        return True
33        return False

34

[docs]
35    @staticmethod
36    def prev_permutation(a: list[Any]) -> bool:
37        """列 ``a`` を辞書順で後の順列にします。
38
39        Args:
40            a (list[Any])
41
42        Returns:
43            bool: 辞書順で後の順列が存在する場合は ``True`` 、存在しない場合は ``False`` を返します。
44        """
45        l = 0
46        r = len(a)
47        for i in range(r - 2, l - 1, -1):
48            if a[i] > a[i + 1]:
49                for j in range(r - 1, i, -1):
50                    if a[i] > a[j]:
51                        a[i], a[j] = a[j], a[i]
52                        p = i + 1
53                        q = r - 1
54                        while p < q:
55                            a[p], a[q] = a[q], a[p]
56                            p += 1
57                            q -= 1
58                        return True
59        return False