Algorithm code: Combination opposite to std::permutation

[BenBear <cxj26424 at 163 dot com>]

Hi, libstdc++-v3

adjust_combination ()
next_combination ()
prev_combination ()

I wrote a algorithm of combination, which is opposite to
std::permutation.  It provides three operations, adjust_combination(),
next_combination() and prev_combination().  The next_combination() and
prev_combination() is just like the std::next_permutation() and
std::perv_permutation().

Each operation's arguments are three iterators, first, middle and last.
I treat the range [first, middle) as the elements selected, while the
range [middle, last) are the elements left.  The range [first, middle)
is treated in dictionary ordering, like the std::permutation.  [middle,
last) is maintained in a special ordering.

A simple example:

select 2 elements from {1, 2, 3, 4}
f   m   l              // f: first,   m: middle,    l: last
1 2, 3 4 
1 3, 4 2 
1 4, 3 2 
2 3, 4 1 
2 4, 3 1 
3 4, 2 1 

The first two number are the elements selected, in dictionary ordering.
The next combination of {3 4}/{2 1} will be {1 2}/{3 4}.

Ben Bear

// 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;

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
}

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) || (middle == last))
    return;

  sort_combination (first, middle);
  sort_combination (middle, last);

  BiIterator b = middle;
  --b;
  BiIterator j = lower_bound (middle, last, *b);
  reverse (j, last);
  reverse (middle, last);
}

template <typename BiIterator>
void
init_combination (BiIterator first, BiIterator middle, BiIterator last,
		  bool min)
{
  sort_combination (first, last);

  if (min == false)
    {
      // the max combination
      reverse (first, last);
      reverse (first, middle);
    }
}

template <typename BiIterator>
bool
next_combination (BiIterator first, BiIterator middle, BiIterator last)
{
  if ((first == middle) || (middle == last))
    return false;

  // last element of [first, middle)
  BiIterator b = middle;
  --b;

  if (*b < *middle)
    {
      BiIterator j = b;
      while ((++b != last) && (*j < *b))
	{
	  iter_swap (j, b);
	  j = b;
	}
      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 (!(*first < *e))
    {
      reverse (first, middle);
      reverse (first, last);
      return false;
    }

  if (*b < *e)
    {
      BiIterator bb = b;
      while ((++bb != e) && !(*b < *bb))
	;
      reverse (bb, f);
      reverse (b, f);
    }
  else
    {
      BiIterator i = b;
      while (!(*--i < *e))
	;
      
      BiIterator j = last;
      while (!(*i < *--j))
	;

      iter_swap (i, j);
      reverse (++i, middle);
      reverse (i, j);
    }
  return true;
}

template <typename BiIterator>
bool
prev_combination (BiIterator first, BiIterator middle, BiIterator last)
{
  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);
    }
  system ("Pause");


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

  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);
      system ("Pause");
    }

  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);
      system ("Pause");
    }


  system ("Pause");
  return 0;
}