C++, not in order combination of array elements

Question

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!

sorry that was unclear, it should have been double list1[5], well I am actually using a dynamic array where double *list1=new double[size], I have changed the main post for clarity — tom, Jun 09 '14 at 18:26
@tom: Actually, the issue is you declared it as having a size of 4 but specified 5 elements. — Dave S, Jun 09 '14 at 18:26
Since the amount of loops is theoretically infinite in this situation, it is easier to write this algorithm via recursion. — keiv.fly, Jun 09 '14 at 18:30
i have a proper answer but it takes me time to add here..so i can only post it if you stil need sthe answer..otherwise i will not post :) — Wasim Ahmed, Jun 11 '14 at 13:51
@WasimAhmed thanks I have already figured this out with the binary array method, http://stackoverflow.com/questions/24129078/optimize-binary-increment-loop/24129832#24129832, thats what I did for this case, no worries if its too much trouble since its not homework or anything, just a side project im doing for work :) — tom, Jun 12 '14 at 16:58

score 1 · Accepted Answer · answered Jun 09 '14 at 18:28

1

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

answered Jun 09 '14 at 18:28

Alexandru Barbarosie

2,952
3
24
46

I get the concept of it having all the combinations of 1,2,3,4,5 but how do I execute this in code? – tom Jun 09 '14 at 18:37
Do you really need an explicit tutorial on how to iterate over binary numbers? Sorry to be rude but show some effort mate. Alternatively I'd ask another question ;) – luk32 Jun 09 '14 at 18:56
@luk32 yeah you are right that was probably a bit lazy on my end, i have no clue what you mean by another questions tho, shed some light? – tom Jun 09 '14 at 19:07
A follow up question. "How do I iterate over a numbers in binary mode?" or something. Try something, if you have troubles ask a question. It's fine even if it is very simple as long as you show some genuine effort. Also look around in the internet. The problem you are given now is probably more popular and already solved. – luk32 Jun 09 '14 at 19:19
@tom By binary addition, addition mod 2 is assumed i.e. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 and 1 carry. – Alexandru Barbarosie Jun 09 '14 at 22:31

score 0 · Answer 2 · edited May 23 '17 at 12:14

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

score 0 · Answer 3 · answered Jun 09 '14 at 19:41

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.

score 0 · Answer 4 · answered Jun 09 '14 at 19:46

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));
}

C++, not in order combination of array elements

4 Answers4

Linked