CODEWITHSUNDEEP
c++arrays
Tanmay Sharma
Tanmay Sharma

Reputation: 59

How do you generate subarrays of an array with specific number of elements and then store it in another array?

What I need to do is to create subarrays of an existing array and the subarray should have a given number of elements.

For eg. if I have the array [1,2,3,4] and I need to generate subarrays of it with exactly three elements, I would want the a separate 2-d array to include the following arrays:

[1,2,3]

[1,2,4]

[1,3,4]

[2,3,4]

and so on and so forth.

Thank you in advance.

Upvotes: 0

Views: 302

Answers (1)

Pepijn Kramer
Pepijn Kramer

Reputation: 12849

You can do it by first calculating how many combinations there are by picking 3 elements in a group of 4 and what these combinations look like. Then you can use these combinations to pick elements from your input and create output like this :

#include <cassert>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <set>

// calculate numbers of ways in which we can pick number_of_elements_to_pick from
// number_of_elements
auto get_combinations_of_indices_to_pick(std::size_t number_of_elements_to_pick, std::size_t number_of_elements)
{
    assert(number_of_elements > number_of_elements_to_pick);

    // set which element to pick to true for number_of_elements_to_pick
    std::vector<bool> pick_element_n(number_of_elements_to_pick, true);

    // and the rest to false (we will not pick out those indices)
    pick_element_n.insert(pick_element_n.end(), number_of_elements - number_of_elements_to_pick, 0);

    // the total number of combinations is the number of permutations of the bits.
    std::vector<std::vector<std::size_t>> combinations;
    do
    {
        std::vector<std::size_t> combination;
        for (std::size_t i = 0; i < number_of_elements; ++i)
        {
            if (pick_element_n[i]) combination.push_back(i);
        }
        combinations.push_back(combination);
    } while (std::prev_permutation(pick_element_n.begin(), pick_element_n.end()));

    return combinations;
}

int main()
{
    std::vector<int> input{ 1,2,3,4 };

    // get combinations of 3 indices to pick from input vector
    auto combinations = get_combinations_of_indices_to_pick(3, input.size());       

    // there will be a vector of vectors as output
    std::vector<std::vector<int>> outputs;
    outputs.reserve(combinations.size());

    // loop over all combinations of indices
    for (const auto& combination : combinations)
    {
        std::vector<int> output;
        // foreach combination of indicices to pick
        // add input for that index to the output for this combination
        for (const auto index : combination)
        {
            output.push_back(input[index]);
        }

        // then add this selected subvector to the outputs
        outputs.push_back(output);
    }


    // show the possible output vectors
    for (const auto& output : outputs)
    {
        bool comma = false;
        for (const auto& value : output)
        {
            if (comma) std::cout << ", ";
            std::cout << value;
            comma = true;
        }
        std::cout << "\n";
    }
}

Note : The number of possible combinations can get very big very quickly. And usually there is a faster way of solving problems then just blindly go over all the possible combinations.

Upvotes: 2

Related Questions