I have n integer arrays. I want to iterate over every combination of elements from each array. For example, if:

A = [1, 4, 5]
B = [3, 7, 9]
C = [2, 0, -6]

A possible combination would be [1, 7, 0].

Each iteration, I want to check if the sum of the combination is equal to a certain number.

I tried to do that by first generating the cartesian product and then iterating over every single combination. The probkem is that even if I had only 7 array with 10 elements each, the cartesian product's length 10,000,000, and so it's not very efficient.

Is there a known algorithm for this problem? Something like sliding window, but for this case?

CodePudding user response：

Since you have an array of n arrays, you can create an array of n indices and take each possible index value one by one.

In C , it would look like this:

std::vector<std::vector<int>> inputs; // n input arrays
std::vector<std::size_t> indices(inputs.size(), 0); // n indices, initialized to 0

bool looped_over_all_combinations = false;
while (!looped_over_all_combinations) {
    int sum = 0;
    for (auto i = 0u; i < inputs.size();   i) {
        sum  = inputs[i][indices[i]];
    }
    if (sum == target_number) {
        // do something
    }

    // next combination
    auto i = indices.size() - 1;
    while (indices[i] == inputs[i].size() - 1) {
        indices[i] = 0;
        if (i == 0) {
            looped_over_all_combinations = true;
            break;
        }
        --i;
    }
      indices[i];
}

Demo

The summing part and the next combination part should both be functions, but hopefully this gives you the idea.

CodePudding user response：

I think this is a variation of the knapsack problem so this is also an NP complete problem, but I implemented a faster DP based solution!

def solve(arrays, goal):
    dp = dict()
    for arr_ind, arr in enumerate(arrays):
        temp_dp = dict()
        for v in arr:
            for k in list(dp.keys()):
                if not arr_ind or len(dp[k]) == arr_ind:
                    temp_dp[v   k] = dp[k]   (v,)
            if not arr_ind:
                temp_dp[v] = (v,)
        for k, v in temp_dp.items():
            dp[k] = v
            
    if goal in dp:
        return dp[goal]
    return []

This solution takes one number from every single array and tries to sum that into to the goal value.