IntegerComposition Class Reference

Lists a weak composition of an integer N up to length L with a constraint that each summand does not exceed Max. More...

#include <IntegerComposition.hpp>

Collaboration diagram for IntegerComposition:

Public Member Functions
__host__ __device__	IntegerComposition ()
	Construct a new Integer Composition object.
__host__ __device__	IntegerComposition (int N, int Length, int Max)
__host__ __device__	IntegerComposition (IntegerComposition const &other)
__host__ __device__ int	value () const
__host__ __device__ int	length () const
__host__ __device__ int	max () const
__host__ __device__ Index_t	dim () const
__host__ void	status (void) const
	Show the status of the instance.
template<typename Vector_t >
__host__ __device__ Index_t	partToOrdinal (Vector_t const &vec) const
	Converts an composition of the integer N from a vector form to an ordinal number.
template<class Vector_t >
__host__ __device__ void	ordinalToPart (Vector_t &vec, Index_t const num) const
	Converts an ordinal number of a composition of the integer N to a vector form.
__host__ __device__ Eigen::RowVectorXi	ordinalToPart (Index_t const num) const
template<typename Index_ >
__host__ __device__ int	locNumber (Index_ const num, Index_ const pos) const
template<class Vector_t >
__host__ __device__ Index_t	translate (Index_t const num, int trans, Vector_t &workSpace) const
__host__ __device__ Index_t	translate (Index_t const num, int trans) const

Private Types
typedef unsigned long	Index_t

Private Attributes
int	m_N
int	m_Length
int	m_Max
Index_t	m_dim
Eigen::MatrixX< Index_t >	workA
Eigen::MatrixX< Index_t >	workB

Detailed Description

Lists a weak composition of an integer N up to length L with a constraint that each summand does not exceed Max.

Member Typedef Documentation

Index_t

typedef unsigned long IntegerComposition::Index_t

private

Constructor & Destructor Documentation

IntegerComposition() [1/3]

__host__ __device__ IntegerComposition::IntegerComposition ( )

inline

Construct a new Integer Composition object.

Parameters

N	Integer to be decomposed
Length	Number of parts into which N is decomposed
Max	Maximum number of each part that composes the integer N

{ debug_constructor_printf(Default); }

IntegerComposition() [2/3]

IntegerComposition::IntegerComposition ( int  N, int  Length, int  Max  )

inline

    : m_N(N),
      m_Length(Length),
      m_Max(Max < N ? Max : N),
      workA(N + 1, Length),
      workB(N + 1, Length) {
    // debug_printf("IntegerComposition::IntegerComposition(%d,%d,%d) : Dim = %d\n", (int)N,
    //              (int)Length, (int)Max, (int)m_dim);
    if(Length <= 1) {
        m_dim = Length;
        return;
    }
 
    int   max  = std::min(Max, N);
    auto& Dims = workB;
    for(int l = 0; l < Length; ++l) Dims(0, l) = 1;
    for(int n = N; n > max; --n) {
        Dims(n, 1)  = 0;
        Dims(n, 0)  = 0;
        workA(n, 0) = 0;
    }
    for(int n = max; n >= 0; --n) {
        Dims(n, 1)  = 1;
        Dims(n, 0)  = 0;
        workA(n, 0) = 0;
    }
    // Recursively calculate Dims(l,n) for remaining (l,n)
    for(int l = 2; l < Length; ++l)
        for(int n = 1; n <= N; ++n) {
            Dims(n, l) = 0;
            for(int k = 0; k <= std::min(max, n); ++k) { Dims(n, l) += Dims(n - k, l - 1); }
        }
    //   std::cout << Dims << "\n" << std::endl;
 
    for(int l = 1; l < Length; ++l) {
        workA(0, l) = Dims(N, Length - l);
        for(int n = 1; n <= N; ++n) workA(n, l) = workA(n - 1, l) + Dims(N - n, Length - l);
    }
    // std::cout << workA << "\n" << std::endl;
 
    for(int l = 0; l < Length; ++l) workB(0, l) = 0;
    for(int n = 1; n <= N; ++n) {
        for(int l = 1; l < Length - 1; ++l) workB(n, l) = workA(n - 1, l) - workA(n - 1, l + 1);
        workB(n, Length - 1) = workA(n - 1, Length - 1);
    }
    // std::cout << workB << "\n" << std::endl;
 
    m_dim = workA(max, 1);
    // std::cout << "Dim = " << m_dim << std::endl;
    debug_printf("(END) IntegerComposition::IntegerComposition(%d,%d,%d) : Dim = %d\n", (int)N,
                 (int)Length, (int)Max, (int)m_dim);
}

IntegerComposition() [3/3]

__host__ __device__ IntegerComposition::IntegerComposition ( IntegerComposition const &  other )

inline

            : m_N(other.value()),
              m_Length(other.length()),
              m_Max(other.max()),
              m_dim(other.dim()),
              workA(other.workA),
              workB(other.workB) {
            debug_constructor_printf((Copy));
        }

Member Function Documentation

dim()

__host__ __device__ Index_t IntegerComposition::dim ( ) const

inline

{ return m_dim; };

length()

__host__ __device__ int IntegerComposition::length ( ) const

inline

{ return m_Length; };

locNumber()

template<typename Index_ >

__host__ __device__ int IntegerComposition::locNumber ( Index_ const  num, Index_ const  pos  ) const

inline

                                                                                     {
    // Eigen::ArrayXi config(m_Length);
    // this->ordinalToPart(config, num);
    // return config(pos);
 
    auto num_copy = num;
    auto position = ((pos % m_Length) + m_Length) % m_Length;
    int  z = 0, zprev = 0;
    int  l;
    for(l = 1; l != m_Length - position; ++l) {
        assert(z < workA.rows());
        assert(l < workA.cols());
        while(workA(z, l) <= num_copy) z += 1;
        zprev = z;
 
        assert(z < workB.rows());
        assert(l < workB.cols());
        num_copy -= workB(z, l);
    }
    assert(z < workA.rows());
    assert(l < workA.cols());
    if(pos == 0) { return m_N - z; }
    else {
        while(workA(z, l) <= num_copy) z += 1;
        return z - zprev;
    }
}

max()

__host__ __device__ int IntegerComposition::max ( ) const

inline

{ return m_Max; };

ordinalToPart() [1/2]

__host__ __device__ Eigen::RowVectorXi IntegerComposition::ordinalToPart ( Index_t const  num ) const

inline

                                                                                    {
            Eigen::RowVectorXi res(this->m_Length);
            this->ordinalToPart(res, num);
            return res;
        }

ordinalToPart() [2/2]

template<typename Vector_t >

__host__ __device__ void IntegerComposition::ordinalToPart ( Vector_t &  vec, IntegerComposition::Index_t const  num  ) const

inline

Converts an ordinal number of a composition of the integer N to a vector form.

Parameters

[out]	vec	A vector to which the resulting composition of the integer N is assigned
[in]	num	An ordinal of a composition of the integer N to be converted to a vector form

                                                              {
    IntegerComposition::Index_t num_copy = num;
    int                         z = 0, zprev = 0;
#ifndef __CUDA_ARCH__
    vec.resize(m_Length);
#else
    assert(vec.size() >= m_Length);
#endif
    // if constexpr(is_container_v<Vector_t>) { vec.resize(m_Length); }
    for(int l = 1; l != m_Length; ++l) {
        assert(z < workA.rows());
        assert(l < workA.cols());
        while(workA(z, l) <= num_copy) z += 1;
 
        assert(m_Length - l >= 0);
        assert(m_Length - l < vec.size());
        vec[m_Length - l] = z - zprev;
        zprev             = z;
 
        assert(z < workB.rows());
        assert(l < workB.cols());
        num_copy -= workB(z, l);
    }
    vec[0] = m_N - z;
}

partToOrdinal()

template<typename Vector_t >

__host__ __device__ IntegerComposition::Index_t IntegerComposition::partToOrdinal ( Vector_t const &  vec ) const

inline

Converts an composition of the integer N from a vector form to an ordinal number.

Parameters

[in]

vec

Composition of the integer N

Returns

unsigned long : An ordinal number corresponding to the input composition (vec) of N.

Note

An ordinal here is a non-negative number, including zero.

                               {
    IntegerComposition::Index_t z = 0, res = 0;
    for(int l = 1; l != int(m_Length); ++l) {
        assert(m_Length - l >= 0);
        assert(m_Length - l < vec.size());
        z += vec[m_Length - l];
 
        assert(z < workB.rows());
        assert(l < workB.cols());
        res += workB(z, l);
    }
    return res;
}

status()

__host__ void IntegerComposition::status ( void  ) const

inline

Show the status of the instance.

• N: Integer to be decomposed
• Length: Number of parts into which N is decomposed
• Max: Maximum number of each part that composes the integer N
• Dim: Number of ways to decompose the integer N

                                         {
            std::cout << "IntegerComposition.status()"
                      << "\n"
                      << "\tValue:" << this->m_N << "\n"
                      << "\tLength:" << this->m_Length << "\n"
                      << "\tMax:   " << this->m_Max << "\n"
                      << "\tDim:   " << this->m_dim << std::endl;
            std::cout << "workA:\n"
                      << workA << "\n"
                      << "workB:\n"
                      << workB << std::endl;
        }

translate() [1/2]

__host__ __device__ Index_t IntegerComposition::translate ( Index_t const  num, int  trans  ) const

inline

                                                                                  {
            Eigen::ArrayXi config(m_Length);
            return this->translate(num, trans, config);
        }

translate() [2/2]

template<class Vector_t >

__host__ __device__ IntegerComposition::Index_t IntegerComposition::translate ( IntegerComposition::Index_t const  num, int  trans, Vector_t &  workSpace  ) const

inline

                                                                               {
    if(workSpace.size() < m_Length)
        debug_printf("%s\n\tworkSpace.size()=%d\n", __PRETTY_FUNCTION__, (int)workSpace.size());
    assert(workSpace.size() >= m_Length);
    // debug_printf("%s\n\t workSpace=%p, workSpace.size()=%d, m_Length=%d\n", __PRETTY_FUNCTION__,
    //                workSpace.data(), (int)workSpace.size(), (int)m_Length);
    this->ordinalToPart(workSpace, num);
    Index_t z = 0, res = 0;
    for(int l = 0; l < int(m_Length); ++l) {
        // if(!(z < workB.rows()) || !(l < workB.cols())) {
        //  debug_printf("\t (z=%d, l=%d), workB.rows()=%d, workB.cols()=%d\n", (int)z, (int)l,
        //               (int)workB.rows(), (int)workB.cols());
        // }
        assert(z < workB.rows());
        assert(l < workB.cols());
        res += workB(z, l);
 
        assert(int(m_Length - 1 - l + trans) % workSpace.size() < workSpace.size());
        z += workSpace[int(m_Length - 1 - l + trans) % workSpace.size()];
    }
    return res;
}

value()

__host__ __device__ int IntegerComposition::value ( ) const

inline

{ return m_N; };

Member Data Documentation

m_dim

Index_t IntegerComposition::m_dim

private

m_Length

int IntegerComposition::m_Length

private

m_Max

int IntegerComposition::m_Max

private

m_N

int IntegerComposition::m_N

private

workA

Eigen::MatrixX<Index_t> IntegerComposition::workA

private

workB

Eigen::MatrixX<Index_t> IntegerComposition::workB

private

---

The documentation for this class was generated from the following file:

• /Users/shoki/GitHub/Locality/Headers/Algorithm/IntegerComposition.hpp