Let's say we have a 5x5 matrix, filled with 0s.
myMatrix <- matrix(rep(0, 25), ncol = 5)
Now, let's pick a triplet of integers between 1 and 5.
triplet <- c(1,2,3)
For all combinations of this triplet we now add 1 in the matrix, with this function:
addCombinationsToMatrix <- function(.matrix, .triplet){
indexesToChange <- as.matrix(expand.grid(.triplet, .triplet))
.matrix[indexesToChange] <- .matrix[indexesToChange] + 1
.matrix
}
Using the function, we go from
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 0 0 0 0 0
[2,] 0 0 0 0 0
[3,] 0 0 0 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
to
myMatrix <- addCombinationsToMatrix(myMatrix, triplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 1 1 0 0
[3,] 1 1 1 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
If we pick another triplet we move on to
nextTriplet <- 2:4
myMatrix <- addCombinationsToMatrix(myMatrix, nextTriplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 2 2 1 0
[3,] 1 2 2 1 0
[4,] 0 1 1 1 0
[5,] 0 0 0 0 0
So, row-column combinations represent how often two integers have been shown together in a triplet: 3 and 4 have been shown together once, 2 and 3 have been shown together twice.
Question: How can one pick triplets, such that every combination (1-2, 1-3, 1-4...) was picked at least once and the number of triplets is minimized.
I'm looking for an algorithm here that picks the next triplet.
Ideally it can be extended to
- arbitrarily big matrices (10x10, 100x100 ...)
- arbitrarily big vectors (quadruplets, quintuplets, n-tuplets)
- an arbitrary number of times a combination must have been picked at least
Example:
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 1:3)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 3:5)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(1,4,5))
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(2,4,5))
myMatrix
EDIT:
Just to be sure: the answer doesn't have to be R
code. It can be some other language as well or even pseudo code.
EDIT 2: It occured to me now, that there are different ways of measuring efficiency. I actually meant, the algorithm should take as little iterations as possible. The algorithm being fast is also very cool, but not the main goal here.