SequentialCombinationGenerator< T > Class Template Reference

#include <SequentialCombinationGenerator.h>

Public Types
typedef std::vector< T >	Collection
typedef std::vector< Collection >	Combination
typedef SequentialPartitionGenerator::Partition	Partition
typedef std::vector< int >	Vecint

Public Member Functions
Combination	next_combination (Collection &coll)
	SequentialCombinationGenerator (Partition &part)

Private Member Functions
Vecint	next_combi (Vecint &cold, int n, const Partition &p)
Vecint	next_subset (const Vecint &_g, const Vecint &_c)
void	vecprint (const Vecint &v) const

Private Attributes
bool	dbg
Vecint	the_comb
int	the_k
int	the_n
Partition	the_part

Detailed Description

template<class T>
class SequentialCombinationGenerator< T >

Class to compute all distinct Combinations of a collection 'data' of objects of type 'T'. A Combination is a set of collections, each collection containing one or more objects, with any object in 'data' assigned to exactly one collection.

Definition at line 21 of file SequentialCombinationGenerator.h.

Member Typedef Documentation

template<class T >

typedef std::vector<T> SequentialCombinationGenerator< T >::Collection

Definition at line 24 of file SequentialCombinationGenerator.h.

template<class T >

typedef std::vector<Collection> SequentialCombinationGenerator< T >::Combination

Definition at line 25 of file SequentialCombinationGenerator.h.

template<class T >

typedef SequentialPartitionGenerator::Partition SequentialCombinationGenerator< T >::Partition

Definition at line 23 of file SequentialCombinationGenerator.h.

template<class T >

typedef std::vector<int> SequentialCombinationGenerator< T >::Vecint

Definition at line 26 of file SequentialCombinationGenerator.h.

Constructor & Destructor Documentation

template<class T >

SequentialCombinationGenerator< T >::SequentialCombinationGenerator ( Partition &  part )

inline

Definition at line 28 of file SequentialCombinationGenerator.h.

References SequentialCombinationGenerator< T >::the_comb, SequentialCombinationGenerator< T >::the_n, and SequentialCombinationGenerator< T >::the_part.

                                                      :
      the_part ( part ), the_k ( part.size() ),
      the_n ( accumulate ( part.begin(), part.end(), 0 ) )
  {
    sort(the_part.begin(),the_part.end());
    the_comb.reserve(the_n);
  };

Member Function Documentation

template<class T >

Vecint SequentialCombinationGenerator< T >::next_combi ( Vecint &  cold, int  n, const Partition &  p  )

inlineprivate

Definition at line 64 of file SequentialCombinationGenerator.h.

References popcon2dropbox::copy(), relativeConstraints::empty, mps_fire::i, gen::k, gen::n, SequentialCombinationGenerator< T >::next_subset(), p1, and alignCSCRings::s.

Referenced by SequentialCombinationGenerator< T >::next_combination().

  {
    Vecint empty;
    if (cold.empty()) { // first entry, initialize
      cold.reserve(n);
      for (int i=0;i<n;cold.push_back(++i));
      return cold;
    }
    int k=p.size();
    if (k==1) return empty;
    Vecint cnew(cold);
    int n1=n-p[0];
    Vecint cold1(cold.begin()+p[0],cold.end());
    Vecint cnew1(n1);
    Partition p1(p.begin()+1,p.end());
    cnew1=next_combi(cold1,n1,p1);
    if (!cnew1.empty()) {
      copy(cnew1.begin(),cnew1.end(),cnew.begin()+p[0]);
      return cnew;
    }
    Vecint cold2(cold.begin(),cold.begin()+p[0]);
    Vecint cnew2(p[0]);
    sort(cold.begin(),cold.end());
    sort(cold2.begin(),cold2.end());
    cnew2=next_subset(cold,cold2);
    if (cnew2.empty()) return empty;
    copy(cnew2.begin(),cnew2.begin()+p[0],cnew.begin());
    Vecint ss(n1);
    set_difference(cold.begin(),cold.end(),
                   cnew2.begin(),cnew2.end(),ss.begin());
    int ip=p[0];
    for (int i=1;i<k;i++) {
      if (p[i]!=p[i-1]) {
        copy(ss.begin(),ss.end(),&cnew[ip]);
        return cnew;
      }
      int mincnew2=cnew2[0];
      if (ss[n1-1]<mincnew2) return empty;
      Vecint::iterator j1=find_if(ss.begin(),ss.end(),bind2nd(std::greater<int>(),mincnew2));
      if (ss.end()-j1 < p[i]) return empty;
      Vecint sss(j1,ss.end());
      for (int j=0;j<p[i];j++){cnew[ip+j]=cnew2[j]=sss[j];}
      int n2=ss.size()-cnew2.size();
      if (n2==0) return cnew;
      Vecint s(n2);
      set_difference(ss.begin(),ss.end(),cnew2.begin(),cnew2.end(),s.begin());
      ss=s;
      ip+=p[i];
    }
   
   return empty; 
 
  };

template<class T >

Combination SequentialCombinationGenerator< T >::next_combination ( Collection &  coll )

inline

Create combinations obtained by dividing 'coll' according to partition the_part defined by the constructor.

Definition at line 39 of file SequentialCombinationGenerator.h.

References SequentialCombinationGenerator< T >::dbg, relativeConstraints::empty, mps_fire::i, checklumidiff::l, SequentialCombinationGenerator< T >::next_combi(), groupFilesInBlocks::temp, SequentialCombinationGenerator< T >::the_comb, SequentialCombinationGenerator< T >::the_k, SequentialCombinationGenerator< T >::the_n, and SequentialCombinationGenerator< T >::the_part.

  {
    dbg=false;
    Combination comb;
    Vecint newcomb=next_combi(the_comb,the_n,the_part);
    the_comb=newcomb;
    if (newcomb.empty()) {
      Combination empty;
      return empty;
    }
    int i=0;
    for (int j=0;j<the_k;j++) 
    {
      Collection temp;
      for (int l=0;l<the_part[j];l++) 
      {
        temp.push_back(coll[the_comb[i]-1]);
        i++;
      }
      comb.push_back(temp);
    }
    return comb;
  };

template<class T >

Vecint SequentialCombinationGenerator< T >::next_subset ( const Vecint &  _g, const Vecint &  _c  )

inlineprivate

Definition at line 118 of file SequentialCombinationGenerator.h.

References EnergyCorrector::c, popcon2dropbox::copy(), relativeConstraints::empty, spr::find(), g, diffTwoXMLs::g2, mps_fire::i, gen::k, and gen::n.

Referenced by SequentialCombinationGenerator< T >::next_combi().

  {
    Vecint g = _g;
    Vecint c = _c;
    Vecint empty;
    int n=g.size();
    int k=c.size();
    typename Vecint::iterator ind;
    for (int i=k-1;i>=0;i--) {
      if (c[i]<g[n-k+i]) {
        
    
//  ind=find(&g[0],&g[n-k+i],c[i])+1;
        
    Vecint::iterator g2 = g.begin();
    advance(g2,n-k+i);  
    
    ind=find(g.begin(),g2,c[i]);
    
    ind++;
    
    
    
    copy(ind,ind+k-i,&c[i]);
        return c;
      }
    }
    return empty;
  };

template<class T >

void SequentialCombinationGenerator< T >::vecprint ( const Vecint &  v ) const

inlineprivate

Definition at line 148 of file SequentialCombinationGenerator.h.

References gather_cfg::cout, mps_fire::i, and gen::n.

  {
    int n=v.size();
    for (int i=0;i<n;std::cout << v[i++]);
    std::cout << std::endl;
  };

Member Data Documentation

template<class T >

bool SequentialCombinationGenerator< T >::dbg

mutableprivate

Definition at line 160 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination().

template<class T >

Vecint SequentialCombinationGenerator< T >::the_comb

mutableprivate

Definition at line 159 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().

template<class T >

int SequentialCombinationGenerator< T >::the_k

private

Definition at line 157 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination().

template<class T >

int SequentialCombinationGenerator< T >::the_n

private

Definition at line 153 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().

template<class T >

Partition SequentialCombinationGenerator< T >::the_part

private

Definition at line 158 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().