#include <iterator>
#include <algorithm>
#include <functional>

// Based on code by Christopher Eltschka:
// http://groups.google.com/groups?selm=38568F79.13680B86%40physik.tu-muenchen.de&output=gplain

template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin, BidirectionalIterator combo_end, BidirectionalIterator end);

template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin, BidirectionalIterator combo_end, BidirectionalIterator end, Compare comp);

// Interprets the first elements of the sequence (between begin and
// combo_end) as "combo" and the rest as "size"; gives the next
// combination for the "combo". To avoid permutations of the same
// combo to be generated, Iterator::value_type must be
// less-than-comparable for the three-argument-version
//
// Preconditions:
//  - [begin, end) must be a valid range
//  - [begin, combo_end) must be a valid subrange of [begin, end)
//  - The sequences [begin, combo_end) and [combo_end, end) must
//    be sorted
//  - begin, end and combo_and must be mutable iterators
//
// return value:
//   false, if the sequence is now sorted (if starting with a sorted
//     sequence, this means that all combos were generated)
//   true otherwise
//
// After return from next_combination, [begin, combo_end) and
// [combo_end, end) are sorted again.
//
// Example usage:
// #include "src/basic_types/combinations.h"
// #include <list>
//
// int main()
// {
//   std::list<int> foo;
//   foo.push_back(1);
//   foo.push_back(2);
//
//   // Number to choose
//   int count = 1;
//
//   std::list<int>::iterator combo_end = foo.begin();
//
//   if (count > 0)
//     for (int i(1); i <= count; i++)
//       combo_end++;
//
//   do
//   {
//     std::list<int>::const_iterator a_value;
//
//     std::cout << "Chosen: ";
//     for(a_value = foo.begin(); a_value != combo_end; a_value++)
//       std::cout << *a_value;
//     std::cout << std::endl;
//
//     std::cout << "Not chosen: ";
//     for(a_value = combo_end; a_value != foo.end(); a_value++)
//       std::cout << *a_value;
//     std::cout << std::endl;
//   }
//   while(next_combination(foo.begin(), combo_end, foo.end()));
//
//   return 0;
// }

template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin, BidirectionalIterator combo_end, BidirectionalIterator end)
{
// MSVC++ doesn't support typename correctly (6.0 SP4)
#if defined(_MSC_VER) && _MSC_VER <= 1200
  return next_combination(
    begin, combo_end, end,
    std::less <std::iterator_traits <BidirectionalIterator>::value_type>());
#else
  return next_combination(
    begin, combo_end, end,
    std::less <typename std::iterator_traits <BidirectionalIterator>::value_type>());
#endif // defined(_MSC_VER) && _MSC_VER <= 1200
}

template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin, BidirectionalIterator combo_end, BidirectionalIterator end, Compare comp)
{
  if (combo_end == begin || combo_end == end)
    return false;
  
  BidirectionalIterator combo = combo_end;
  BidirectionalIterator total_set;

  --combo;
  total_set = std::upper_bound(combo_end, end, *combo, comp);
  if (total_set != end)
  {
    std::swap(*combo, *total_set);
    return true;
  }

  --total_set;
  combo = std::lower_bound(begin, combo_end, *total_set, comp);
  
  if (combo == begin)
  {
    std::rotate(begin, combo_end, end);
    return false;
  }

  BidirectionalIterator combo_next = combo;
  --combo;
  total_set = std::upper_bound(combo_end, end, *combo, comp);
  
  BidirectionalIterator sort_pos = end;
  std::advance(sort_pos, -std::distance(combo_end, total_set)-1);

  std::rotate(combo_next, total_set, end);
  std::rotate(combo, combo_next, end);
  std::rotate(combo_end, sort_pos, end);

  return true;
}

// --------------------------------------------------------------------------
// A useful function

#include <set>
#include <list>

template<class T>
set< set<T> > compute_combinations(const set<T> in_elements_to_choose_from)
{
  set< set<T> > sets_of_chosen_elements;

  // We need a list of the spare gates for the combination algorithm
  std::list<T> list_to_choose_from;

  // Copy the elements to choose from into the list. Sets are sorted, so the
  // resulting list will be sorted, as required by the // combination
  // algorithm.
  {
    std::set<T>::const_iterator an_element =
      in_elements_to_choose_from.begin();
    while(an_element != in_elements_to_choose_from.end())
    {
      list_to_choose_from.push_back(*an_element);
      an_element++;
    }
  }


  // Now compute the combinations and store them in the set of sets
  for (unsigned int number_to_select = 0;
    number_to_select <= in_elements_to_choose_from.size(); number_to_select++)
  {
    // This combination implementation needs the end of the combo, not the
    // number of elements to choose
    std::list<T>::iterator combo_end = list_to_choose_from.begin();

    for (unsigned int i(0); i <= number_to_select; i++)
      combo_end++;

    do
    {
      std::set<T> chosen_elements;

      chosen_elements.insert(list_to_choose_from.begin(), combo_end);

      sets_of_chosen_elements.insert(chosen_elements);
    }
    while(next_combination(list_to_choose_from.begin(), combo_end, list_to_choose_from.end()));
  }

  return sets_of_chosen_elements;
}