I have read this paper and I actually found it interesting.
This is an attempt to implement the proposed algorithm. I would like to know:
- Is my algorithm correct by what is discribed in the paper?
- Is my algorithm easy to understand?
Here is my little program
// Based on http://www.ijcai.org/Proceedings/16/Papers/053.pdf
//
// The paper uses two matrices, but I decided to "join" them into 1 matrix of
// tuples. Things are easier this way (isn't it a valid reason?).
//
// A matrix is a list of lists, but...
//
// It is not like you would expect.
//
// Each inner list represents a column, not a row!
//
// A "standard" visualization of a matrix is:
// column1 column2 column3
// row1 (1, 90) (1, 10) (0, 90)
// row2 (0, 0) (1, 100) (1, 40)
// row3 (0, 10) (1, 80) (1, 100)
//
// In my program it is seen as:
// row1 row2 row3
// colum1 (1, 90) (0, 0) (0, 10)
// colum2 (1, 10) (1, 100) (1, 80)
// colum3 (0, 90) (1, 40) (1, 100)
//
// It is made this way because, in this specific case, it is easier to go
// recursively in a list of columns.
let exampleMatrix = [
[1, 90; 0, 0; 0, 10]
[1, 10; 1, 100; 1, 80]
[0, 90; 1, 40; 1, 100]
]
let optimalColumnOrderOf matrix =
let sumProbabilities column =
column
|> List.map (fun (_, q) -> q)
|> List.reduce (+)
let comparator column1 column2 =
let sum1 = sumProbabilities column1
let sum2 = sumProbabilities column2
sum2 - sum1
matrix
|> List.sortWith comparator
let thereIsZeroProbabilityIn column =
List.exists (fun (_, q) -> q = 0) column
let optimalRowOrderOf column =
let comparator (_, q1) (_, q2) =
q2 - q1
column
|> List.sortWith comparator
let isColumnFeaseble column =
let thereIsZeroIn c =
c
|> optimalRowOrderOf
|> List.exists (fun (n, _) -> n = 0)
if thereIsZeroProbabilityIn column then false
else
column
|> List.filter (fun (_, q) -> q < 100)
|> thereIsZeroIn
|> not
let isMatrixFeaseble matrix =
matrix
|> optimalColumnOrderOf
|> List.exists isColumnFeaseble
[<EntryPoint>]
let main argv =
printf "%O" (isMatrixFeaseble exampleMatrix)
System.Console.ReadKey() |> ignore
0