How to pick a sequence of numbers (from a fixed list) that will sum to a target number?

user_365251 0
Viewed 146

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:

  1. first decide if there is any sequence that will reach the target
  2. return one of the many (possible) sequence

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?

algorithm c++
2 Answers

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.

Abstraction

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.

Example

#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

Further Thoughts

  • productive code should test for zeros in any given values
  • the search could be improved by incrementing the next coefficient if the evaluated polynomial already exceeded the target value.
  • further speedup is possible, when calculating the difference of the target value and the evaluated polynomial when c1 is set to zero, and checking if that difference is a multiple of b1. If not, c2 could be incremented straight forward.
  • Perhaps there exist some shortcuts exploiting the least common multiple
user_64309410

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_105533410
Related