Generates all k-combinations of a range that may contain equal elements

next_combination.cpp

// [first, from) and [to, last) are non-overlapping ranges
template<class Iter>
void reverse_gapped(Iter first, Iter from, Iter to, Iter last) {
	if (from == to) {
		std::reverse(first, last);
		return;
	}
	if (first == from) {
		std::reverse(to, last);
		return;
	}
	if (last == to) {
		std::reverse(first, from);
		return;
	}
	--last;
	while (first != last) {
		std::iter_swap(first, last);
		++first;
		if (first == from) first = to;
		if (first == last) break;
		if (last == to) last = from;
		--last;
	}
}

//[first, middle) and [middle, last) are sorted before and after every call to this function
template<class Iter>
bool next_combination(Iter first, Iter middle, Iter last)
{
	if (middle == first || middle == last) {
		return false;
	}
	
	Iter left, right;
//	left = std::lower_bound(first, middle, *std::prev(last));
//	if (left == first) {
//		std::rotate(first, middle, last);
//		return false;
//	}
//	--left;
	left = std::prev(middle);
	for (right = std::prev(last); *left >= *right; --left) {
		if (left == first) {
			std::rotate(first, middle, last);
			return false;
		}
	}
	
//	right = std::upper_bound(middle, last, *left);
	while (right != middle && *std::prev(right) > *left) --right;
	
	std::iter_swap(left, right);
	++left; ++right;

	std::reverse(left, middle);
	std::reverse(right, last);
	reverse_gapped(left, middle, right, last);
	
	return true;
}

//[first, middle) is sorted and [middle, last) is reverse-sorted before and after every call to this function, doesn't need reverse_gapped
template<class Iter>
bool next_combination2(Iter first, Iter middle, Iter last)
{
	if (middle == first || middle == last) {
		return false;
	}
	
	Iter left, right;
	left = std::prev(middle);
	for (right = middle; *left >= *right; --left) {
		if (left == first) {
			std::reverse(first, middle);
			std::reverse(first, last);
			std::reverse(middle, last);
			return false;
		}
	}
	
	while (std::next(right) != last && *std::next(right) > *left) ++right;
	
	std::iter_swap(left, right);
	++left;

	std::reverse(left, middle);
	std::reverse(left, right);
	std::reverse(middle, right);
	
	return true;
}