Combination algorithm opposite to std::permutation

[BenBear <cxj26424 at 163 dot com>]

Hi, chris,

Excuse me. I want to submit my code of combination algorithm. My
combination algorithm is compatible with std::permutation. I'm sorry i
can't say more particular. But, I'm sure the Combination is as `GOOD' as
the std::permutation.

BenBear

ps: I wrote a letter two months ago. But nobody reply me. Sorry, I don't
know how to work with the mailing list.
http://gcc.gnu.org/ml/libstdc++/2005-04/msg00224.html

// Combination algorithm implementation

// Copyright (C) 2004, BenBear
//
// This file is an algorithm of the combination. This library 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, or (at your option) any later
// version.

// This library 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 library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

#include <algorithm>

namespace benbear
{

  using namespace std;

  // BiIterator ::  Binary Direction Iterator
  

  /****    sort_combination     *********
   *
   *  merge sort needed by benbear::combination
   */
  template <typename BiIterator>
  void
  sort_combination (BiIterator first, BiIterator last)
  {
    if (first == last) // no element
      return;
    
    BiIterator i = first;
    ++i;
    if (i == last)     // one element
      return;
    
    int half = distance (first, last) / 2;  // half of the length
    BiIterator middle = first;
    advance (middle, half);  // middle += half
    
    sort_combination (first, middle);     // sort first part
    sort_combination (middle, last);      // sort second part
    
    inplace_merge (first, middle, last);  // merge two parts
  }
  

  /*******    adjust_combination     ********
   *
   *  adjust the ranges, [first, middle) and [middle, last), to a
   *  standard combination sequence
   */
  template <typename BiIterator>
  void
  adjust_combination (BiIterator first, BiIterator middle, BiIterator last)
  {
    // the front part or the back part have no elements
    if (first == middle)
      {
	sort_combination (middle, last);
	return;
      }
    if (middle == last)
      {
	sort_combination (first, middle);
	return;
      }
    
    sort_combination (first, middle);
    sort_combination (middle, last);
    
    BiIterator b = middle;
    --b;
    BiIterator j = lower_bound (middle, last, *b);
    // [j, last) is the range which is not small than the last element
    // of the front part
    reverse (j, last);
    reverse (middle, last);
  }
  

  /***********     init_combination     *********
   *
   *  initialize the ranges to the first or last of the standard
   *  combination sequences
   */
  template <typename BiIterator>
  void
  init_combination (BiIterator first, BiIterator middle, BiIterator last,
		    bool min)
  {
    // this is the min combination sequence
    sort_combination (first, last);
    

    if (min == false)		// max ?
      {
	// the max combination
	reverse (first, last);
	reverse (first, middle);
      }
  }
  
  /************         next_combination           ***************
   *
   *  get the next (bigger) combination sequence of current sequence
   */
  template <typename BiIterator>
  bool
  next_combination (BiIterator first, BiIterator middle, BiIterator last)
  {
    // the front or the back part is empty, only need to sort them
    if ((first == middle) || (middle == last))
      return false;


    BiIterator b = middle;	// last element of [first, middle)
    --b;
    
    if (*b < *middle)
      {
	// *b < *middle, then *b is just the element which we look for
	BiIterator j = b;
	while ((++b != last) && (*j < *b))
	  {
	    iter_swap (j, b);
	    j = b;
	  }
	return true;
      }
    
    BiIterator e = last;	// biggest of the back part
    --e;
    while (e != middle)
      {
	BiIterator k = e;
	--k;
	if (!(*k < *e))
	  e = k;
	else
	  break;
      }	// get the biggest `e'
    
    BiIterator f = e;		// right element of the *e
    ++f;
    while ((f != last) && !(*f < *e))
      ++f;
    

    if (!(*first < *e))
      {
	// the front part is bigger than the back part, 
	// it's the max combination sequence
	reverse (first, middle);
	reverse (first, last);
	return false;
      }
    

    if (*b < *e)
      {
	// target element will be found in [middle, e]
	BiIterator bb = b;
	while ((++bb != e) && !(*b < *bb))
	  ;
	reverse (bb, f);
	reverse (b, f);
      }
    else
      {
	BiIterator i = b;	// `i' is the max element select out
	while (!(*--i < *e))
	  ;
	
	BiIterator j = last;	// `j' is the min element select in
	while (!(*i < *--j))
	  ;
	
	// now, *j > *i. replace *i with *j, then adjust the
	// combination sequence
	iter_swap (i, j);
	reverse (++i, middle);
	reverse (i, j);
      }
    return true;
  }
  

  /****************         prev_combination        **************
   *
   *  get the previous (smaller) combination sequence of the current
   *  sequence
   */
  template <typename BiIterator>
  bool
  prev_combination (BiIterator first, BiIterator middle, BiIterator last)
  {
    // the front or the back part is empty, only need to sort them
    if ((first == middle) || (middle == last))
      return false;

    
    BiIterator b = middle;
    --b;
    
    if (*middle < *b)
      {
	BiIterator i = upper_bound (first, middle, *middle);
	if (i != b)
	  iter_swap (i, middle);
	else
	  {
	    BiIterator s = middle;
	    while ((++s != last) && !(*s < *middle))
	      ;
	    reverse (b, s);
	  }
	
	return true;
      }
    
    BiIterator e = last;
    --e;
    while (e != middle)
      {
	BiIterator k = e;
	--k;
	if (!(*k < *e))
	  e = k;
	else
	  break;
      }
    
    BiIterator f = e;
    ++f;
    while ((f != last) && !(*f < *e))
      ++f;
    
    if (f == last)
      {
	reverse (first, last);
	reverse (first, middle);
	return false;
      }
    
    BiIterator i = upper_bound (first, middle, *f);
    if (i == b)
      {
	BiIterator s = f;
	while ((++s != last) && !(*s < *f))
	  ;
	
	reverse (b, f);
	reverse (b, s);
      }
    else
      {
	iter_swap (i, f);
	reverse (++i, f);
	reverse (i, middle);
      }
    return true;
  }
  
} // end of namespace benbear


// for test:
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

template <typename BiIterator>
void
show_array (BiIterator f, BiIterator m, BiIterator l)
{
  while (f != m)
    cout << *f++;
  cout << " ";
  while (f != l)
    cout << *f++;
  cout << endl;
}

template <typename BiIterator>
void
combi (BiIterator f, BiIterator m, BiIterator l, bool next)
{
  benbear::init_combination (f, m, l, next);
  int c = 0;
  cout << endl;
  do
    {
      show_array (f, m, l);
      c++;
    }
  while (next ? benbear::next_combination (f, m, l)
	 : benbear::prev_combination (f, m, l));
  cout << "The end: ";
  show_array (f, m, l);
  cout << "There's: " << c << endl;
}

int
main ()
{
  int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  bool dir = false;

  for (int i = 1; i < 10; i++)
    {
      random_shuffle (a, a+7);
      sort (a, a+3);
      benbear::adjust_combination (a, a+3, a+7);
      show_array (a, a+3, a+7);
    }


  for (int i = 1, j = 9; i < j; i++)
    {
      combi (a, a+i, a+j, dir);
    }

  sort (a, a+9);
  benbear::sort_combination (a, a+7);
  a[1] = 1;
  a[4] = 6;
  //a[6] = 6;
  for (int i = 1, j = 7; i < j; i++)
    {
      combi (a, a+i, a+j, dir);
    }

  int n;
  cout << "The n: ";
  cin >> n;
  vector<int> vec(n);
  cout << "please. input numbers: " << endl;
  for (int i = 0; i < n; i++)
    cin >> vec[i];

  for (int i = 1; i < n; i++)
    {
      combi (vec.begin(), vec.begin()+i, vec.end(), dir);
    }


  return 0;
}