AnonX
Reputation: 169
Algorithm for best sum combination from 3 groups list
I have multi group of data like:
X <- c(2,3,5,10,15)
Y <- c(4,6,23,15,12)
Z <- c(23,34,12,1,5)
and a target: target = 50
I want to know the best (for example): 2 values from X (call it X2), 4 values from Y (Y4) and 3 values from Z (Z3) that if I sum them I get sum(X2) + sum(Y4) + sum(Z3) = 50 (or the closest to 50).
Is there a solution to this problem?
Edit: The data I've provided is just an example… My end goal is to reproduce it on a large data.
Here's my large data:
target <- 362007
X <- c(1782L, 1780L, 1783L, 1784L, 1783L, 1781L, 1782L, 1781L, 1782L,
1782L, 1782L, 1784L, 1780L, 1784L, 1782L, 1779L, 1782L, 1784L,
1783L, 1782L, 1781L, 1777L, 1784L, 1782L, 1784L, 1784L, 1784L,
1782L, 1784L, 1782L, 1783L, 1783L, 1785L, 1782L, 1781L, 1782L,
1788L, 1789L, 1786L, 1787L, 1786L, 1783L, 1781L, 1781L, 1786L,
1787L, 1786L, 1786L, 1785L, 1785L, 1784L, 1786L, 1785L, 1784L,
1786L, 1785L, 1785L, 1783L, 1787L, 1787L, 1786L, 1785L, 1788L,
1786L, 1788L, 1786L, 1780L, 1788L, 1785L, 1784L, 1786L, 1784L,
1785L, 1783L, 1785L, 1785L, 1785L, 1786L, 1784L, 1784L, 1785L,
1784L, 1785L, 1787L, 1786L, 1788L, 1785L, 1785L, 1780L, 1787L,
1784L, 1785L, 1787L, 1784L, 1780L, 1785L, 1782L, 1787L, 1786L,
1781L, 1780L, 1784L, 1785L, 1785L, 1785L, 1785L, 1785L, 1782L,
1783L, 1787L, 1784L, 1783L, 1783L, 1782L, 1785L, 1783L, 1783L,
1782L, 1786L, 1783L, 1786L, 1782L, 1783L, 1786L, 1784L, 1782L,
1782L, 1785L, 1785L, 1783L, 1782L, 1781L, 1782L, 1779L, 1781L,
1781L, 1785L, 1780L, 1782L, 1781L, 1782L, 1786L, 1786L, 1787L,
1781L, 1780L, 1788L, 1781L, 1781L, 1780L, 1787L, 1787L, 1787L,
1780L, 1786L, 1786L, 1779L, 1785L, 1792L, 1788L, 1781L, 1784L,
1780L, 1784L, 1783L, 1785L, 1783L, 1783L, 1781L, 1783L, 1785L,
1783L, 1785L, 1782L, 1785L, 1782L, 1782L, 1782L, 1779L, 1787L,
1784L, 1783L, 1783L, 1786L, 1785L, 1787L, 1785L, 1783L, 1783L,
1786L, 1784L, 1778L, 1787L, 1786L, 1784L, 1784L, 1781L, 1779L,
1782L, 1786L, 1781L, 1787L, 1783L, 1781L, 1781L, 1786L, 1787L,
1780L, 1779L, 1785L, 1784L, 1781L, 1783L, 1782L, 1781L, 1781L,
1787L, 1785L, 1787L, 1784L, 1784L, 1783L, 1782L, 1785L, 1785L,
1783L, 1779L, 1786L, 1780L, 1778L, 1783L, 1785L, 1780L, 1786L,
1784L, 1779L, 1779L, 1779L, 1785L, 1780L, 1786L, 1778L, 1782L,
1779L, 1779L, 1784L, 1780L, 1780L, 1785L, 1781L, 1778L, 1787L,
1781L, 1786L, 1783L, 1784L, 1785L, 1786L, 1784L, 1782L, 1784L,
1785L, 1786L, 1786L, 1785L, 1782L, 1786L, 1783L, 1783L, 1788L,
1779L, 1786L, 1787L, 1781L, 1780L, 1780L, 1782L, 1784L, 1787L,
1780L, 1786L, 1786L, 1786L, 1784L, 1787L, 1785L, 1784L, 1784L,
1784L, 1781L, 1784L, 1784L, 1786L, 1784L, 1783L, 1784L, 1786L,
1787L, 1786L, 1786L, 1785L, 1786L, 1785L, 1785L)
Y <- c(1786L, 1786L, 1786L, 1786L, 1787L, 1784L, 1782L, 1787L, 1786L,
1786L, 1781L, 1787L, 1782L, 1785L, 1785L, 1786L, 1783L, 1781L,
1787L, 1780L, 1785L, 1783L, 1787L, 1785L, 1786L, 1789L, 1784L,
1785L, 1782L, 1780L, 1783L, 1786L, 1784L, 1782L, 1781L, 1788L,
1785L, 1779L, 1782L, 1781L, 1781L, 1785L, 1781L, 1786L, 1784L,
1782L, 1783L, 1782L, 1783L, 1784L, 1786L, 1780L, 1784L, 1782L,
1779L, 1783L, 1789L, 1783L, 1782L, 1786L, 1784L, 1783L, 1788L,
1786L, 1788L, 1783L, 1785L, 1787L, 1787L, 1784L, 1784L, 1787L,
1783L, 1782L, 1787L, 1788L, 1786L, 1786L, 1785L, 1787L, 1782L,
1787L, 1782L, 1787L, 1783L, 1787L, 1783L, 1784L, 1782L, 1782L,
1784L, 1784L, 1786L, 1782L, 1780L, 1786L, 1783L, 1787L, 1785L,
1786L, 1783L, 1783L, 1780L, 1781L, 1782L, 1788L, 1782L, 1783L,
1785L, 1785L, 1783L, 1786L, 1785L, 1786L, 1780L, 1782L, 1785L,
1784L, 1787L, 1779L, 1783L, 1782L, 1785L, 1780L, 1780L, 1786L,
1782L, 1785L, 1785L, 1779L, 1783L, 1786L, 1787L, 1789L, 1782L,
1781L, 1783L, 1780L, 1784L, 1783L, 1784L, 1784L, 1785L, 1785L,
1786L, 1782L, 1782L, 1781L, 1783L, 1787L, 1784L, 1785L, 1782L,
1781L, 1786L, 1784L, 1783L, 1784L, 1786L, 1784L, 1781L, 1783L,
1786L, 1784L, 1782L, 1782L, 1786L, 1783L, 1782L, 1784L, 1786L,
1784L, 1786L, 1783L, 1788L, 1782L, 1782L, 1787L, 1780L, 1781L,
1782L, 1787L, 1785L, 1781L, 1781L, 1783L, 1787L, 1785L, 1786L,
1783L, 1786L, 1780L, 1785L, 1786L, 1786L, 1781L, 1786L, 1786L,
1787L, 1786L, 1783L, 1789L, 1785L, 1782L, 1789L, 1788L, 1784L,
1782L, 1783L, 1781L, 1784L, 1783L, 1783L, 1787L, 1784L, 1783L,
1781L, 1783L, 1787L, 1783L, 1786L, 1791L, 1782L, 1788L, 1786L,
1785L, 1782L, 1787L, 1782L, 1784L, 1782L, 1782L, 1781L, 1782L,
1784L, 1783L, 1783L, 1784L, 1780L, 1787L, 1783L, 1785L, 1782L,
1786L, 1782L, 1787L, 1785L, 1782L, 1785L, 1784L, 1786L, 1783L,
1781L, 1782L, 1781L, 1785L, 1782L, 1783L, 1784L, 1782L, 1782L,
1784L, 1783L, 1787L, 1786L, 1786L, 1781L, 1782L, 1785L, 1787L,
1784L, 1782L, 1788L, 1782L, 1783L, 1783L, 1785L, 1781L, 1780L,
1786L, 1785L, 1780L, 1781L, 1782L, 1787L, 1784L, 1780L, 1782L,
1781L, 1781L, 1780L, 1784L, 1782L, 1792L, 1787L, 1782L, 1779L,
1784L, 1785L, 1786L, 1782L, 1786L, 1785L, 1785L, 1784L, 1785L,
1783L, 1786L, 1785L, 1783L, 1782L, 1784L, 1781L, 1782L, 1784L,
1786L, 1783L, 1783L, 1781L, 1785L, 1779L, 1783L, 1781L, 1781L,
1786L, 1783L, 1781L, 1787L, 1782L, 1787L, 1786L, 1645L, 1788L,
1783L, 1786L, 1787L, 1783L, 1780L, 1781L, 1782L, 1782L, 1786L,
1781L, 1785L, 1783L, 1784L, 1783L, 1784L, 1784L, 1781L, 1787L,
1781L, 1785L, 1782L, 1784L, 1790L, 1795L, 1793L, 1780L, 1782L,
1788L, 1787L, 1788L, 1781L, 1781L, 1788L, 1782L, 1783L, 1780L,
1785L, 1784L, 1781L, 1786L, 1781L, 1787L, 1794L, 1792L, 1791L,
1781L, 1779L, 1781L, 1781L, 1782L, 1784L, 1783L, 1785L, 1785L,
1785L, 1781L, 1778L, 1782L, 1784L, 1786L, 1786L, 1784L, 1782L,
1779L, 1781L, 1782L, 1785L, 1783L, 1782L, 1784L, 1779L, 1785L,
1784L, 1787L, 1785L, 1786L, 1789L, 1788L, 1785L, 1785L, 1785L,
1783L, 1784L, 1786L, 1784L, 1782L, 1779L, 1782L, 1787L, 1788L,
1782L, 1786L, 1784L, 1783L, 1782L, 1785L, 1785L, 1786L, 1786L,
1786L, 1785L, 1785L, 1789L, 1786L, 1781L, 1785L, 1784L, 1787L,
1781L, 1788L, 1783L, 1786L, 1786L, 1786L, 1783L, 1788L, 1788L,
1781L, 1787L, 1791L, 1784L, 1784L, 1785L, 1784L, 1784L, 1782L,
1779L, 1777L, 1780L, 1783L, 1782L, 1780L, 1781L, 1785L, 1780L,
1783L, 1786L, 1784L, 1779L, 1785L, 1784L, 1783L, 1783L, 1783L,
1783L, 1785L, 1781L, 1778L, 1781L, 1785L, 1781L, 1782L, 1788L,
1782L, 1783L, 1781L, 1786L, 1781L, 1784L, 1782L, 1783L, 1787L,
1783L, 1786L, 1783L, 1780L, 1781L, 1779L, 1781L, 1784L, 1785L,
1782L, 1785L, 1785L, 1783L, 1781L, 1780L, 1780L, 1781L, 1779L,
1780L, 1783L, 1782L, 1786L, 1780L, 1785L, 1786L, 1781L, 1783L,
1783L, 1788L, 1783L, 1786L, 1788L, 1786L, 1783L, 1784L, 1788L,
1787L, 1785L, 1785L, 1784L, 1782L, 1785L, 1785L, 1784L, 1781L,
1788L, 1785L, 1785L, 1786L, 1785L, 1786L, 1787L, 1781L, 1787L,
1782L, 1781L, 1786L, 1781L, 1783L, 1782L, 1786L, 1786L, 1788L,
1781L, 1781L, 1783L, 1784L, 1783L, 1781L, 1788L, 1785L, 1779L,
1786L, 1781L, 1781L, 1787L, 1784L, 1788L, 1782L, 1786L, 1787L,
1780L, 1785L, 1788L, 1783L, 1783L, 1785L, 1780L, 1780L, 1788L,
1784L, 1782L, 1787L, 1782L, 1783L, 1782L, 1782L, 1786L, 1784L,
1788L, 1783L, 1785L, 1786L, 1781L, 1784L, 1782L, 1792L, 1784L,
1782L, 1780L, 1784L, 1782L, 1783L, 1785L, 1783L, 1787L, 1785L,
1785L, 1781L, 1787L, 1785L, 1787L, 1783L, 1780L, 1780L, 1785L,
1783L, 1786L, 1784L, 1783L, 1782L, 1782L, 1789L, 1783L, 1786L,
1785L, 1783L, 1787L, 1788L, 1783L, 1783L, 1786L, 1783L, 1786L,
1782L, 1787L, 1782L, 1784L, 1782L, 1786L, 1787L, 1788L, 1788L,
1782L, 1786L, 1780L, 1785L, 1779L, 1779L, 1779L, 1779L, 1779L,
1783L, 1783L, 1782L, 1786L, 1785L, 1783L, 1781L, 1780L, 1784L,
1779L, 1785L, 1780L, 1779L, 1780L, 1779L, 1780L, 1782L, 1783L,
1781L, 1785L, 1783L, 1786L, 1779L, 1781L, 1781L, 1781L, 1780L,
1781L, 1780L, 1780L, 1780L, 1780L, 1781L, 1781L, 1781L, 1781L,
1781L, 1781L, 1780L, 1780L, 1781L, 1786L, 1780L, 1781L, 1780L,
1780L, 1795L, 1790L, 1793L, 1786L, 1784L, 1782L, 1784L, 1783L,
1788L, 1787L, 1786L, 1778L, 1783L, 1786L, 1784L, 1783L, 1785L,
1786L, 1780L, 1786L, 1786L, 1785L, 1782L, 1782L, 1786L, 1784L,
1787L, 1789L, 1788L, 1782L, 1783L, 1787L, 1783L, 1786L, 1782L,
1782L, 1786L, 1783L, 1785L, 1788L, 1788L, 1787L, 1783L, 1788L,
1783L, 1782L, 1782L, 1786L, 1789L, 1784L, 1785L, 1780L, 1781L,
1786L, 1786L, 1788L, 1785L, 1781L, 1786L, 1785L, 1782L, 1780L,
1784L, 1781L, 1779L, 1785L, 1786L, 1779L, 1782L, 1783L, 1783L,
1780L, 1783L, 1782L, 1786L, 1779L, 1780L, 1781L, 1786L, 1783L,
1785L, 1786L, 1782L, 1787L, 1784L, 1786L, 1786L, 1785L, 1786L,
1785L, 1784L, 1787L, 1784L, 1784L, 1788L, 1785L, 1784L, 1782L,
1783L, 1785L, 1782L, 1787L, 1781L, 1782L, 1785L, 1782L, 1786L,
1785L, 1787L, 1787L, 1786L, 1787L, 1780L, 1785L, 1784L, 1783L,
1782L, 1787L, 1779L, 1779L, 1786L, 1780L, 1787L, 1781L, 1778L,
1782L, 1779L, 1778L, 1780L, 1786L, 1779L, 1785L, 1784L, 1779L,
1784L, 1781L, 1784L, 1782L, 1785L, 1783L, 1781L, 1786L, 1780L,
1781L, 1780L, 1781L, 1784L, 1787L, 1779L, 1786L, 1781L, 1782L,
1780L, 1782L, 1786L, 1786L, 1787L, 1782L, 1788L, 1783L, 1785L,
1788L, 1785L, 1786L, 1787L, 1787L, 1785L, 1784L, 1784L, 1787L,
1788L, 1787L, 1782L, 1786L, 1784L, 1783L, 1786L, 1782L, 1782L,
1789L, 1784L, 1783L, 1793L, 1794L, 1793L, 1787L, 1783L, 1782L,
1786L, 1784L, 1787L, 1783L, 1783L, 1786L, 1789L, 1781L, 1785L,
1784L, 1788L, 1789L, 1782L, 1784L, 1784L, 1787L, 1787L, 1783L,
1784L, 1784L, 1783L, 1786L, 1783L, 1785L, 1788L, 1787L, 1788L,
1783L, 1784L, 1783L, 1783L, 1781L, 1784L, 1786L, 1782L, 1791L,
1787L, 1781L, 1787L, 1785L, 1787L, 1783L, 1785L, 1782L, 1784L,
1787L, 1784L, 1783L, 1783L, 1783L, 1784L, 1786L, 1787L, 1782L,
1789L, 1782L, 1782L, 1783L, 1782L, 1783L, 1783L, 1784L, 1783L,
1788L, 1786L, 1782L, 1784L, 1781L, 1786L, 1782L, 1779L, 1780L,
1783L, 1780L, 1786L, 1780L, 1786L, 1784L, 1784L, 1785L, 1777L,
1783L, 1780L, 1784L, 1783L, 1780L, 1784L, 1781L, 1785L, 1785L,
1781L, 1780L, 1786L, 1788L, 1787L, 1791L, 1789L, 1787L, 1787L,
1793L, 1781L, 1784L, 1781L, 1784L, 1779L, 1784L, 1784L, 1784L,
1780L, 1780L, 1784L, 1787L, 1782L, 1781L, 1784L, 1787L, 1785L,
1781L, 1785L, 1783L, 1782L, 1782L, 1785L, 1781L, 1782L, 1786L,
1788L, 1780L, 1787L, 1784L, 1788L, 1787L, 1784L, 1784L, 1785L,
1780L, 1786L, 1780L, 1780L, 1788L, 1782L, 1793L, 1783L, 1785L,
1785L, 1781L, 1783L, 1783L, 1787L, 1783L, 1784L, 1784L, 1783L,
1785L, 1787L, 1788L, 1784L, 1787L, 1787L, 1785L, 1786L, 1784L,
1786L, 1784L, 1786L, 1787L)
Z <- c(1788L, 1792L, 1787L, 1791L, 1790L, 1789L, 1791L, 1788L, 1792L,
1794L, 1793L, 1791L, 1792L, 1787L, 1792L, 1792L, 1791L, 1788L,
1792L, 1794L, 1791L, 1788L, 1794L, 1794L, 1789L, 1792L, 1788L,
1793L, 1792L, 1788L, 1786L, 1787L, 1791L, 1786L, 1788L, 1792L,
1787L, 1785L, 1786L, 1790L, 1788L, 1790L, 1792L, 1788L, 1787L,
1790L, 1786L, 1792L, 1789L, 1787L, 1786L, 1787L, 1793L, 1793L,
1792L, 1789L, 1786L, 1795L, 1793L, 1788L, 1791L, 1790L, 1792L,
1790L, 1794L, 1792L, 1789L, 1791L, 1794L, 1788L, 1788L, 1794L,
1794L, 1792L, 1790L, 1789L, 1788L, 1788L, 1789L, 1789L, 1794L,
1790L, 1787L, 1791L, 1789L, 1791L, 1790L, 1783L, 1782L, 1781L,
1781L, 1793L, 1788L, 1795L, 1793L, 1789L, 1791L, 1793L, 1792L,
1792L, 1784L, 1781L, 1782L, 1795L, 1788L, 1789L, 1793L, 1793L,
1792L, 1791L, 1791L, 1790L, 1794L, 1792L, 1796L, 1793L, 1791L,
1793L, 1790L, 1794L, 1795L, 1788L, 1789L, 1790L, 1790L, 1793L,
1790L, 1795L, 1793L, 1792L, 1778L, 1784L, 1782L, 1791L, 1793L,
1791L, 1794L, 1793L, 1793L, 1790L, 1792L, 1788L, 1786L, 1790L,
1794L, 1794L, 1791L, 1787L, 1792L, 1790L, 1791L, 1799L, 1790L,
1788L, 1795L, 1791L, 1792L, 1787L, 1788L, 1792L, 1795L, 1786L,
1785L, 1778L, 1794L, 1790L, 1794L, 1792L, 1793L, 1793L, 1793L,
1792L, 1791L, 1794L, 1791L, 1788L, 1789L, 1790L, 1794L, 1793L,
1793L, 1791L, 1791L, 1795L, 1790L, 1790L, 1788L, 1793L, 1793L,
1786L, 1788L, 1795L, 1790L, 1781L, 1781L, 1782L, 1786L, 1794L,
1787L, 1787L, 1782L, 1786L, 1783L, 1788L, 1784L)
Upvotes: 3
Views: 140
Answers (2)
Stéphane Laurent
Reputation: 84639
Here is a solution with the function MixedCombnPerm which can be found here.
This solution consists in deriving all possible combinations and then taking the best one(s).
X <- c(2,3,5,10,15)
Y <- c(4,6,23,15,12)
Z <- c(23,34,12,1,5)
set_list <- list(X, Y, Z)
k <- c(2, 4, 3)
combinations <- MixedCombnPerm(set_list, k)
total <- colSums(combinations)
deviation <- abs(total - 50)
is <- which(deviation == min(deviation))
combinations[, is]
# [1] 2 3 4 6 15 12 12 1 5
total[is]
# [1] 60
Here is a solution with CVXR. The small values in the results actually are 0.
library(CVXR)
x <- Bool(5)
y <- Bool(5)
z <- Bool(5)
constraintX <- sum(x) == 2
constraintY <- sum(y) == 4
constraintZ <- sum(z) == 3
objective <- Minimize((sum(x*X+y*Y+z*Z) - 50)^2)
problem <- Problem(objective,
constraints = list(constraintX, constraintY, constraintZ))
result <- solve(problem)
result$getValue(x)
# [,1]
# [1,] 1.000000e+00
# [2,] 1.000000e+00
# [3,] 1.168141e-09
# [4,] 8.964959e-11
# [5,] 2.563038e-11
result$getValue(y)
# [,1]
# [1,] 1.000000e+00
# [2,] 1.000000e+00
# [3,] 1.841415e-10
# [4,] 1.000000e+00
# [5,] 1.000000e+00
result$getValue(z)
# [,1]
# [1,] 9.946796e-11
# [2,] 3.816320e-11
# [3,] 1.000000e+00
# [4,] 1.000000e+00
# [5,] 1.000000e+00
EDIT
Here is a solution using CVXR for your large data. First, install the package Rglpk:
install.packages("Rglpk")
Then do:
result <- solve(problem, solver = "GLPK")
I tested it with
objective <- Minimize( abs( sum(x*X) + sum(y*Y) + sum(z*Z) - target) )
and it worked.
Upvotes: 4
ThomasIsCoding
Reputation: 102399
Maybe outer() can help you, but the efficiency may be low when with large dataset:
k <- c(2,4,3)
L <- list(X,Y,Z)
V <- sapply(seq_along(k), function(q) combn(L[[q]],k[q]))
S <- abs(Reduce(function(x,y) outer(x,y,"+"), Map(colSums,V))-50)
r <- as.numeric(which(S == min(S),arr.ind = T))
res <- sapply(seq_along(r), function(q) V[[q]][,r[q]])
which gives:
> res
$X
[1] 2 3
$Y
[1] 4 6 15 12
$Z
[1] 12 1 5
Upvotes: 1
Related Questions
- Create Combinations in R by Groups
- Obtaining all possible combinations with a minimum number per group
- How to find possible combinations of 3 values given their maximums?
- find all possible 3 number combinations where sum is less than a given number using R
- algorithm to find best combination
- R Find best set of all possible combinations that includes all values
- R: get all combinations of three numbers that add up to 100
- Algorithm for combining numbers into optimal groups which do not exceed a vector of max values?
- Sum values of combinations within a group
- Need algorithm (logic) for best sum combination from multi group list