CODEWITHSUNDEEP
c++algorithmmathcombinationsnested-loops
tom
tom

Reputation: 485

C++, not in order combination of array elements

I am trying to get all combinations of an array with C++ such that

double* list1 = new double[size];

Items in that array is {1,2,3,4,5}

I need to add all possible combinations into a stack, such as:

1+2, 1+2+3, 1+2+3+4，1+2+3+4+5, 1+3, 1+3+4, 1+3+4+5, 1+4, 1+4+5, 1+5...

the problem I am running into is I am doing this through 2 for loops and a while loop

for(int i = 0; i < size - 1; i++)
{
    for(int j = i; j < size - 1; j++)
    {
        double temp = list1[i] + list1[j + 1];
        list1combos.push(temp);
        int k = j + 2;
        while (k <= size - 1)
        {
            temp = temp + list1[k];
            list1combos.push(temp);
            k++;
        }
    }
}

I can get the ones I listed above but I have no clue how to code in combinations such as 1+3+5, or 1+2+5

Please advise on how to get those combinations, thanks stackoverflow!

Upvotes: 1

Views: 208

Answers (4)

Jarod42
Jarod42

Reputation: 217293

Following may help: http://ideone.com/SpCejs

template <std::size_t N>
bool increase(std::bitset<N>& bs)
{
    for (std::size_t i = 0; i != bs.size(); ++i) {
        if (bs.flip(i).test(i) == true) {
            return true;
        }
    }
    return false;
}

template <typename T, std::size_t N>
void print_combinaison(const std::array<T, N>& a)
{
    std::bitset<N> bs;

    do {
        for (std::size_t i = 0; i != N; ++i) {
            if (bs.test(i)) {
                std::cout << a[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (increase(bs));
}

Upvotes: 0

Nik Bougalis
Nik Bougalis

Reputation: 10613

Others have already answered your question. I'll point out one important thing:

double* list1=new double(size);

This does not allocate an array of double with size elements.

Instead it allocates a single double and sets the value of it to size. Attempting to access it as an array results in undefined behavior and could lead to a crash.

You want to do this instead:

double* list1=new double[size];

Notice the use of square brackets. Also remember that you must call delete[] list1; instead of simply delete list1; when you want to release the allocated memory.

Upvotes: 0

4pie0
4pie0

Reputation: 29724

You can approach this problem by printing all subsets of a set {1,2,3,4,5}. There are 2^5 of them - or 2^5-1 since set {0) is meaningless for you.

This code can help you.

#include<iostream>
#include<list>
#include <iterator>

void print( std::list<int> l){
    std::copy( l.begin(), l.end(), std::ostream_iterator<int>( std::cout, " "));
    std::cout << std::endl;
}

void subset( int arr[], int size, int left, int index, std::list<int> &l){
    if( left == 0){

        print(l);
        return;
    }

    for( int i = index; i < size; i++){
        l.push_back( arr[i]);
        subset( arr, size, left - 1, i + 1, l);
        l.pop_back();
    }

}     

int main() {
    int array[5] = { 1, 2, 3, 4, 5} ;
    std::list<int> lt;   
    subset( array, 5, 1, 0, lt);
    subset( array, 5, 2, 0, lt);
    subset( array, 5, 3, 0, lt);
    subset( array, 5, 4, 0, lt);
    subset( array, 5, 5, 0, lt);

    return 0;
}

http://ideone.com/J78J7q

more algorithms for subsets: generate all subsets of size k from a set

Upvotes: 0

Alexandru Barbarosie
Alexandru Barbarosie

Reputation: 2992

Since the order does not matter, I would suggest having an array of the same size as your x and perform a binary increment on it, i.e. you start with the array inited to only 0s and count until you have only 1s. For every addition of a 1 you would pick a permutation from your x array.

First iteration:
0 0 0 0 0 -> empty
Second iteration:
0 0 0 0 1 -> you pick 5
3rd iteration:
0 0 0 1 0 -> you pick 4
4th iteration:
0 0 0 1 1 -> you pick 4 and 5
And so on until you reach:
1 1 1 1 1 -> you pick 1, 2, 3, 4 and 5

Upvotes: 1

Related Questions