Incorrect handling of integer partitions when vector has negative values #18
Open
Description
There are many issues in the logic that assumes positive values. For example, there are many places where we check if the first element is zero. The vector is first sorted, thus when we have negative values, this check not valid. This causes strange behavior as we see below.
comboGeneral(-5:0, repetition = TRUE, constraintFun = "sum",
comparisonFun = "==",
limitConstraints = -5)
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] -5 0 0 0 0 0
[2,] -4 -1 0 0 0 0
[3,] -3 -2 0 0 0 0
[4,] -3 -1 -1 0 0 0
[5,] -2 -2 -1 0 0 0
[6,] -2 -1 -1 -1 0 0
[7,] -1 -1 -1 -1 -1 0The above example should look only have 5 columns. Observe:
comboGeneral(5:0, repetition = TRUE, constraintFun = "sum",
comparisonFun = "==",
limitConstraints = 5)
[,1] [,2] [,3] [,4] [,5]
[1,] 0 0 0 0 5
[2,] 0 0 0 1 4
[3,] 0 0 0 2 3
[4,] 0 0 1 1 3
[5,] 0 0 1 2 2
[6,] 0 1 1 1 2
[7,] 1 1 1 1 1Lastly, there is a significant performance penalty by all of those incorrect assumptions. The general algorithm (which is still efficient) is utilized in these situations when a much more efficient algorithm could be used.
## Optimized algorithm
system.time(comboGeneral(0:60, repetition = TRUE, constraintFun = "sum",
comparisonFun = "==",
limitConstraints = 60))
user system elapsed
0.086 0.061 0.147
## General algorithm
system.time(comboGeneral(0:-60, repetition = TRUE, constraintFun = "sum",
comparisonFun = "==",
limitConstraints = -60))
user system elapsed
0.718 0.348 1.066Metadata
Assignees
Labels
No labels