search

Libbum / elm-partition

Partition problem (number partitioning) solvers
https://package.elm-lang.org/packages/Libbum/elm-partition/latest/Partition
BSD 3-Clause "New" or "Revised" License
0 stars 1 forks source link

Possible bug in LDM #5

Closed Libbum closed 6 years ago

Libbum commented 6 years ago 
largestDifference [2,5,6,7,8,2,3,5] |> sumOfSets == (26,12)
greedy [2,5,6,7,8,2,3,5] |> sumOfSets == (18,20)

Unsure if this is just a case where LDM is no good or the implementation is bad.

Libbum commented 6 years ago

Definitely a bug.

Graph [Node 0 (2), Node 1 (5), Node 2 (6), Node 3 (7), Node 4 (8), Node 5 (2), Node 6 (3), Node 7 (5)] [Edge 7->6 (2), Edge 7->0 (0), Edge 5->4 (0), Edge 5->2 (1), Edge 4->3 (1), Edge 4->0 (0), Edge 2->1 (1)]

id 4 is connected outward to both 0 and 3, as well as inward by 5. id 3 has no outward connection. So somewhere we miss the 3->0 or 0->3 and instead place it on 4.

Libbum commented 6 years ago

No, the tree is fine, it's just not as straightforward in this case. colourGraph is not doing the correct red-black solution. Splitting like we do now is not correct.