Geek Answers Handbook

Which is the best way to generate a selection from a given set of numbers?

for example, if it is set to select all options from 1 to 5, and the answer will look 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 quick algorithm?

+4
source share
6 answers

Just generate all integers from one (or zero if you want to include an empty set) in 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 a subset of {C, D}.

+18
source

Do you want to find poweret

 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 a power search algorithm in 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 simple way to do this is described in the answers above. Here is a link that explains this in detail.

+1
source

The fastest of them: a metaprogramming template that will trade compilation time and code size for runtime. But it will be practical only for a low number of combinations, and you should know them in advance. 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 method creates all combinations at compile time.

+1
source

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

0
source

can anyone suggest a quick algorithm?

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

 power [] = [[]] power (x:xs) = rest ++ map (x:) rest where rest = power xs
0
source

You want combinations, not permutations (ie {1,2} to be the same as {2,1})

C (n, k) = n! / (K! (Nk)!)

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

  ( ie C(n,1)+C(n,2)...+C(n,n) )
0
source

More articles:


All Articles