Добавить пару комбинаторных функций

Ayrtat
Ayrtat
template<typename InputIt, typename T>
bool nextPermutationWithRepetition(InputIt begin, InputIt end, T from_value, T to_value) {
	auto it = std::find_if_not(std::make_reverse_iterator(end),
	std::make_reverse_iterator(begin),
	[&to_value](auto current) { return to_value == current; });

	if (it == std::make_reverse_iterator(begin))
		return false;

	auto bound_element_iterator = std::prev(it.base());

	(*bound_element_iterator)++;
	std::fill(std::next(bound_element_iterator), end, from_value);

	return true;
}

template<typename InputIt, typename T>
bool nextCombination(InputIt begin,
		     InputIt end,
		     T toElement) {
	const auto lengthOfSubsequence = std::distance(begin, end);
	auto pos = lengthOfSubsequence;

	auto viewed_element_it = std::make_reverse_iterator(end);
	auto reversed_begin = std::make_reverse_iterator(begin);

	/*Looking for this element here*/

	while ((viewed_element_it != reversed_begin) && 
               (*viewed_element_it >= toElement - lengthOfSubsequence + std::distance(viewed_element_it, reversed_begin))) 
        { viewed_element_it++; }

	if (viewed_element_it == reversed_begin)
		return false;

	auto it = std::prev(viewed_element_it.base());

	std::iota(it, end, *it + 1); //with C++17

	return true;
}

/* The example of usage */

std::list<int> vec(3);

do {
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
} while (nextPermutationWithRepetition(vec.begin(), vec.end(), 0, 2));

std::list<int> vec = { 1, 2, 3 };

do {
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
} while (nextCombination(vec.begin(), vec.end(), 10));

​
template<typename InputIt, typename T>
bool nextPermutationWithRepetition(InputIt begin, InputIt end, T from_value, T to_value) {
	auto it = std::find_if_not(std::make_reverse_iterator(end),
	std::make_reverse_iterator(begin),
	[&to_value](auto current) { return to_value == current; });

	if (it == std::make_reverse_iterator(begin))
		return false;

	auto bound_element_iterator = std::prev(it.base());

	(*bound_element_iterator)++;
	std::fill(std::next(bound_element_iterator), end, from_value);

	return true;
}

template<typename InputIt, typename T>
bool nextCombination(InputIt begin,
		     InputIt end,
		     T toElement) {
	const auto lengthOfSubsequence = std::distance(begin, end);
	auto pos = lengthOfSubsequence;

	auto viewed_element_it = std::make_reverse_iterator(end);
	auto reversed_begin = std::make_reverse_iterator(begin);

	/*Looking for this element here*/

	while ((viewed_element_it != reversed_begin) && 
               (*viewed_element_it >= toElement - lengthOfSubsequence + 									  std::distance(viewed_element_it, reversed_begin))) { viewed_element_it++; }

	if (viewed_element_it == reversed_begin)
		return false;

	auto it = std::prev(viewed_element_it.base());

	std::iota(it, end, *it + 1); //with C++17

	return true;
}

/* The example of usage */

std::list<int> vec(3);

do {
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
} while (nextPermutationWithRepetition(vec.begin(), vec.end(), 0, 2));

std::list<int> vec = { 1, 2, 3 };

do {
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
} while (nextCombination(vec.begin(), vec.end(), 10));

3
рейтинг
Нет комментариев
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения