Multisets under constraint with integer vectors

[jwood000]

When trying to replicate the results of this question: Remove repeating numbers from for loop, I found an issue with how version 2.3.5 handles multisets and their respective frequencies when the vector passed isn't sorted. Observe:

set.seed(42)
vals <- sample(-50:50, 20)
vals
 [1]  42  43 -22  31  12  -1  19 -38  11  14  -9  41  33 -28 -10  30
[17]  38 -41 -11  -5

vals <- c(0L, vals)
myfreqs <- c(length(vals) - 1, rep(1, length(vals) - 1))

myfreqs
 [1] 20  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

combs <- comboGeneral(vals, length(vals), freqs = myfreqs, 
                                            constraintFun = "sum", 
                                            comparisonFun = "==", 
                                            limitConstraints = 170)

dim(combs)
[1] 6561   21

## Brute force verification
allCombs <- comboGeneral(sort(vals), length(vals),
                         freqs = myfreqs[order(vals)], constraintFun = "sum")

verifiedCombs <- allCombs[which(allCombs[,22] == 170), ]

dim(verifiedCombs)
[1] 2135   22

Clearly, something is not right. We obtained 2135 solutions with brute force and 6561 with the constraint algorithm. Let's have a look at the actual results.

head(combs[,1:12])
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
[1,]  -41  -38  -28  -22  -11  -10   -5    0   11    11    11    11
[2,]  -41  -38  -28  -22  -11  -10   -5   11   11    11    11    11
[3,]  -41  -38  -28  -22  -11  -10   -5   11   11    11    11    11
[4,]  -41  -38  -28  -22  -11  -10   -1   11   11    11    11    11
[5,]  -41  -38  -28  -22  -11  -10    0   11   11    11    11    11
[6,]  -41  -38  -28  -22  -11  -10    0   11   11    11    11    11

head(verifiedCombs)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
[1,]  -41  -38  -28  -22  -10   -5    0    0    0     0    11    12
[2,]  -41  -38  -28  -22   -9   -5   -1    0    0     0    11    12
[3,]  -41  -38  -28  -22   -1    0    0    0    0     0     0    11
[4,]  -41  -38  -28  -11  -10   -5    0    0    0     0     0    12
[5,]  -41  -38  -28  -11   -9   -5   -1    0    0     0     0    12
[6,]  -41  -38  -28  -11   -9   -5    0    0    0     0     0    11
     [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22]
[1,]    14    19    30    31    33    38    41    42    43   170
[2,]    14    19    30    31    33    38    41    42    43   170
[3,]    12    19    30    31    33    38    41    42    43   170
[4,]    14    19    30    31    33    38    41    42    43   170
[5,]    14    19    30    31    33    38    41    42    43   170
[6,]    14    19    30    31    33    38    41    42    43   170

We can see that the brute force solution correctly repeats zero multiple times whereas the constraint algo repeats 11 multiple times. This sorting is taken care of in GetPartitionCase :

RcppAlgos/src/ConstraintsUtils.cpp

Lines 397 to 408 in 8364c46

	if (IsMult) {
	for (int i = 0; i < (lenV - 1); ++i) {
	for (int j = (i + 1); j < lenV; ++j) {
	if (v[i] > v[j]) {
	std::swap(v[i], v[j]);
	std::swap(Reps[i], Reps[j]);
	}
	}
	}
	} else {
	std::sort(v.begin(), v.end());
	}

And we see that it is a templated function that can accept vectors of different types:

RcppAlgos/src/ConstraintsUtils.cpp

Lines 377 to 382 in 8364c46

	template <typename typeVector>
	void GetPartitionCase(const std::vector<std::string> &compFunVec, std::vector<typeVector> &v,
	const std::string &mainFun, const std::vector<typeVector> &target,
	PartitionType &PartType, distinctType &distinctTest, const SEXP &Rlow,
	std::vector<int> &Reps, int lenV, int &m, double tolerance, bool IsMult,
	bool IsRep, bool IsBet, bool mIsNull) {

Now, ConstraintsMaster.cpp calls GetPartitionCase here:

RcppAlgos/src/ConstraintsMaster.cpp

Lines 150 to 156 in 8364c46

	Rtolerance, compFunVec, tolerance, mainFun, vNum);
	GetPartitionCase(compFunVec, vNum, mainFun, targetVals,
	PartType, distinctTest, Rlow, myReps, n, m,
	tolerance, IsMult, IsRep, IsBetweenComp, Rf_isNull(Rm));
	}

And here is the problem. We are only taking care of numeric vectors (vNum and targetVals are vectors of type double). We can verify this by simply wrapping vals above with as.numeric:

combsNum <- comboGeneral(as.numeric(vals), length(vals),
                         freqs = myfreqs, 
                         constraintFun = "sum", 
                         comparisonFun = "==", 
                         limitConstraints = 170)

dim(combsNum)
[1] 2135   21

all.equal(combsNum, verifiedCombs[, 1:21])
[1] TRUE

We simply need to ensure we handle the integer case appropriately.

[jwood000]

Fixed by e0b4909