1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
//! Brute-force algorithm for finding column minima.
//!
//! The functions here are mostly meant to be used for testing
//! correctness of the SMAWK implementation.
//!
//! **Note: this module is only available if you enable the `ndarray`
//! Cargo feature.**
use ndarray::{Array2, ArrayView1};
/// Compute lane minimum by brute force.
///
/// This does a simple scan through the lane (row or column).
#[inline]
pub fn lane_minimum<T: Ord>(lane: ArrayView1<'_, T>) -> usize {
lane.iter()
.enumerate()
.min_by_key(|&(idx, elem)| (elem, idx))
.map(|(idx, _)| idx)
.expect("empty lane in matrix")
}
/// Compute row minima by brute force in O(*mn*) time.
///
/// This function implements a simple brute-force approach where each
/// matrix row is scanned completely. This means that the function
/// works on all matrices, not just Monge matrices.
///
/// # Examples
///
/// ```
/// let matrix = ndarray::arr2(&[[4, 2, 4, 3],
/// [5, 3, 5, 3],
/// [5, 3, 3, 1]]);
/// assert_eq!(smawk::brute_force::row_minima(&matrix),
/// vec![1, 1, 3]);
/// ```
///
/// # Panics
///
/// It is an error to call this on a matrix with zero columns.
pub fn row_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> {
matrix.rows().into_iter().map(lane_minimum).collect()
}
/// Compute column minima by brute force in O(*mn*) time.
///
/// This function implements a simple brute-force approach where each
/// matrix column is scanned completely. This means that the function
/// works on all matrices, not just Monge matrices.
///
/// # Examples
///
/// ```
/// let matrix = ndarray::arr2(&[[4, 2, 4, 3],
/// [5, 3, 5, 3],
/// [5, 3, 3, 1]]);
/// assert_eq!(smawk::brute_force::column_minima(&matrix),
/// vec![0, 0, 2, 2]);
/// ```
///
/// # Panics
///
/// It is an error to call this on a matrix with zero rows.
pub fn column_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> {
matrix.columns().into_iter().map(lane_minimum).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use ndarray::arr2;
#[test]
fn brute_force_1x1() {
let matrix = arr2(&[[2]]);
let minima = vec![0];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_2x1() {
let matrix = arr2(&[
[3], //
[2],
]);
let minima = vec![0, 0];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_1x2() {
let matrix = arr2(&[[2, 1]]);
let minima = vec![1];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_2x2() {
let matrix = arr2(&[
[3, 2], //
[2, 1],
]);
let minima = vec![1, 1];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_3x3() {
let matrix = arr2(&[
[3, 4, 4], //
[3, 4, 4],
[2, 3, 3],
]);
let minima = vec![0, 0, 0];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_4x4() {
let matrix = arr2(&[
[4, 5, 5, 5], //
[2, 3, 3, 3],
[2, 3, 3, 3],
[2, 2, 2, 2],
]);
let minima = vec![0, 0, 0, 0];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
#[test]
fn brute_force_5x5() {
let matrix = arr2(&[
[3, 2, 4, 5, 6],
[2, 1, 3, 3, 4],
[2, 1, 3, 3, 4],
[3, 2, 4, 3, 4],
[4, 3, 2, 1, 1],
]);
let minima = vec![1, 1, 1, 1, 3];
assert_eq!(row_minima(&matrix), minima);
assert_eq!(column_minima(&matrix.reversed_axes()), minima);
}
}
|
