SequentialCombinationGenerator< T > Class Template Reference

#include <SequentialCombinationGenerator.h>

List of all members.

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 (Vecint g, 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 python::multivaluedict::sort(), 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
	)		[inline, private]

Definition at line 64 of file SequentialCombinationGenerator.h.

References filterCSVwithJSON::copy, relativeConstraints::empty, i, j, gen::k, n, SequentialCombinationGenerator< T >::next_subset(), p1, alignCSCRings::s, and python::multivaluedict::sort().

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

  {
    Vecint empty;
    if (cold.size()==0) { // 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.size()!=0) {
      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.size()==0) 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];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 bookConverter::comb, SequentialCombinationGenerator< T >::dbg, relativeConstraints::empty, i, j, prof2calltree::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.size()==0) {
      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	(	Vecint	g,
		Vecint	c
	)		[inline, private]

Definition at line 118 of file SequentialCombinationGenerator.h.

References trackerHits::c, filterCSVwithJSON::copy, relativeConstraints::empty, spr::find(), diffTwoXMLs::g2, i, gen::k, and n.

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

  {
    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 [inline, private]

Definition at line 146 of file SequentialCombinationGenerator.h.

References gather_cfg::cout, i, and 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 [mutable, private]

Definition at line 158 of file SequentialCombinationGenerator.h.

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

template<class T >

Vecint SequentialCombinationGenerator< T >::the_comb [mutable, private]

Definition at line 157 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 155 of file SequentialCombinationGenerator.h.

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

template<class T >

int SequentialCombinationGenerator< T >::the_n [private]

Definition at line 151 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 156 of file SequentialCombinationGenerator.h.

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