Velocity Reviews > C++ > Re: Recursive combinations algorithm

# Re: Recursive combinations algorithm

alexey.pyatovskiy@gmail.com
Guest
Posts: n/a

 02-15-2005
Could you please explain what is the NullSet - are you emptying the
set? I am lost..

> You still have too many loops, a good sign that you haven't found an
> "elegant" recursive solution.
> Consider: You can divide the subsets of {a, b, c, d} into two groups:
> subsets containing a and subsets not containing a.
> The second case gives you an obvious recursion on {b, c, d}. What

> the first case? It simply the subsets of {b, c, d} with a added to

each
> one!
>
> Comb( Set CurrentSet, Set ElementsToAdd = NullSet )

//here - what is NullSet?

> {
> if( CurrentSet.IsEmpty() )
> {
> }
> else
> {
> Element x = CurrentSet.GetFirstElement();
> Comb( CurrentSet - x, ElementsToAdd + x );
> Comb( CurrentSet - x, ElementsToAdd );
> }
> }
>
> This assumes the existence of a Set class (not quite the same as the
> standard C++ set template) with the appropriate member functions. In
> particular, the + and - operators should return a copy of the left

hand
> operand with the right hand operand inserted and deleted

respectively.
>
> Seth Jones