Let say I've a target number and a list of possibile values that I can pick to create a sequence that, once summed every picked number, will sum to the target:
target = 31
list = 2, 3, 4
possible sequence: 3 2 4 2 2 2 4 2 3 2 3 2
I'd like to:
This is my attempt:
#include <iostream>
#include <random>
#include <chrono>
#include <vector>
inline int GetRandomInt(int min = 0, int max = 1) {
uint64_t timeSeed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
std::seed_seq ss{ uint32_t(timeSeed & 0xffffffff), uint32_t(timeSeed >> 32) };
std::mt19937_64 rng;
rng.seed(ss);
std::uniform_int_distribution<int> unif(min, max);
return unif(rng);
}
void CreateSequence(int target, std::vector<int> &availableNumbers) {
int numAttempts = 1;
int count = 0;
std::vector<int> elements;
while (count != target) {
while (count < target) {
int elem = availableNumbers[GetRandomInt(0, availableNumbers.size() - 1)];
count += elem;
elements.push_back(elem);
}
if (count != target) {
numAttempts++;
count = 0;
elements.clear();
}
}
int size = elements.size();
std::cout << "count: " << count << " | " << "num elements: " << size << " | " << "num attempts: " << numAttempts << std::endl;
for (auto it = elements.begin(); it != elements.end(); it++) {
std::cout << *it << " ";
}
}
int main() {
std::vector<int> availableNumbers = { 2, 3, 4 };
CreateSequence(31, availableNumbers);
}
But it can loop infinitely if the list of number can't be appropriate to reach such sum; example:
std::vector<int> availableNumbers = { 3 };
CreateSequence(8, availableNumbers);
No sequence of 3 will sum to 8. Also, if the list is huge and the target number high, it can lead to a huge amount of processing (cause lots of while check fails).
How would you implement this kind of algorithm?
Your suggested code is possibly very fast, since it is heuristic. But as you said, it gets potentially trapped in a nearly endless loop.
If you want to avoid this situation, you have to search the complete set of possible combinations.
Let's define our algorithm as a function f
with a scalar target t
and a vector <b>
as parameters returning a vector of coefficients <c>
, where <b>
and <c>
have the same dimension:
<c> = f(t, <b>)
First the given set of numbers Sg
should be reduced to their reduced set Sr
so we reduce the dimension of our solution vector <c>
. E.g. {2,3,4,11}
can be reduced to {2,3}
. We get this by calling our algorithm recursively by splitting Sg
into a new target ti
with the remaining numbers as the new given set Sgi
and ask the algorithm, if it finds any solution (a non-zero vector). If so, remove that target ti
from the original given set Sg
. Repeat this recursively until no solutions found any more.
Now we can understand this set of numbers as a polynomial, where we are looking for possible coefficients ci
to get our target t
. Let's call each element in Sb
bi
with i={1..n}
.
Our test sum ts
is the sum over all i
for ci * bi
, where each ci
can run from 0
to ni = floor(t/bi)
.
The number of possible tests N
is now the product over all ni+1
: N = (n1+1) * (n2+1) * ... * (ni+1)
.
Iterate now over all possibilities by representing the coefficient vector <c>
as an vector of integers and incrementing c1
and carrying over an overrun to the next element in the vector, resetting c1 and so forth.
#include <random>
#include <chrono>
#include <vector>
#include <iostream>
using namespace std;
static int evaluatePolynomial(const vector<int> &base, const vector<int> &coefficients)
{
int v=0;
for(unsigned long i=0; i<base.size(); i++){
v += base[i]*coefficients[i];
}
return v;
}
static bool isZeroVector(vector<int> &v)
{
for (auto it = v.begin(); it != v.end(); it++) {
if(*it != 0){
return false;
}
}
return true;
}
static vector<int> searchCoeffs(int target, vector<int> &set) {
// TODO: reduce given set
vector<int> n = set;
vector<int> c = vector<int>(set.size(), 0);
for(unsigned long int i=0; i<set.size(); i++){
n[i] = target/set[i];
}
c[0] = 1;
bool overflow = false;
while(!overflow){
if(evaluatePolynomial(set, c) == target){
return c;
}
// increment coefficient vector
overflow = true;
for(unsigned long int i=0; i<c.size(); i++){
c[i]++;
if(c[i] > n[i]){
c[i] = 0;
}else{
overflow = false;
break;
}
}
}
return vector<int>(set.size(), 0);
}
static void print(int target, vector<int> &set, vector<int> &c)
{
for(unsigned long i=0; i<set.size(); i++){
for(int j=0; j<c[i]; j++){
cout << set[i] << " ";
}
}
cout << endl;
cout << target << " = ";
for(unsigned long i=0; i<set.size(); i++){
cout << " +" << set[i] << "*" << c[i];
}
cout << endl;
}
int main() {
vector<int> set = {4,3,2};
int target = 31;
auto c = searchCoeffs(target, set);
print(target, set,c);
}
That code prints
4 4 4 4 4 4 4 3
31 = +4*7 +3*1 +2*0
As ihavenoidea proposed, I would also try backtracking. In addition, I will sort the numbers in decreasing order, il order to speed up the process.
Note: a comment would be more appropriate than an answer, but I am not allowed to. Hope it helps. I will suppress this answer if requested.
User contributions licensed under CC BY-SA 3.0