SequentialPartitionGenerator Class Reference

#include <SequentialPartitionGenerator.h>

Public Types
typedef std::vector< int >	Partition

Public Member Functions
Partition	next_partition ()
	SequentialPartitionGenerator (int n, int k, int pmin=1)
	SequentialPartitionGenerator (int n, int k, int pmin, int pmax)

Private Member Functions
bool	first_part (Partition &p, int k, int n, int pmin, int pmax) const
bool	next_part (Partition &p) const

Private Attributes
int	n_first
int	n_next
int	the_k
int	the_n
Partition	the_part
int	the_pmax
int	the_pmin

Detailed Description

Class to compute partitions of size k of an integer n.

Definition at line 10 of file SequentialPartitionGenerator.h.

Member Typedef Documentation

typedef std::vector<int> SequentialPartitionGenerator::Partition

Definition at line 12 of file SequentialPartitionGenerator.h.

Constructor & Destructor Documentation

SequentialPartitionGenerator::SequentialPartitionGenerator	(	int	n,
		int	k,
		int	pmin = 1
	)

Definition at line 3 of file SequentialPartitionGenerator.cc.

                                                                                   :
  the_n(n), the_k(k), the_pmin(pmin), the_pmax(n) {}

SequentialPartitionGenerator::SequentialPartitionGenerator	(	int	n,
		int	k,
		int	pmin,
		int	pmax
	)

Definition at line 6 of file SequentialPartitionGenerator.cc.

                                                                                           :
  the_n(n), the_k(k), the_pmin(pmin), the_pmax(pmax) {}

Member Function Documentation

bool SequentialPartitionGenerator::first_part ( SequentialPartitionGenerator::Partition &  p, int  k, int  n, int  pmin, int  pmax  ) const

private

Definition at line 20 of file SequentialPartitionGenerator.cc.

References popcon2dropbox::copy(), first_part(), i, min(), n_first, and createTree::pp.

Referenced by first_part(), and next_part().

{
  n_first++;
  bool done=false;
  switch (k) {
  case 1:
    p[0]=std::min(pmax,n);
    return (n<=pmax && p[0]>=pmin);
  case 2:
    for (int i=std::min(pmax,n-1);i>=pmin;i--) {
      if ((done=(i>=n-i && n-i>=pmin))) {p[0]=i;p[1]=n-i;}
      return done;
    }
  default:
    Partition pp(p.begin()+1,p.end());
    for (int i=std::min(pmax,n-k+1);i>=pmin;i--) {
      p[0]=i;
      done=this->first_part(pp,k-1,n-p[0],pmin,p[0]);
      if (done) {copy(pp.begin(),pp.end(),p.begin()+1);}
      return done;
    }
  }
  return done;
}

bool SequentialPartitionGenerator::next_part ( SequentialPartitionGenerator::Partition &  p ) const

private

Definition at line 46 of file SequentialPartitionGenerator.cc.

References popcon2dropbox::copy(), first_part(), i, gen::k, gen::n, n_next, createTree::pp, the_k, the_n, the_pmax, and the_pmin.

Referenced by next_partition().

{
  n_next++;
  bool done=false;
  int k=p.size();
  switch (k) {
    case 0:  // empty partition: first call to next_part, initialize
      p.insert(p.begin(),the_k,0);
      return this->first_part(p,the_k,the_n,the_pmin,the_pmax);
    case 1:
      return false;
    default:
      int n=0;
      for (int i=0;i<k;i++) n=n+p[i];
      SequentialPartitionGenerator::Partition pp(p.begin()+1,p.end());
      done = (pp.size()>1 ? this->next_part(pp) : false);
      if (done)
      {
        copy(pp.begin(),pp.end(),p.begin()+1);
      } else {
        done = (p[0]==1 ? false :
                this->first_part(pp,k-1,n-p[0]+1,the_pmin,p[0]-1));
        if (done) { --p[0];copy(pp.begin(),pp.end(),p.begin()+1); }
      };
      return done;
  };
  return done;
}

SequentialPartitionGenerator::Partition SequentialPartitionGenerator::next_partition

(

)

Get the next partition, in a well-defined series of partition

Definition at line 9 of file SequentialPartitionGenerator.cc.

References relativeConstraints::empty, next_part(), and the_part.

{
  bool done=next_part(the_part);
  if (done)
  {
    return the_part;
  };
  SequentialPartitionGenerator::Partition empty;
  return empty;
}

Member Data Documentation

int SequentialPartitionGenerator::n_first

mutableprivate

Definition at line 34 of file SequentialPartitionGenerator.h.

Referenced by first_part().

int SequentialPartitionGenerator::n_next

mutableprivate

Definition at line 35 of file SequentialPartitionGenerator.h.

Referenced by next_part().

int SequentialPartitionGenerator::the_k

private

Definition at line 30 of file SequentialPartitionGenerator.h.

Referenced by next_part().

int SequentialPartitionGenerator::the_n

private

Definition at line 29 of file SequentialPartitionGenerator.h.

Referenced by next_part().

Partition SequentialPartitionGenerator::the_part

private

Definition at line 33 of file SequentialPartitionGenerator.h.

Referenced by next_partition().

int SequentialPartitionGenerator::the_pmax

private

Definition at line 32 of file SequentialPartitionGenerator.h.

Referenced by next_part().

int SequentialPartitionGenerator::the_pmin

private

Definition at line 31 of file SequentialPartitionGenerator.h.

Referenced by next_part().