/**********************************************************************
  *                                                                    *
  * Copyright (c) 2003 INFN - Sezione di Napoli                        *
  *                                                                    *
  * For more information (including a list of authors) see             *
  * the README file                                                    *
  *                                                                    *
  * This library is free software; you can redistribute it and/or      *
  * modify it under the terms of the GNU General Public License        *
  * as published by the Free Software Foundation; either version 2     *
  * of the License, or (at your option) any later version.             *
  *                                                                    *
  * This library is distributed in the hope that it will be useful,    *
  * but WITHOUT ANY WARRANTY; without even the implied warranty of     *
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the       *
  * GNU General Public License for more details.                       *
  *                                                                    *
  * You should have received a copy of the GNU General Public License  *
  * along with this library (see file COPYING); if not, write to the   *
  * Free Software Foundation, Inc., 59 Temple Place, Suite 330,        *
  * Boston, MA 02111-1307 USA, or contact the authors.                 *
  *                                                                    *
  **********************************************************************/
#ifndef COMBINATIONS_H
#define COMBINATIONS_H
#include <set>
#include <vector>
#include <algorithm>
#include <cassert>



// all the combination of i numbers >= 1 whose sum is n

struct combinations
{
  typedef std::set< std::vector<int> > container;
  typedef container::const_iterator const_iterator;
  combinations( int k, int n )
  {
    assert( k <= n );
    if ( k == n )
    {
      _comb.insert( std::vector<int>( k, 1 ) );
    } 
    else
    {
      combinations comb( k, n - 1 );
      for ( int j = 0; j < k; j++ ) 
	for ( const_iterator i = comb.begin(); i != comb.end(); i++ )
	{
	  std::vector<int> v = *i;
	  v[ j ] ++;
	  _comb.insert( v );
	}
    }
  }
  int size() { return _comb.size(); }
  const_iterator begin() { return _comb.begin(); }
  const_iterator end() { return _comb.end(); }
private:
  container _comb;
};

#endif