Finding Combinations of Numbers in an Array

[DaveC426913]

Grr! This is flummoxing me!

I want to add every combination of cells in n rows that will be input be textfields.

• The number of rows is flexible. It is defined when the appropriate number of textfields have strings of numbers in them.
• Each row will have its own number of cells in it, determined by the data in the textfield.
• I want to sum one from each field.

So, user inputs:
field 1: 12
field 2: 678
field 3: 45
field n: -
And user is looking for sum: 12

Results in:

164
165 is a hit!
174 is a hit!
175
184
185
264 is a hit!
265
274
275
284
285

Every time I write a nested loop, I run into trouble. I need a counter for EACH field. (My code below advances the cell counter for ALL rows at the same time.)

(This is essentially JavaScript but just treat it as pseudocode. I can transcribe from pseudocode.)

arr = loadFieldDataIntoArray();
var lookingToMatchSum = loadSum();

for (field=0; field<arr.length-1; field++ ){
  for (for cell=0; cell<arr[field]; cell++){
    var iAns = 0;
    var sAns = "";
    for (sumFields=0;sumFields<arr.length-1; sumFields++){
      var thisFieldCellValue = parseInt(arr[sumFields].substring(cell,1));
      iAns += thisFieldCellValue;
      sAns += thisFieldCellValue;
    }
    if (iAns==lookingToMatchSum){
       document.write(sAns " is a hit!");
    }
  }
}

 

[rcgldr]

Not quite understanding this, if a row has n entries, then is what you want to do is generate sums for all combinations of n things taken 1 at a time, n things taken 2 at a time, n things taken 3 at a time, ... to n things taken n at a time?

 

[DrGreg]

Not quite understanding this, if a row has n entries, then is what you want to do is generate sums for all combinations of n things taken 1 at a time, n things taken 2 at a time, n things taken 3 at a time, ... to n things taken n at a time?

It took me a while to decipher what this question was about, but I worked it out eventually.

Look at the example given. The output is a table of 12 rows and 3 columns of digits.

Field 1 = 12 means that the first column contains '1' or '2'.
Field 2 = 678 means that the 2nd column contains '6' or '7' or '8'.
Field 3 = 45 means that the 3nd column contains '4' or '5'.
Field 4 = - means no more columns.

The table enumerates all possible combinations, a "is a hit" whenever the digits in a row add up to the target value (12).


As for the solution, my first thought is recursion. Have a function which loops through all the options for the first column, and for each option recursively calls itself to process the remaining columns. Is that a big enough clue, or do I need to spend time to flesh out the details?

Warning: recursion is potentially dangerous and you should encode a safety net to ensure you don't accidentally try to recurse to too great a depth for your stack to cope with.

 

[DaveC426913]

Not quite understanding this, if a row has n entries, then is what you want to do is generate sums for all combinations of n things taken 1 at a time, n things taken 2 at a time, n things taken 3 at a time, ... to n things taken n at a time?

One selection from every entry.

Look at these tables of input versus output:

Input:
12
678
45

Output:
164
165 *
174 *
175
184
185
264 *
265
274
275
284
285
* These ones sum to 12
So, my final output is three possibilities 165, 174, 264.


Another example: (I've added some complications: input numbers are not necessarily contiguous. Also, numbers cannot be used twice in output.)

Input:
46
5
78
689

Output:
4576
4578
4579
6586 (ignore, cannot reuse a number)
6588 (ignore, cannot reuse a number)
6589
6576 (ignore, cannot reuse a number)
6578 *
6579
6586 (ignore, cannot reuse a number)
6588 (ignore, cannot reuse a number)
6589
* These ones sum to 26.
So my final output is only one possibility: 6578.

It's particularly the iterating I'm struggling with. The tests and disqualifiers can be added after I get the iterating working.

 

[rcgldr]

OK, not all combinations from each field, but all combinations of 1 digit from each of the fields. The number of combinations is the product of the sizes of the fields. Instead of recursion, you could use an array of indexes and pointers to each field, advancing them similar to advancing an odometer, with the index of the last digit field cycling the fastest. You could use a second array to keep track of the number of instances each digit was previously used (0 would mean not used and available, 1 would mean number already used). To handle any "carries" that may occur each time you increment the "odometer", you'll need an index to the array of indexes for the fields; that index is initialized to index the last digit field. The incrementing is done in a loop and breaks out as soon as there are no carries. If there's a carry, the current field index is reset to the start of the field, if the index to the indexes is zero, you're done (use a return, goto, or set a flag to indicate done), otherwise the index to the indexes is decremented,, the loop continues, incrementing the next higher digit field. Each time an increment step is done, then the array of indexes is used to generate a sum for that combination of field digits.

 

[Grep]

I hope you can understand C++, because I wrote something that does roughly what you seem to want to do. It does use recursion, because there's no way I want to write that out without using recursion. You end up essentially having to keep your own "call stack" to keep track of where you are. It's a massive pain. Believe me, I've done it, and it gets annoying. It's no wonder you're having problems working it out without recursion.

I really wish C++ compilers did what ML does when you do recursion. The ML compiler works it out so it doesn't use a call stack the way C++ does, so you can use it with wild abandon without risking a stack overflow.

Anyways, it's quick and dirty code, totally uncommented, and certainly not tested that well. But it seems to work. Hope it's of use to you. I could rewrite it in Java if you really want. My knowledge of Javascript is sketchy at best.

My output:

--- Values ---
46
5
78
689
--- Output ---
4576
4578
4579
4586
4588 (ignore, cannot reuse a number)
4589 is a hit!
6576 (ignore, cannot reuse a number)
6578 is a hit!
6579
6586 (ignore, cannot reuse a number)
6588 (ignore, cannot reuse a number)
6589

And the code:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void doit(vector<string>& arr, int target, int currentRow, int currentSum,
          vector<int> digitsUsed, vector<int> currentDigits)
{
    int digit = 0;

    for (int i = 0; i < arr[currentRow].size(); i++)
    {
       digit = arr[currentRow][i] - '0';
       ++digitsUsed[digit];
       currentDigits.push_back(digit);

       if (currentRow < arr.size()-1)
       {
           doit(arr, target, currentRow+1, currentSum+digit,
           digitsUsed, currentDigits);
       }
       else
       {
           for (int j = 0; j < currentDigits.size(); j++)
           {
              cout << currentDigits[j];
           }

           bool isRepeats = false;
           for (int j = 0; j < 10; j++)
           {
               if (digitsUsed[j] > 1)
               {
                   isRepeats = true;
                   break;
               }
           }

           if (isRepeats)
           {
               cout << " (ignore, cannot reuse a number)" << endl;
           }
           else if (currentSum+digit == target)
           {
               cout << " is a hit!" << endl;
           } else {
               cout << endl;
           }
       }
       currentDigits.pop_back();
       --digitsUsed[digit];
    }
}

int main(int argc, char *argv[])
{
    vector<int> digitsUsed(10, 0);
    vector<string> arr;
    vector<int> currentDigits;

    arr.push_back("46");
    arr.push_back("5");
    arr.push_back("78");
    arr.push_back("689");

    cout << "--- Values ---" << endl;
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << endl;
    }

    cout << "--- Output ---" << endl;
    doit(arr, 26, 0, 0, digitsUsed, currentDigits);
}

 

[DaveC426913]

It took me a while to decipher what this question was about, but I worked it out eventually.

Look at the example given. The output is a table of 12 rows and 3 columns of digits.

Field 1 = 12 means that the first column contains '1' or '2'.
Field 2 = 678 means that the 2nd column contains '6' or '7' or '8'.
Field 3 = 45 means that the 3nd column contains '4' or '5'.
Field 4 = - means no more columns.

The table enumerates all possible combinations, a "is a hit" whenever the digits in a row add up to the target value (12).


As for the solution, my first thought is recursion. Have a function which loops through all the options for the first column, and for each option recursively calls itself to process the remaining columns. Is that a big enough clue, or do I need to spend time to flesh out the details?

Warning: recursion is potentially dangerous and you should encode a safety net to ensure you don't accidentally try to recurse to too great a depth for your stack to cope with.

Hm. I hadn't thought of recursion; I was busy working on nested loops. Thanks, I'll think that through.

Funny, this problem is really quite simple for a human. Doing it on paper is almost trivial.That first example, 12, 678, 45 can be done in my head in about thirty seconds. In fact, its very triviality is what's been confounding me; we assign pointers, counters and loops to positions in the physical array so effortlessly that we're not even aware we're doing it. But translating those implicit mental tricks into explicit structures and lines of code is extremely challenging.

 

[DaveC426913]

I hope you can understand C++, because I wrote something that does roughly what you seem to want to do. It does use recursion, because there's no way I want to write that out without using recursion. You end up essentially having to keep your own "call stack" to keep track of where you are. It's a massive pain. Believe me, I've done it, and it gets annoying. It's no wonder you're having problems working it out without recursion.

C++ won't be a problem. I'll look over your ideas, thanks!

BTW, if anyone wants to know the application for this algorithm, I do these:
http://www.freexsums.com/
Of course the ones there are incredibly simple, they take about ten minutes to complete with one eye tied behind my back. The ones I prefer can easily take more than an hour.

I'm not cheating, I'm automating a specific task, to be used under only certain conditons. A more likely input is like this (actual example):
789
123456
15789
1234
1234
12
=31

So, that's a result table of 2880 possible combinations. A few more than 12... :tongue:

 

[Grep]

C++ won't be a problem. I'll look over your ideas, thanks!

Excellent! And it's my pleasure.

BTW, if anyone wants to know the application for this algorithm, I do these:
http://www.freexsums.com/
Of course the ones there are incredibly simple, they take about ten minutes to complete with one eye tied behind my back. The ones I prefer can easily take more than an hour.

I admit I was really wondering why you wanted to do that.

I'm not cheating, I'm automating a specific task, to be used under only certain conditons.

I'm not one to criticize. You should see what I did to help me solve cryptograms a while back!

So, that's a result table of 2880 possible combinations. A few more than 12... :tongue:

Luckily, the maximum recursion level is the number of "fields". Even in that example, it's only 6. For that application, you should have no worries about stack overflow.

Well, have fun!

 

[rcgldr]

update - I included sample code that displays all the combinations of field digits using the non-recursive odometer method. A vector of indexes (vFieldIndexes) for the fields of digits is incremented like an odometer to generate test strings (one at a time) that cycle through all the combinations, treating each field as the displayed digits of that odometer. As each field cycles through all of it's digits, then next higher field is advanced one digit. For the actual code, instead of just displaying each test string of digits, the code would perform the same tests asked for in the OP.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
    size_t i;
    vector<string> vFields;

    vFields.push_back("46");
    vFields.push_back("5");
    vFields.push_back("78");
    vFields.push_back("689");

    string sTest(vFields.size(), 0);
    vector<size_t> vFieldIndexes(vFields.size(), 0);

    while(1){
        // generate a test string of digits from the fields and display it
        for(i = 0; i < vFields.size(); i++)
            sTest[i] = vFields[i][vFieldIndexes[i]];
        cout << sTest << endl;

        // advance to next string of digits
        i = vFields.size() - 1;       // set i for last field
        while(1){                     // advance to next digit in current field
            if((++vFieldIndexes[i]) < vFields[i].size())
                break;                // back to main loop if not end of field
            vFieldIndexes[i] = 0;     // reset current field index
            if((--i) != (size_t)(-1)) // back up one field
                continue;
            return(0);                // if all fields done, exit
        }
    }
}

 

[DaveC426913]

A vector of indexes (vFieldIndexes) for the fields of digits

This is what I kept starting to build. I'd get half way thorugh, and I'd be thinking there was a more elegant way to do it that didn't require extraneous storage of variabless. But it got away from me every time.

 

[rcgldr]

A vector of indexes (vFieldIndexes) for the fields of digits

This is what I kept starting to build. I'd get half way through, and I'd be thinking there was a more elegant way to do it that didn't require extraneous storage of variables. But it got away from me every time.

You need some method to index through all of the elements in all the fields, either using multiple indexes from an array or multiple indexes through recursion, or as an alternative, you could increment a single number, then use modulo and divide to break up that number into indexes, similar to doing a conversion from binary to decimal, but the single number would have to have enough bits to represent the product of the sizes of all the fields. I'm not sure that the division approach is more elegant though. The trade off would be a number of divisions to dynamically generate indexes as opposed to maintaining a number of indexes stored in memory.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
    size_t i;
    int loop;
    int maxloop;
    int dividend;
    vector<string> vFields;

    vFields.push_back("46");
    vFields.push_back("5");
    vFields.push_back("78");
    vFields.push_back("689");

    string sTest(vFields.size(), 0);
    maxloop = 1;
    for(i = 0; i < vFields.size(); i++)
        maxloop *= vFields[i].size();

    for(loop = 0; loop < maxloop; loop++){
        // generate a test string of digits from the fields and display it
        dividend = loop;
        for(i = vFields.size(); i;){
            i--;
            sTest[i] = vFields[i][dividend % vFields[i].size()];
            dividend /= vFields[i].size();
        }
        cout << sTest << endl;
    }
}

 

[cobalt124]

Given it's the iteration that's the problem here, I tried to think of a solution where the iteration part was easy, and came up with the following high level pseudocode:

1) Calculate the number of permutations, perm-tot

2.1) Loop perm-tot times
2.2) ---Loop through each row /*----------------------//--------------------------------*/
2.3) ------select relevant digit from row /*-------------// generates a single permutation--*/
-----------if there are no duplicate digits in the permutation
-------------total the digits in the permutation
-------------if the total is the required total
---------------success

Obviously it all hinges on whether line 2.3 is possible. I believe it is, and think I am close to a solution which I will post when I get chance to look at it again, it's looking equally horrible to be honest, but it's an interesting problem.

 

[rcgldr]

1) Calculate the number of permutations, perm-tot

Which is the first loop used to calculate maxloop in post #12.

2.1) Loop perm-tot times

The outer loop in post #12.

2.2) Loop through each row
2.3) select relevant digit from row - generates a single permutation

The inner loop in post #12 (using modulo and division to index the rows) to create a single permutation in string sTest for each loop.

 

[cobalt124]

Yes, apologies, I rushed straight into the problem and didn't give your responses the attention they deserved. Also I am a poor reader of C++ these days, but I'm going to look at the inner loop of post #12 to see how that bit works. I wasn't even sure it was the best way to do it, it was just simple from an iterative point of view.