which is the best way to generate choices out of a given set of numbers?

Question

for example if it is given to make all the choices between 1 to 5 and the answer goes like this..

1,2,3,4,5,  
1-2,1-3,1-4,1-5,2-3,2-4,2-5,3-4,3-5,4-5,  
1-2-3,1-2-4,1-2-5,1-3-4,
.....,
1-2-3-4-5.

can anyone suggest a fast algorithm?

Answer 1

Just generate all the integers from one (or zero if you want to include the empty set) to 2^N - 1. Your sets are indicated by the set bits in the number. For example if you had 5 elements {A,B,C,D,E} the number 6 = 00110 would represent the subset {C,D}.

Answer 2

What you want is called choose in combinatorics. This and this should get you started.

Answer 3

You want to find the powerset

In mathematics, given a set S, the power set (or powerset) of S, written , 
P(S), , is the set of all subsets of S

There is an algorithm to find the power set at this link.

You basically take first element say 1 and find a all subsets {{},{1}}. Call this 
power set
Take next element 2 and add to powerset and get {{2},{1,2}} and take union
 with powerset.
{{},{1}} U {{2},{1,2}} = {{},{1},{2},{1,2}}

But a easy way to do it is described in the answers above. Here is a link which explains it in detail.

Answer 4

can anyone suggest a fast algorithm?

Algorithms can be expressed in many languages, here is the power set in Haskell:

power [] = [[]]

power (x:xs) = rest ++ map (x:) rest
  where rest = power xs

Answer 5

The fastest is by using template metaprogramming, which will trade compile time and code size for execution time. But this will only be practical for lowish numbers of combinations, and you have to know them ahead of time. But, you said "fast" :)

#include <iostream>
using namespace std;

typedef unsigned int my_uint;

template <my_uint M>
struct ComboPart {
    ComboPart<M-1> rest;

    void print() {
        rest.print();
        for(my_uint i = 0; i < sizeof(my_uint) * 8; i++)
            if(M & (1<<i)) cout << (i + 1) << " ";
        cout << endl;
    }
};

template <>
struct ComboPart<0> {
    void print() {};
};

template <my_uint N>
struct TwoPow {
    enum {value = 2 * TwoPow<N-1>::value};
};

template <>
struct TwoPow<0> {
    enum {value = 1};
};

template <my_uint N>
struct Combos {
    ComboPart<TwoPow<N>::value - 1> part;
    void print() {
        part.print();
    }
};

int main(int argc, char *argv[]) {
    Combos<5> c5 = Combos<5>();
    c5.print();

    return 0;
}

This one constructs all the combinations at compile time.

Answer 6

You want combinations, not permutations (i.e. {1,2} is the same as {2,1})

C(n,k) = n!/(k!(n-k)!)

Answer = sum(k = 1 to n) C(n,k)

      ( i.e. C(n,1)+C(n,2)...+C(n,n) )