shuffles.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// An iterator of shuffles.
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2009-2016 by Pawel Pilarczyk.
//
// This file is part of my research software package. This 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 3 of the License, or (at your option) any later version.
//
// This software 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 software; see the file "license.txt". If not,
// please, see <http://www.gnu.org/licenses/>.

// Started on March 24, 2009. Last revision: August 21, 2013.


#ifndef _CHAINCON_SHUFFLES_H_
#define _CHAINCON_SHUFFLES_H_


// include some standard C++ header files
#include <istream>
#include <ostream>
#include <vector>

// include selected header files from the CHomP library
#include "chomp/system/config.h"

// include relevant local header files


// --------------------------------------------------
// -------------------- shuffles --------------------
// --------------------------------------------------

/// An iterator of all the (p,q)-shuffles.
/// A (p,q)-shuffle (alpha, beta) is a partition of the set {0,...,p+q-1}
/// into two disjoint subsets, such that alpha_1 < ... < alpha_p
/// and beta_1 < ... < beta_q.
class Shuffles
{
public:
        /// The constructor in which the size of the shuffle is given.
        Shuffles (int p, int q);

        /// Rewinds the counter of the (p,q)-shuffles.
        void rewind ();

        /// Gets a (p,q)-shuffle and its signature.
        /// Returns true if more (p,q)-shuffles are available,
        /// or false if this was the last one (and rewinds the iterator).
        template <class ArrayP, class ArrayQ>
        bool get (ArrayP &alpha, ArrayQ &beta, int &sig);

private:
        /// The number p of the elements of the first set in the partition.
        int _p;

        /// The sum of the numbers of the elements of both sets
        /// in the partition: p + q.
        int _pq;

        /// A vector of counters that correspond to the first set
        /// in the partition.
        std::vector<int> _alpha;

}; /* class Shuffles */

// --------------------------------------------------

inline Shuffles::Shuffles (int p, int q): _p (p), _pq (p + q),
        _alpha ((p > 0) ? p : 1)
{
        if ((p < 0) || (q < 0))
                throw "Trying to define shuffles with negative p or q.";
        rewind ();
        return;
} /* Shuffles::Shuffles */

inline void Shuffles::rewind ()
{
        for (int i = 0; i < _p; ++ i)
                _alpha [i] = i;
        return;
} /* Shuffles::rewind */

template <class ArrayP, class ArrayQ>
inline bool Shuffles::get (ArrayP &alpha, ArrayQ &beta, int &sig)
{
        // copy the current shuffle
        int alpha_i = 0;
        int beta_i = 0;
        int cur = 0;
        for (int i = 0; i < _pq; ++ i)
        {
                if ((cur < _p) && (_alpha [cur] == i))
                {
                        alpha [alpha_i ++] = i;
                        ++ cur;
                }
                else
                {
                        beta [beta_i ++] = i;
                }
        }

        // compute the signature
        sig = 0;
        for (int i = 0; i < _p; ++ i)
                sig += _alpha [i] - i;

        // prepare the next shuffle following this algorithm
        // (http://stackoverflow.com/questions/17435030/)
        //int s = (1 << k) - 1;
        //while (!(s & 1 << N))
        //{
        //      // do stuff with s
        //      int lo = s & ~(s - 1);       // lowest one bit
        //      int lz = (s + lo) & ~s;      // lowest zero bit above lo
        //      s |= lz;                     // add lz to the set
        //      s &= ~(lz - 1);              // reset bits below lz
        //      s |= (lz / lo / 2) - 1;      // put back right number of bits
        //}

        // find the lowest number in the p-tuple
//      int lo = _alpha [0];
        // find the first number in the p-tuple that can be increased
        cur = 0;
        while ((cur < _p - 1) && (_alpha [cur + 1] - _alpha [cur] == 1))
                ++ cur;
        // if this is the last number and it cannot be increased then rewind
        if ((cur >= _p) || ((cur == _p - 1) && (_alpha [cur] == _pq - 1)))
        {
                rewind ();
                return false;
        }
        // increase this number and rewind the numbers below it
        ++ (_alpha [cur]);
        for (int i = 0; i < cur; ++ i)
                _alpha [i] = i;

        return true;
} /* Shuffles::get */


#endif // _CHAINCON_SHUFFLES_H_