mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

next_combination
(z_other/next_combination.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "z_other/next_combination.hpp"
• Link: https://qiita.com/mdstoy/items/39104b686540c5f1dc6c

next_combination

使い方

next_combination(T first, T last, int k) : イテレータの $[first, last)$ 間の上位 $k$ 個について、 $nCk$ の全ての組み合わせを順に返す。

Code

#pragma once

#include<algorithm>
#include<iterator>

// https://qiita.com/mdstoy/items/39104b686540c5f1dc6c
template <typename T> bool next_combination(const T first, const T last, int k) {
	const T subset = first + k;
	// empty container | k = 0 | k == n 
	if (first == last || first == subset || last == subset) {
		return false;
	}
	T src = subset;
	while (first != src) {
		src--;
		if (*src < *(last - 1)) {
			T dest = subset;
			while (*src >= *dest) {
				dest++;
			}
			iter_swap(src, dest);
			rotate(src + 1, dest + 1, last);
			rotate(subset, subset + (last - dest) - 1, last);
			return true;
		}
	}
	// restore
	rotate(first, subset, last);
	return false;
}

#line 2 "z_other/next_combination.hpp"

#include<algorithm>
#include<iterator>

// https://qiita.com/mdstoy/items/39104b686540c5f1dc6c
template <typename T> bool next_combination(const T first, const T last, int k) {
	const T subset = first + k;
	// empty container | k = 0 | k == n 
	if (first == last || first == subset || last == subset) {
		return false;
	}
	T src = subset;
	while (first != src) {
		src--;
		if (*src < *(last - 1)) {
			T dest = subset;
			while (*src >= *dest) {
				dest++;
			}
			iter_swap(src, dest);
			rotate(src + 1, dest + 1, last);
			rotate(subset, subset + (last - dest) - 1, last);
			return true;
		}
	}
	// restore
	rotate(first, subset, last);
	return false;
}

Back to top page