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











up vote
3
down vote

favorite
1












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?










share|improve this question




















  • 2




    I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
    – ihavenoidea
    Nov 4 at 19:13












  • Isn't it a change making problem?
    – user58697
    Nov 4 at 21:27















up vote
3
down vote

favorite
1












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?










share|improve this question




















  • 2




    I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
    – ihavenoidea
    Nov 4 at 19:13












  • Isn't it a change making problem?
    – user58697
    Nov 4 at 21:27













up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





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?










share|improve this question















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?







c++ algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 4 at 19:00

























asked Nov 4 at 18:50









markzzz

17.9k86226400




17.9k86226400








  • 2




    I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
    – ihavenoidea
    Nov 4 at 19:13












  • Isn't it a change making problem?
    – user58697
    Nov 4 at 21:27














  • 2




    I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
    – ihavenoidea
    Nov 4 at 19:13












  • Isn't it a change making problem?
    – user58697
    Nov 4 at 21:27








2




2




I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
– ihavenoidea
Nov 4 at 19:13






I'm thinking backtracking paradigm might be useful here: if the current sum exceeds the target you can disregard that branch and move on to another permutation.
– ihavenoidea
Nov 4 at 19:13














Isn't it a change making problem?
– user58697
Nov 4 at 21:27




Isn't it a change making problem?
– user58697
Nov 4 at 21:27












2 Answers
2






active

oldest

votes

















up vote
1
down vote



accepted










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






share|improve this answer





















  • Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
    – markzzz
    Nov 5 at 10:10










  • Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
    – markzzz
    Nov 5 at 10:17










  • I think this would be the answer: stackoverflow.com/a/47196566/365251
    – markzzz
    Nov 5 at 11:04










  • You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
    – Karl Zeilhofer
    Nov 6 at 9:13










  • The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
    – Karl Zeilhofer
    Nov 6 at 9:16


















up vote
0
down vote













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.






share|improve this answer





















    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53144215%2fhow-to-pick-a-sequence-of-numbers-from-a-fixed-list-that-will-sum-to-a-target%23new-answer', 'question_page');
    }
    );

    Post as a guest
































    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    1
    down vote



    accepted










    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






    share|improve this answer





















    • Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
      – markzzz
      Nov 5 at 10:10










    • Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
      – markzzz
      Nov 5 at 10:17










    • I think this would be the answer: stackoverflow.com/a/47196566/365251
      – markzzz
      Nov 5 at 11:04










    • You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
      – Karl Zeilhofer
      Nov 6 at 9:13










    • The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
      – Karl Zeilhofer
      Nov 6 at 9:16















    up vote
    1
    down vote



    accepted










    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






    share|improve this answer





















    • Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
      – markzzz
      Nov 5 at 10:10










    • Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
      – markzzz
      Nov 5 at 10:17










    • I think this would be the answer: stackoverflow.com/a/47196566/365251
      – markzzz
      Nov 5 at 11:04










    • You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
      – Karl Zeilhofer
      Nov 6 at 9:13










    • The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
      – Karl Zeilhofer
      Nov 6 at 9:16













    up vote
    1
    down vote



    accepted







    up vote
    1
    down vote



    accepted






    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






    share|improve this answer












    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







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered Nov 5 at 2:05









    Karl Zeilhofer

    7518




    7518












    • Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
      – markzzz
      Nov 5 at 10:10










    • Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
      – markzzz
      Nov 5 at 10:17










    • I think this would be the answer: stackoverflow.com/a/47196566/365251
      – markzzz
      Nov 5 at 11:04










    • You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
      – Karl Zeilhofer
      Nov 6 at 9:13










    • The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
      – Karl Zeilhofer
      Nov 6 at 9:16


















    • Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
      – markzzz
      Nov 5 at 10:10










    • Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
      – markzzz
      Nov 5 at 10:17










    • I think this would be the answer: stackoverflow.com/a/47196566/365251
      – markzzz
      Nov 5 at 11:04










    • You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
      – Karl Zeilhofer
      Nov 6 at 9:13










    • The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
      – Karl Zeilhofer
      Nov 6 at 9:16
















    Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
    – markzzz
    Nov 5 at 10:10




    Nice, but this doesn't return a list of possible sequence I'll use. For example: if I set vector<int> set = {2, 3, 4}; with target 12, it returns 2 2 2 2 2 2. What if I'd like to place 2 3 2 3 2? I should combine it with 6 and found 2*3? Its a pain to manage.
    – markzzz
    Nov 5 at 10:10












    Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
    – markzzz
    Nov 5 at 10:17




    Or are you suggesting to use your approch to see if the set can be used, and THAN my approch?
    – markzzz
    Nov 5 at 10:17












    I think this would be the answer: stackoverflow.com/a/47196566/365251
    – markzzz
    Nov 5 at 11:04




    I think this would be the answer: stackoverflow.com/a/47196566/365251
    – markzzz
    Nov 5 at 11:04












    You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
    – Karl Zeilhofer
    Nov 6 at 9:13




    You are right, it only prints that sequence. But generating that sequence in a vector or list should be easy. I'm a bit confused, why a systematic sequence (not shuffeld in any way) is not aceptable. You said, you want to get any of the multiple solutions.
    – Karl Zeilhofer
    Nov 6 at 9:13












    The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
    – Karl Zeilhofer
    Nov 6 at 9:16




    The given algorithm could easily return a list of all solutions, and then you could randomly select one of them.
    – Karl Zeilhofer
    Nov 6 at 9:16












    up vote
    0
    down vote













    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.






    share|improve this answer

























      up vote
      0
      down vote













      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.






      share|improve this answer























        up vote
        0
        down vote










        up vote
        0
        down vote









        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.






        share|improve this answer












        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 4 at 19:52









        Damien

        565




        565






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53144215%2fhow-to-pick-a-sequence-of-numbers-from-a-fixed-list-that-will-sum-to-a-target%23new-answer', 'question_page');
            }
            );

            Post as a guest




















































































            這個網誌中的熱門文章

            Xamarin.form Move up view when keyboard appear

            Post-Redirect-Get with Spring WebFlux and Thymeleaf

            Anylogic : not able to use stopDelay()