/*-----------------------------------------------------------------------------
  
Copyright (C) 2022

A. Ronald Gallant
Post Office Box 659
Chapel Hill NC 27514-0659
USA

This program 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 2 of the License, or
(at your option) any later version.

This program 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 program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

-------------------------------------------------------------------------------

Class        n_choose_k - Generates all k combinations of n integers

Syntax       # include "libscl.h"
             class n_choose_k {
             private:
               //..
             public:
               n_choose_k() {error("Error, default constructor not allowed");}
               n_choose_k(INTEGER n, INTEGER k);
               void reset(INTEGER n, INTEGER k);
               void draw(intvec& lhs, intvec& rhs);
	       bool update();
             };

Declared in  libscl.h

Remark       k integers are returned in lhs, n-k in rhs.

Return value A bool is returned by update that is true until update is
             called for one past the ending combination. When false is 
	     returned, n_choose_k is reset to its initial state. A
	     subsequent call to draw will return the beginning combination.

Functions    Library: prev_permutation
called       libscl: (none)

Reference    https://stackoverflow.com/questions/12991758/creating-all-
             possible-k-combinations-of-n-items-in-c

Sample       #include "libscl.h"
program      //..
             INTEGER n=5, k=2;
             n_choose_k nck(n,k);
             intvec lhs, rhs;
             do {
               nck.draws(lhs,rhs);
               //..
             } while (nck.update());

------------------------------------------------------------------------------*/

#include "libscl.h"

using namespace scl;
using namespace std;

namespace scl {

  n_choose_k::n_choose_k(INTEGER n, INTEGER k)
  : N(n),K(k)
  { 
    if (K >= N) error("Error, k must be less than n");
    string bm(K,1); // K leading 1's
    bm.resize(N,0); // N-K trailing 0's
    bitmask = bm;
  }

  void n_choose_k::reset(INTEGER n, INTEGER k)
  {
    N = n;
    K = k;
    if (K >= N) error("Error, k must be less than n");
    string bm(K,1);  // K leading 1's
    bm.resize(N,0);  // N-K trailing 0's
    bitmask = bm;
  }

  void n_choose_k::draw(intvec& lhs, intvec& rhs)
  {
    lhs.resize(K);
    rhs.resize(N-K);
    INTEGER lhs_count = 0;
    INTEGER rhs_count = 0;
    for (INTEGER i=0; i<N; ++i) {
      if (bitmask[i]) {
        lhs[++lhs_count] = i+1;
      }
      else {
        rhs[++rhs_count] = i+1;
      }
    }
  }

  bool n_choose_k::update()
  {
    return prev_permutation(bitmask.begin(), bitmask.end());
  }

}
   
  
