c++ - 在 python/C++ 中快速生成用于排序矩阵的 key

Question

在 C++ 和 Python 中工作，我正在寻找矩阵函数 f (即，将矩阵作为输入并返回标量值的函数)，我可以使用它来生成用于对具有非负整数项的方矩阵/二维数组进行排序的键。

示例:我有一组三个(或更多)矩阵 A , B , C ... 与 f(A)=a , f(b)=b , f(C)=c ... 如果a<b<c ，程序返回列表 (A,B,C) .如果b<a<c程序返回列表 (B,A,C) .

为了确保这个排序过程是可靠的，我需要 f(A)=f(B)当且仅当 A==B .我正在寻找满足此条件并能快速计算最多 100 行和 100 列的矩阵的函数。

Answer 1

为了正确重载 < 运算符，您的关系必须是严格的弱顺序，这意味着，要成为严格顺序，它必须是不对称的和可传递的，并且它是弱顺序序，其不可比性关系必须是传递的。换句话说，这意味着如果您要比较三个矩阵 A、B 和 C，那么您的“<”不能同时具有 A

为了满足最后一个要求，只有当矩阵 A 与矩阵 B 相同时，A 和 B 的比较才必须返回“相等”，我们知道只有当 A 的每个元素都相等时才为真到 B 的每个元素。考虑到这一点，我们必须使用矩阵中的每个元素来确保只有当矩阵 A 与矩阵 B 相同时，A 和 B 才返回“相等”。

考虑以下函数:

1. If matrix A has less rows than matrix B (return A is less than B)

2. If matrix B has less rows than matrix A (return B is less than A)

3. If they have the same number of rows, continue

4. If matrix A has less cols than matrix B (return A is less than B)

5. If matrix B has less cols than matrix A (return B is less than A)

6. If they have the same number of cols, continue

7. Iterate through every element in A

   i. Compare the integer value at each position and the integer value of B at that same position

   ii. If element at A < element at B (return A is less than B)

   iii. If element at B < element at A (return B is less than A)

8. If all entries are equal (return A = B)

这意味着在最坏的情况下，函数将不得不检查矩阵中的每个元素，但为了正确重载 < 运算符，别无选择

在所有其他情况下，函数将在元素存在差异时立即返回，大多数情况下会相当快