You can find the following algorithm:
1. detect all existing units: `n` units
2. create a `n x n` matrix `M` such that the same rows and columns show
the corresponding unit. put all elements of the main diagonal of the
matrix to `1`.
3. put the specified value in the input into the corresponding row and column.
4. put zero for the transpose of the row and the column in step 3.
5. put `-1` for all other elements
Now, based on `M` you can easily find the biggest unit:
5.1 candidate_maxs <-- Find columns with only one non-zero positive element
not_max <-- []
6. while len(candidate_max)> 1:
a. take a pair <i, l> and find a column h such that both (i, h)
and (l, h) are known, i.e., they are positive.
If M[i, h] > M[l, h]:
remove_item <-- l
Else:
remove_item <-- i
candidate_max.remove(remove_item)
not_max.append(remove_item)
b. if cannot find such a pair, find a pair <i, l>: i from
candidate_max and h from not_max with the same property.
If M[i, h] < M[l, h]:
candidate_max.remove(i)
not_max.append(i)
biggest_unit <-- The only element of candidate_max
By finding the biggest unit, you can order others based on their value in the corresponding row of the biggest_unit.
7. while there is `-1` value in the row `biggest_unit` on column `j`:
`(biggest_unit, j)`
a. find a non-identity and non-zero positive element in (column `j`
and row `k`) or (row `j` and column `k`), i.e., `(k,j)` or `(j, k)`, such that `(biggest_unit, k)` is strictly
positive and non-identity. Then, calculate the missing value
based on the found equivalences.
b. if there is not such a row, continue the loop with another `-1`
unit element.
8. sort units based on their column value in `biggest_unit` row in
ascending order.
However, the time complexity of the algorithm is Theta(n^2) that n is the number of units (if you implement the loop on step 6 wisely!).
Example
Input 1
km = 1000 m
m = 100 cm
cm = 10 mm
Solution:
km m cm mm
km 1 1000 -1 -1
m 0 1 100 -1
cm -1 0 1 10
mm -1 -1 0 1
M = [1 1000 -1 -1
0 1 100 -1
-1 0 1 10
-1 -1 0 1]
===> 6. `biggest_unit` <--- km (column 1)
7.1 Find first `-1` in the first row and column 3: (1,3)
Find strictly positive value in row 2 such that (1,2) is strictly
positive and non-identity. So, the missing value of `(1,3)` must be
`1000 * 100 = 100000`.
7.2 Find the second `-1` in the first row and column 4: (1,4)
Find strictly positive value in row 3 such that (1,3) is strictly
positive and non-identity. So, the missing value of `(1,4)` must be
`100000 * 10 = 1000000`.
The loop is finished here and we have:
M = [1 1000 100000 1000000
0 1 100 -1
-1 0 1 10
-1 -1 0 1]
Now you can sort the elements of the first row in ascending order.
Input 2
km = 100000 cm
km = 1000000 mm
m = 1000 mm
Solution:
km m cm mm
km 1 -1 100000 1000000
m -1 1 -1 1000
cm 0 -1 1 -1
mm 0 0 -1 1
M = [1 -1 100000 1000000
-1 1 -1 1000
0 -1 1 -1
0 0 -1 1]
===>
6.1 candidate_max = [1, 2]
6.2 Compare them on column 4 and remove 2
biggest_unit <-- column 1
And by going forward on step 7,
Find first `-1` in the first row and column 2: (1,2)
Find a strictly positive and non-identity value in row 2:(1,4)
So, the missing value of `(1,2)` must be `1000000 / 1000 = 1000`.
In sum, we have:
M = [1 1000 100000 1000000
-1 1 -1 1000
0 -1 1 -1
0 0 -1 1]
Now you can sort the elements of the first row in ascending order (step 8).
