I have a problem with passing subsets to a vector. I am trying to rewrite code from Java to C . An-CodePudding

I have a problem with passing subsets to a vector. I am trying to rewrite code from Java to C . Any suggestions? The program is supposed to print all possible combinations of r elements in a given array of size n.

Code

// The main function that prints
// all combinations of size r
// in arr[] of size n. This function
// mainly uses combinationUtil()
vector<vector<int>> getCombinations(const vector<int>& list, int r) {
    // A temporary array to store
    // all combination one by one
//    int data[r];
    vector<vector<int>> resultSet = vector<vector<int>>();

//list = u
    // Print all combination using
    // temporary array 'data[]'
//   combinationUtil(arr, data, 0, n-1, 0, r);
    return combinationUtil(list, list.size(), r, 0, vector<int>(), 0, resultSet);
}

/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and
Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
vector<vector<int>> combinationUtil(vector<int> list, int n, int r, int index, vector<int> result, int i, vector<vector<int>> resultSet) {
    // Current combination is ready
    // to be printed, print it
    if (index == r) {
        vector<int> variant = vector<int>();
        for (int j = 0; j < r; j  ) {
            variant.push_back(result.at(j)); "";
        }
        resultSet.push_back(variant);
        return resultSet;
    }

    // replace index with all possible
    // elements. The condition "end-i 1 >= r-index"
    // makes sure that including one element
    // at index will make a combination with
    // remaining elements at remaining positions
    if (i >= n) {return resultSet;}

    // current is included, put next at next
    // location
    result.insert(result.begin()   index, list.at(i));
    combinationUtil(list, n, r, index   1, result, i   1, resultSet);

    // current is excluded, replace it with
    // next (Note that i 1 is passed, but
    // index is not changed)
    combinationUtil(list, n, r, index, result, i   1, resultSet);
    return resultSet;
}

CodePudding user response：

Are you sure you know both languages good enough to do translation? E.g. your code creates a lot of copies of vectors. It's actually most used operation there. ANd this part looks suspicious, does it work right?

vector<vector<int>> calculate(vector<int> inputSet) {
    log(inputSet);
    vector<int> result = vector<int>();

    for (int i = 0; i < inputSet.size(); i  ) {
        result.push_back(inputSet.at(i));
        if (sum(result) > sum(inputSet) - sum(result)) {
            cout << i   1 << "elementow" << endl;
            //tutaj ta funkcja zwracająca pozdbiory
            break;
        }
    }
    cout << "Nie znaleziono zbioru spelniajacego wymagania" << endl;
    return {};
}

int sum(vector<int> vector) {
    return accumulate(vector.begin(), vector.end(), 0);
}

calculate always returns an empty vector. It performs N*3 2 copies of vector inputSet and summarily O(3*N*(N 1)) operations, where N is size of that vector. You perhaps need to alias your types, e.g and pass by value:

    using VectorInt = vector<int>;
    using VectorInt2D = vector<vector<int>>>;


    void /*VectorInt2D*/  calculate(const VectorInt&  inputSet) {
        log(inputSet);
        int result = 0, inputSum = sum(inputSet);

    
        for (int i = 0; i < inputSet.size(); i  ) {
            result  = inputSet[i];
            if (result  > inputSum  - result ) {
                cout << i   1 << "elementow" << endl;
                //tutaj ta funkcja zwracająca pozdbiory
                break;
            }
        }
        cout << "Nie znaleziono zbioru spelniajacego wymagania" << endl;
        //return {};  // what we return here?
    }
    
    int sum(const VectorInt&  vector) {
        return accumulate(vector.begin(), vector.end(), 0);
    }

I suspect that you don't realize that in C all parameters are passed by value while in Java all parameters are passed by reference. Function with signature

vector<vector<int>> combinationUtil(vector<int> list, int n, int r, int index, 
vector<int> result, int i, vector<vector<int>> resultSet)

cannot change vector passed as argument for parameter resultSet. Maybe it shouldn't even try but it looks necessary for recursion.

vector<vector<int>> getCombinations(const vector<int>& list, int r) {
    // A temporary array to store
    // all combination one by one
//    int data[r];
    vector<vector<int>> resultSet = vector<vector<int>>();

//list = u
    // Print all combination using
    // temporary array 'data[]'
//   combinationUtil(arr, data, 0, n-1, 0, r);
    return combinationUtil(list, list.size(), r, 0, vector<int>(), 0, resultSet);
}

resultSet is not a temporary. That's a local automatic variable and it gets copied when passed to combinationUtil and copied again when returned. It cannot be changed by recursive calls of combinationUtil. Whole thing looks flawed and seemed worked only in original language.

CodePudding user response：

The declaration:

vector<vector<int>>
combinationUtil(vector<int> list, int n, int r, int index, vector<int> result, int i, vector<vector<int>> resultSet); // <-- returns a vector of vectors

The calls:

result.insert(result.begin()   index, list.at(i));
combinationUtil(list, n, r, index   1, result, i   1, resultSet); // <-- the result is discarded

// current is excluded, replace it with
// next (Note that i 1 is passed, but
// index is not changed)
combinationUtil(list, n, r, index, result, i   1, resultSet); // <-- the result is discarded

return resultSet;

If you don't need the return value, why are you returning it?

This kind of coding might work in Java, where most things are references, but not in C . combinationUtil receives all arguments by value, and uses no global variables, so thee only way it can influence it surroundings is by returning a value. If you discard the returned value, you just turn the function into a (very, very expensive) no-op.

One way to fix the problem is to stop discarding the return value.

resultSet = combinationUtil(list, n, r, index, result, i   1, resultSet);

A more efficient way is to pass resultSet by reference, and stop returning a value from it, since now the function works by modifying its argument.

void
combinationUtil(vector<int> list, int n, int r, int index, vector<int> result, int i, vector<vector<int>>& resultSet); // adjust calls accordingly

This does not address complexity of the whole solution. The combinations algorithm is exponential (n choose r to be precise) and no amount of fiddling with references can change that. The problem, as I understand it, can be solved with a much more asymptotically efficient algorithm.

CodePudding user response：

Unrelated to your code.

There are many possible solutions

Using recursion. This is a complicated and the most inefficient solution
Using a selector array and permutations of it. This is the default standard approach.

I will show the default standard approach below.

The idea is that we have a selector array in parallel to the original data array. In this selector array, we set as much bits as the subset should be in size. And then we do all permutations for the selector array and use a value from the original array, if the corresponding selector is set.

Example for subset size of 2:

Base Data:  1,2,3,4

            ^ ^ ^ ^
            | | | |

Selector:   0,0,1,1  --> 3,4
            0,1,1,0  --> 2,3
            0,1,0,1  --> 2,4
            1,0,0,1  --> 1,4
            1,0,1,0  --> 1,3
            1,1,0,0  --> 1,2

The really simple code will then look like:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using MyType = int;
using Data = std::vector<int>;
using Combinations = std::vector<Data>;

Combinations getCombinations(const Data& data, const size_t subSetSize) {

    // Define the selector with the same size as the input data vector
    std::vector<bool> selector(data.size());

    // Set subSetSize elements in the selector element to true
    std::fill(selector.begin(), std::next(selector.begin(),subSetSize), true);

    // Here we will store the resulting values
    Combinations result{};

    // Here we will create the subsets. All values will be overwritten in every loop run. No need for clear or something
    Data subset(subSetSize);

    do {
        // Create the subset
        std::copy_if(data.begin(), data.end(), subset.begin(), [&, i=0u](const MyType m) mutable { return selector[i  ]; });
        result.push_back(subset);

            // Create the next permutation
    } while (std::prev_permutation(selector.begin(), selector.end()));

    return result;
}

int main() {
    Data data{ 1,2,3,4,5,6,7,8 };

    for (const Data& d : getCombinations(data, 4)) {
        for (const MyType& t : d) std::cout << t << ' ';
        std::cout << '\n';
    }
}