how do I get all combinations of elements in a list?

Question

When getting a list of X elements, how can I get all doubles, triples, ... ( Y ) combinations of these elements ?
Y being the size of the required combinations. Ex : if Y = 2, I need to get all of the possible pairs.
I must not give the same combinations twice ( ex : [a, b] and [b, a] are the same combination )

Answer 1

Take a copy of the list.

If the list is empty, there are no combinations.

To get all combinations of size one, look at each element in turn.

To get all combinations of size n+1, first remove the first element. Then get all combinations of size n of the rest of the list, plus that first element. Then get all combinations of size n+1 of the rest of the list, and don't add the first element.

And then you are done.

You can get fancy and merely pretend to copy/remove elements for optimization sake.

Answer 2

You can iterate t from 2 to Y, and create an array A with the size X fill with X-t 0s in the front and t 1s in the back, then with the code below:

do{
    //1s in array A now correspond to a valid combination
}while(std::next_permutation(A,A+X));

The loop will stop when all combination with size t are iterated

next_permutation is in header algorithm, it will reorder the array to the next lexicographically greater permutation or return false if the array is already in the lexicographically greatest permutation. Its complexity is O(n), since you also need to iterate through the array once, so it wouldn't be a problem. Total complexity for the whole process will be bounded by O(2^n*n).

So here is an example pseudo code

D[X] = {1,2,3,4} Y = 3 //the input
For t = 2,3,..,Y
    A[X] = {0,...,0,1,...,1} // X - t 0s and t 1s 
    Do
        For j = 0,1,...,X-1
            if A[j] == 1
                output D[j]
            end if
        end for
        output newline
    While next_permutation(A,A+X)
end for

The output will looks like

3 4
2 4
2 3
1 4
1 3
1 2
2 3 4
1 3 4
1 2 4
1 2 3