I am currently working on a little program that's supposed to find every combination.

Fill the following place holders with digits in the range from 1 to 9. Each digit only appears once and make the equation sum up to 100.

_ / _ * _ _ * _ * _ / _ _ * _ = 100

#include <bits/stdc  .h>
#include <cmath>

using namespace std;

void print(int arr[], int n){
    for (int i = 0; i < n; i  ){
        cout << arr[i] << " ";
    }
    cout << endl;
}

void findCombos(int arr[], int n){
    std::sort(arr, arr   n);
    do{
        if((arr[0] / arr[1] * arr[2]   arr[3] * arr[4] * arr[5] / arr[6]   arr[7] * arr[8]) == 100){
            print(arr, n);
        }
    }while(next_permutation(arr, arr   n));
}

int main(){
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    findCombos(arr, size);

    return 0;
} 

I generated 900 solutions with this code. Some of the permutations are correct, but some of the combinations do not calculate exactly to 100. My if statement is matching up the operations correctly, but why are the incorrect permutations displaying? As an extension, how can I make this program run recursively?

CodePudding user response：

You are dividing integers, which truncates the result. If you divide 9 by 2 as integers the result will be 4 and not 4.5. This means the value calculated by your program will not be correct.

CodePudding user response：

As PiedPiper already mentioned about the integer division issue, you can simply declare the arr[] as double and it solves the issue.

As an extension, you can also calculate the permutations using a recursive way. Please check the function findCombosRecursive() which have similar functionality as findCombos() but making the combinations recursively.

The recursive algorithm partitions arr as two parts: the already permuted elements and the remaining unchanged elements. The parameter curr indicates the pivot in between these two parts. Every time we make a swap between the pivot element and the remaining unchanged elements and advance the pivot position by one. Once we reached to the end of the array, we get a new permutation of the array and check whether this permutation satisfy our necessary condition. Do not forget to restore the position after the recursive calls. This will ensure that the pivot position is exchanged with just another remaining elements in a single permutation construction.

Here I have shared a sample implementation of constructing the solution recursively:

#include <bits/stdc  .h>
#include <cmath>

using namespace std;

void print(double arr[], int n, int sid) {
    cout << "Solution " << sid << ":";
    for (int i = 0; i < n; i  ){
        cout << " " << arr[i];
    }
    cout << endl;
}

void findCombosRecursive(double arr[], int size, int curr, int& sid) {
    if (curr == size) {     // base-case of the recursion
        // check whether the current combination satisfy the following condition:
        // "_ / _ * _   _ * _ * _ / _   _ * _ = 100"
        if((arr[0] / arr[1] * arr[2]   arr[3] * arr[4] * arr[5] / arr[6]   arr[7] * arr[8]) == 100){
            print(arr, size, sid);
            sid  = 1;
        }
    } else {
        for (int i = curr; i < size; i =1) {
            swap(arr[i], arr[curr]);
            findCombosRecursive(arr, size, curr   1, sid); // placing next position
            swap(arr[i], arr[curr]);  // restoring
        }
    }
}

void findCombos(double arr[], int n){
    std::sort(arr, arr   n);
    int i = 0;
    do{
        if((arr[0] / arr[1] * arr[2]   arr[3] * arr[4] * arr[5] / arr[6]   arr[7] * arr[8]) == 100){
            print(arr, n, i);
            i  = 1;
        }
    } while(next_permutation(arr, arr   n));
}

int main(){
    double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int sid = 0;
    findCombosRecursive(arr, size, 0, sid);
    // findCombos(arr, size);

    return 0;
}