Coverage for moptipyapps / order1d / distances.py: 32%

1"""Some examples for distance metrics.""" 

2 

3from typing import Final 

4 

5import numba # type: ignore 

6import numpy as np 

7from moptipy.utils.nputils import DEFAULT_BOOL 

8 

9 

10@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False) 

11def swap_distance(p1: np.ndarray, p2: np.ndarray) -> int: 

12 """ 

13 Compute the swap distance between two permutations `p1` and `p1`. 

14 

15 This is the minimum number of swaps required to translate `p1` to `p2` and 

16 vice versa. This function is symmatric. 

17 

18 An upper bound for the number of maximum number of swaps that could be 

19 required is the length of the permutation. This upper bound can be derived 

20 from Selection Sort. Imagine that I want to translate the array `p1` to 

21 `p2`. I go through `p1` from beginning to end. If, at index `i`, I find 

22 the right element (`p1[i] == p2[i]`), then I do nothing. If not, then the 

23 right element must come at some index `j>i` (because all elements before I 

24 already have fixed). So I swap `p1[i]` with `p1[j]`. Now `p1[i] == p2[i]` 

25 and I increment `i`. Once I arrive at the end of `p1`, it must hold that 

26 `all(p1[i] == p2[i])`. At the same time, I have performed at most one swap 

27 at each index during the iteration. Hence, I can never need more swaps 

28 than the arrays are long. 

29 

30 :param p1: the first permutation 

31 :param p2: the second permutation 

32 :return: the swap distance, always between `0` and `len(p1)` 

33 

34 >>> swap_distance(np.array([0, 1, 2, 3]), np.array([3, 1, 2, 0])) 

35 1 

36 >>> swap_distance(np.array([0, 1, 2]), np.array([0, 1, 2])) 

37 0 

38 >>> swap_distance(np.array([1, 0, 2]), np.array([0, 1, 2])) 

39 1 

40 >>> swap_distance(np.array([0, 1, 2]), np.array([1, 0, 2])) 

41 1 

42 >>> swap_distance(np.array([0, 1, 2]), np.array([2, 0, 1])) 

43 2 

44 >>> swap_distance(np.array([2, 0, 1]), np.array([0, 1, 2])) 

45 2 

46 >>> swap_distance(np.arange(10), np.array([4, 8, 1, 5, 9, 3, 6, 0, 7, 2])) 

47 7 

48 >>> swap_distance(np.array([4, 8, 1, 5, 9, 3, 6, 0, 7, 2]), np.arange(10)) 

49 7 

50 """ 

51 n: Final[int] = len(p1) 

52 x: np.ndarray = p2[np.argsort(p1)] 

53 unchecked: np.ndarray = np.ones(n, DEFAULT_BOOL) 

54 result: int = 0 

55 

56 for i in range(n): 

57 if unchecked[i]: 

58 result += 1 

59 unchecked[i] = False 

60 j = x[i] 

61 while j != i: 

62 unchecked[j] = False 

63 j = x[j] 

64 

65 return n - result