-1

I am trying to generate every combination of four numbers from (-1,-0.99,-0.98,...0.98,0.99,1) that sum up to 1.

I have tried to it in C++ but it is not working as I want. Here is the example:

    // C++ program for to print all combination
// of 4 elements in A[] with sum equal to X
#include<bits/stdc++.h>
using namespace std;

/* Following function is needed
for library function qsort(). */
int compare (const void *a, const void * b)
{
    return ( *(int *)a - *(int *)b );
}

/* A sorting based solution to print
all combination of 4 elements in A[]
with sum equal to X */
void find4Numbers(double A[], int n, double X)
{
    int l, r;

    // Sort the array in increasing
    // order, using library function
    // for quick sort
    qsort (A, n, sizeof(A[0]), compare);

    /* Now fix the first 2 elements
    one by one and find
    the other two elements */
    for (int i = 0; i < n - 3; i++)
    {
        for (int j = i+1; j < n - 2; j++)
        {
            // Initialize two variables as
            // indexes of the first and last
            // elements in the remaining elements
            l = j + 1;
            r = n-1;

            // To find the remaining two
            // elements, move the index
            // variables (l & r) toward each other.
            while (l < r)
            {
                if( A[i] + A[j] + A[l] + A[r] == X)
                {
                    cout << A[i]<<", " << A[j] <<
                        ", " << A[l] << ", " << A[r] << endl;
                    l++; r--;
                }
                else if (A[i] + A[j] + A[l] + A[r] < X)
                    l++;
                else // A[i] + A[j] + A[l] + A[r] > X
                    r--;
            } // end of while
        } // end of inner for loop
    } // end of outer for loop

}

/* Driver code */
int main()
{
    /*int A[202];
    for(int i=0; i<201; i++){
        A[i]={i};
    }
    A[202]=0;
    int X = 70;
    int n = 202;*/
    double A[] = {-1,-0.99,-0.98,-0.97,-0.96,-0.95,-0.94,-0.93,-0.92,-0.91,-0.9,-0.89,-0.88,-0.87,-0.86,-0.85,-0.84,-0.83,-0.82,-0.81,-0.8,-0.79,-0.78,-0.77,-0.76,-0.75,-0.74,-0.73,-0.72,-0.71,-0.7,-0.69,-0.68,-0.67,-0.66,-0.65,-0.64,-0.63,-0.62,-0.61,-0.6,-0.59,-0.58,-0.57,-0.56,-0.55,-0.54,-0.53,-0.52,-0.51,-0.5,-0.49,-0.48,-0.47,-0.46,-0.45,-0.44,-0.43,-0.42,-0.41,-0.4,-0.39,-0.38,-0.37,-0.36,-0.35,-0.34,-0.33,-0.32,-0.31,-0.3,-0.29,-0.28,-0.27,-0.26,-0.25,-0.24,-0.23,-0.22,-0.21,-0.2,-0.19,-0.18,-0.17,-0.16,-0.15,-0.14,-0.13,-0.12,-0.11,-0.1,-0.09,-0.08,-0.07,-0.06,-0.05,-0.04,-0.03,-0.02,0.01,0,0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.1,0.11,0.12,0.13,0.14,0.15,0.16,0.17,0.18,0.19,0.2,0.21,0.22,0.23,0.24,0.25,0.26,0.27,0.28,0.29,0.3,0.31,0.32,0.33,0.34,0.35,0.36,0.37,0.38,0.39,0.4,0.41,0.42,0.43,0.44,0.45,0.46,0.47,0.48,0.49,0.5,0.51,0.52,0.53,0.54,0.55,0.56,0.57,0.58,0.59,0.6,0.61,0.62,0.63,0.64,0.65,0.66,0.67,0.68,0.69,0.7,0.71,0.72,0.73,0.74,0.75,0.76,0.77,0.78,0.79,0.8,0.81,0.82,0.83,0.84,0.85,0.86,0.87,0.88,0.89,0.9,0.91,0.92,0.93,0.94,0.95,0.96,0.97,0.98,0.99,1
};

    double X = 1;
    int n = sizeof(A) / sizeof(A[0]);
    find4Numbers(A, n, X);
    return 0;
}

It gives numbers that sum to 1 but the output does not give every combination. For example numbers 0,1,0.12,-0.12 does not show up. I am looking for the list of these numbers, I don't even need a code. Numbers can duplicate so (0,0,0.5, 0.5) is okay, too.

Can you have any tips where could I generate the list or how to make a program that gives one?

user438383
  • 5,716
  • 8
  • 28
  • 43
Maria Adamiak
  • 11
  • 3
    Welcome - please don't add random tags which are unrelated to the question. Thank you. – user438383 Jan 02 '22 at 19:11
  • 1
    Unrelated but please read [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) – Ted Lyngmo Jan 02 '22 at 19:13
  • 3
    Double is not a good way to store such numbers. I would rather represent it by integer by multiplying by 100 – Peter Trencansky Jan 02 '22 at 19:13
  • 2
    This sounds like this came from some coding puzzle web site. Is it? What this is asking is really testing basic knowledge and understanding of computer science and algorithms. If someone don't know the answer, a bare code dump won't help you understand or learn anything. Instead, the correct answer here should be to go and learn the relevant areas of computer science and algorithms which are needed to implement this. Unfortunately, stackoverflow.com is not a replacement for a [good C++ and computer science algorithms textbook](https://stackoverflow.com/questions/388242/). – Sam Varshavchik Jan 02 '22 at 19:15
  • 1
    The sorting comparator looks off - just use `std::sort(A, A + n);` instead. – Ted Lyngmo Jan 02 '22 at 19:16
  • A somewhat lighter note on floating point numbers and what they cannot do : Floating Point Numbers - Computerphile (Tom Scott), https://www.youtube.com/watch?v=PZRI1IfStY0. And like Sam said competitive coding is not a good way to learn C++, you also could try this : https://www.learncpp.com/ – Pepijn Kramer Jan 02 '22 at 19:16
  • Have you tried something simpler? Like finding all pairs of integers from [-10,..,10] that add up to 10? Or all sets of three? – Beta Jan 02 '22 at 19:19
  • @Maria Adamiak, I have created a solution but unfortunately, this question is locked. Here is the solution in Github gist: https://gist.github.com/arsho/9e5358e62f3d2fd1419a953e3587a37c – arshovon Jan 02 '22 at 19:48

1 Answers1

1

For starters, your compare function is wrong since you are comparing int instead of double. Therefore try:

int compare (const void *a, const void * b)
{
    double ca = *((double *) a);
    double cb = *((double *) b);
    return (ca > cb) - (ca < cb);
}
Whitewolf3131
  • 79
  • 10
  • 1
    Ok, it's fine after the edit (unless you get `Inf` as a result in the subtraction), but the suggestion should rather be to use `std::sort`. – Ted Lyngmo Jan 02 '22 at 19:25
  • A version without the risk of `Inf` could look like this `int compare(const void *a, const void * b) { double A = *static_cast(a); double B = *static_cast(b); return (A>B) - (A – Ted Lyngmo Jan 02 '22 at 19:31
  • I agree with you. Unfortunately, I don't know C++, but you are right in using a probably higher level function than qsort. – Whitewolf3131 Jan 02 '22 at 19:35
  • Ok, but the risk of `tester` being assign infinity is there even if you write it like you do in C. – Ted Lyngmo Jan 02 '22 at 19:36
  • 1
    I tried changing the solution to take into account `Inf` as well. – Whitewolf3131 Jan 02 '22 at 19:42
  • Yes, that's much better and safe. I would use `static_cast` like I showed in the comment though, but anyway, now it should work safely. If you use C style cast, you should still cast to a `const double*` though. – Ted Lyngmo Jan 02 '22 at 19:43